个人业务网站创建,网站建设零基础教学,塘沽网站开发,个人建网站流程C-STL01- 容器 引入 我们想存储多个学员的信息 , 现在学员数量不定 通过以前学习的知识 , 我们可以创建一个数组存储学员的信息 但是这个数组大小是多少呢 ? 过大会导致空间浪费 , 小了又需要扩容 对其中的数据进行操作也较为复杂 每次删除数据后还要对其进行回收等操作… C-STL01- 容器 引入 我们想存储多个学员的信息 , 现在学员数量不定 通过以前学习的知识 , 我们可以创建一个数组存储学员的信息 但是这个数组大小是多少呢 ? 过大会导致空间浪费 , 小了又需要扩容 对其中的数据进行操作也较为复杂 每次删除数据后还要对其进行回收等操作 这样我们在编写代码时将大量的时间在这种无关业务的事情上被浪费 为了我们能更好的关心业务操作 程序人员从函数 (functions) 类别 (classes), 函数库 (function libraries), 类别库 (classlibraries) 、各种组件从模块化设计到面向对象 (object oriented ) 进行设计 , 提供 了为了建立数据结构和算法的一套标准并且降低他们之间的耦合关系以提升各自的独 立性、弹性、交互操作性 ( 相互合作性 ,interoperability), 诞生了 STL 概述 STL(Standard Template Library, 标准模板库 ), 是惠普实验室开发的一系列软件的统称。 STL 六大组件 容器 : 作用 : 容纳存储数据 分类 : 序列式容器 强调值的排序每个元素均有固定的位置 除非用删除或插入的操作改 变这个位置 如 vector, deque/queue, list; 关联式容器 : 非线性更准确的说是二叉树结构各元素之间没有严格的物理上的顺 序关系 ; 在数据中选择一个关键字 key 这个 key 对数据起到索引的作用方便查 找。 如 Set/multiset Map/multimap 容器 注意 : 容器可以嵌套容器 算法 : 作用 : 操作数据 , 如插入数据、删除数据、修改数据、排序等 分类 : 质变算法是指运算过程中会更改区间内的元素的内容。例如拷贝替换删 除等等 优点 常用容器 string 作用 : 存储字符的容器 常用操作 构造函数 非质变算法是指运算过程中不会更改区间内的元素内容例如查找、计数、 遍历、寻找极值等等 迭代器 作用 : 容器与算法之间的粘合剂 注意 : 每个容器都有自己的迭代器 分类 : 输入迭代器 提供对数据的只读访问 只读支持 、 、 输出迭代器 提供对数据的只写访问 只写支持 前向迭代器 提供读写操作并能向前推进迭代器 读写支持 、 、 双向迭代器 提供读写操作并能向前和向后操作 读写支持 、 -- 随机访问迭代器 提供读写操作并能以跳跃的方式访问容器的任意数据是 功能最强的迭代器读写支持 、 -- [n] 、 - n 、 、 、 、 仿函数 作用 : 为算法提供策略 适配器 作用 : 为算法提供更多的参数接口 空间配置器 作用 : 为容器和算法管理空间 有高可重用性 高性能 高移植性 跨平台 string();// 创建一个空的字符串 例如 : string str; string(const string str);// 使用一个 string 对象初始化另一个 string 对象 string(const char* s);// 使用字符串 s 初始化 string(int n, char c);// 使用 n 个字符 c 初始化 v 基本赋值操作 获取字符串长度 存取字符操作 示例 拼接操作 string operator(const char* s);//char 类型字符串赋值给当前的字符串 string operator(const string s);// 把字符串 s 赋给当前的字符串 string operator(char c);// 字符赋值给当前的字符串 string assign(const char *s);// 把字符串 s 赋给当前的字符串 string assign(const char *s, int n);// 把字符串 s 的前 n 个字符赋给当前的字符 串 string assign(const string s);// 把字符串 s 赋给当前字符串 string assign(int n, char c);// 用 n 个字符 c 赋给当前字符串 string assign(const string s, int start, int n);// 将 s 从 start 开始 n 个 字符赋值给字符串 int size(); int length(); char operator[](int n);// 通过 [] 方式取字符 , 下标越界不会抛出异常 char at(int n);// 通过 at 方法获取字符 , 下标越界会抛出异常 string str13 abcdefg ; char c1 str13 [ 2 ]; cout 获取单个字符 1: c1 endl ; char c2 str13 . at ( 5 ); cout 获取单个字符 2: c2 endl ; str13 [ 0 ] 1 ; cout str13 endl ; str13 . at ( 1 ) 2 ; cout str13 endl ; string operator(const string str);// 重载 操作符 string operator(const char* str);// 重载 操作符 string operator(const char c);// 重载 操作符 查找和替换 比较操作 string append(const char *s);// 把字符串 s 连接到当前字符串结尾 string append(const char *s, int n);// 把字符串 s 的前 n 个字符连接到当前字符 串结尾 string append(const string s);// 同 operator() string append(const string s, int pos, int n);// 把字符串 s 中从 pos 开始的 n 个字符连接到当前字符串结尾 string append(int n, char c);// 在当前字符串结尾添加 n 个字符 c int find(const string str, int pos 0) const; // 查找 str 第一次出现位置 , 从 pos 开始查找 int find(const char* s, int pos 0) const; // 查找 s 第一次出现位置 , 从 pos 开始查找 int find(const char* s, int pos, int n) const; // 从 pos 位置查找 s 的前 n 个字 符第一次位置 int find(const char c, int pos 0) const; // 查找字符 c 第一次出现位置 int rfind(const string str, int pos npos) const;// 查找 str 最后一次位 置 , 从 pos 开始查找 int rfind(const char* s, int pos npos) const;// 查找 s 最后一次出现位置 , 从 pos 开始查找 int rfind(const char* s, int pos, int n) const;// 从 pos 查找 s 的前 n 个字符最 后一次位置 int rfind(const char c, int pos 0) const; // 查找字符 c 最后一次出现位置 string replace(int pos, int n, const string str); // 替换从 pos 开始 n 个 字符为字符串 str string replace(int pos, int n, const char* s); // 替换从 pos 开始的 n 个字符 为字符串 s /** *compare 函数在 时返回 1 时返回 -1 时返回 0 。 * 比较区分大小写比较时参考字典顺序排越前面的越小。大写的 A 比小写的 a 小。 **/ int compare(const string s) const;// 与字符串 s 比较 int compare(const char *s) const;// 与字符串 s 比较 截取 插入和删除 string* 和 c-style 字符串转换 vector 特点 : 与数组的区别 api 构造函数 string substr(int pos 0, int n npos) const;// 返回由 pos 开始的 n 个字符 组成的字符串 string insert(int pos, const char* s); // 插入字符串 string insert(int pos, const string str); // 插入字符串 string insert(int pos, int n, char c);// 在指定位置插入 n 个字符 c string erase(int pos, int n npos);// 删除从 Pos 开始的 n 个字符 //string 转 char* string str itcast; const char* cstr str.c_str(); //char* 转 string char* s itcast; string str(s); 连续开辟 , 单向开口 , 随机访问迭代器 , 有容量 , 每次扩容是原来的 2 倍 底层数据结构 : 数组 vector 的结构类同于数组数组是静态的在定义时确定的数组的大小 而 vector 是动态的添加元素时如果空间不足时则会自动扩容器 2^n); 这被称为 vector 的未雨绸缪机制 整体来说 vector 比较灵活的而且 vector 是类模板可以存放任意类型的元素。 vectorT v; // 采用模板实现类实现默认构造函数 vector(v.begin(), v.end());// 将 v[begin(), end()) 区间中的元素拷贝给本 身。 vector(n, elem);// 构造函数将 n 个 elem 拷贝给本身。 vector(const vector vec);// 拷贝构造函数 迭代器 示例 赋值操作 本质就是 vector 中一个元素的指针 void fun01 () { // 创建一个空的 vector //vectorint vs; // 创建一个 vector 里面存储 5 个 10 //vectorint vs(5,10); int nums [ 5 ] { 1 , 3 , 5 , 7 , 9 }; // 将数组下标为 0~4 的 5 个元素存储到 vs 中 vector int vs ( nums , nums 5 ); // 获取 vs 中收个元素的地址赋值给其迭代器 vector int :: iterator it vs . begin (); // 判断迭代器是否已经移动到最后一位 while ( it ! vs . end ()) { // 获取迭代器指向的值 cout * it endl ; // 迭代器后移一位 it ; } cout -------------------- endl ; // 将 vs 的值赋值给 vs2 vector int vs2 ( vs ); vector int :: iterator it2 vs2 . begin (); while ( it2 ! vs2 . end ()) { cout * it2 endl ; it2 ; } } assign(beg, end);// 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign(n, elem);// 将 n 个 elem 拷贝赋值给本身。 vector operator(const vector vec);// 重载等号操作符 swap(vec);// 将 vec 与本身的元素互换 示例 插入与删除 示例 void fun02() { int nums[5] {1,3,5,7,9}; vectorint vs1(nums,nums5); vectorint vs2; //vs2.assign(vs1.begin(),vs1.end()); //vs2.assign(6,1); //vs2 vs1; vs2.swap(vs1); cout vs1 的内容 endl; vectorint::iterator it1 vs1.begin(); while (it1 ! vs1.end()) { cout *it1 endl; it1; } cout vs2 的内容 endl; vectorint::iterator it2 vs2.begin(); while (it2 ! vs2.end()) { cout *it2 endl; it2; } } push_back(ele); // 尾部插入元素 ele insert(const_iterator pos, int count, T ele); // 迭代器指向位置 pos 插入 count 个元素 ele. pop_back();// 删除最后一个元素 erase(const_iterator start, const_iterator end); // 删除迭代器从 start 到 end 之间的元素 , 删除 [start, end) 区间的所有元素 erase(const_iterator pos); // 删除迭代器指向的元素 clear(); // 删除容器中所有元素 void print_vector ( vector int v ) { vector int :: iterator it v . begin (); while ( it ! v . end ()) { cout * it \t ; it ; } cout endl ; 取值操作 示例 } void fun03 () { vector int vs ; // 尾部添加 vs . push_back ( 2 ); vs . push_back ( 4 ); vs . push_back ( 6 ); vs . push_back ( 8 ); vs . push_back ( 10 ); print_vector ( vs ); // 插入 vs . insert ( vs . begin (), 1 , 1 ); print_vector ( vs ); // 删除最后一个 vs . pop_back (); print_vector ( vs ); // 删除指定区间 , 包含开始位置 , 不包含结束位置 vs . erase ( vs . begin () 2 , vs . begin () 4 ); print_vector ( vs ); // 删除指定位置的元素 vs . erase ( vs . begin () 1 ); print_vector ( vs ); // 清空 vs . clear (); print_vector ( vs ); } at(int idx); // 返回索引 idx 所指的数据如果 idx 越界抛出 out_of_range 异常。 operator[](int idx); // 返回索引 idx 所指的数据越界时运行直接报错 front(); // 返回容器中第一个数据元素 back(); // 返回容器中最后一个数据元素 void fun04 () { vector int vs ; // 尾部添加 vs . push_back ( 2 ); vs . push_back ( 4 ); vs . push_back ( 6 ); vs . push_back ( 8 ); vs . push_back ( 10 ); 大小相关 示例 cout vs . at ( 1 ) endl ; cout vs [ 2 ] endl ; cout vs . front () endl ; cout vs . back () endl ; } int size(); // 返回容器中元素的个数 bool empty(); // 判断容器是否为空 返回 bool 值 0 1 void resize(int num); // 重新指定容器的长度为 num 若容器变长则以默认值填 充新位置。如果容器变短则末尾超出容器长度的元素被删除。 void resize(int num, elem); // 重新指定容器的长度为 num 若容器变长则以 elem 值填充新位置。如果容器变短则末尾超出容器长度的元素被删除。 int capacity(); // 容器的容量 void reserve(int len); // 容器预留 len 个元素长度 void fun05 () { vector int vs ; // 预留空间 //vs.reserve(10); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; cout 容量大小 vs . capacity () endl endl ; vs . resize ( 3 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; cout 容量大小 vs . capacity () endl endl ; vs . resize ( 5 , 10 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; cout 容量大小 vs . capacity () endl endl ; vs . reserve ( 3 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; 存放自定义对象 容器嵌套 cout 容量大小 vs . capacity () endl endl ; } #includestring class Person { friend void printVectorPerson ( vector Person v ); private : int num ; string name ; public : Person (){} Person ( int num , string name ) { this - num num ; this - name name ; } }; void printVectorPerson ( vector Person v ) { vector Person :: iterator it v . begin (); for (; it ! v . end (); it ) { //*itPerson cout ( * it ). num ( * it ). name endl ; //coutit-num it-nameendl; } } void fun06 () { vector Person v1 ; v1 . push_back ( Person ( 100 , lucy )); v1 . push_back ( Person ( 101 , bob )); v1 . push_back ( Person ( 102 , tom )); v1 . push_back ( Person ( 103 , 德玛 )); printVectorPerson ( v1 ); } void fun07 () { vector int v1 ; v1 . push_back ( 10 ); v1 . push_back ( 20 ); v1 . push_back ( 30 ); v1 . push_back ( 40 ); v1 . push_back ( 50 ); 小技巧 使用 swap 缩小空间 vector int v2 ; v2 . push_back ( 100 ); v2 . push_back ( 200 ); v2 . push_back ( 300 ); v2 . push_back ( 400 ); v2 . push_back ( 500 ); vector int v3 ; v3 . push_back ( 1000 ); v3 . push_back ( 2000 ); v3 . push_back ( 3000 ); v3 . push_back ( 4000 ); v3 . push_back ( 5000 ); vector vector int v ; v . push_back ( v1 ); v . push_back ( v2 ); v . push_back ( v3 ); vector vector int :: iterator it v . begin (); for (; it ! v . end (); it ) { //*it vectorint vector int :: iterator mit ( * it ). begin (); for (; mit ! ( * it ). end (); mit ) { //*mitint cout * mit ; } cout endl ; } } void fun08 () { // 收缩空间 vector int vs ; vs . push_back ( 1 ); vs . push_back ( 2 ); vs . push_back ( 3 ); vs . push_back ( 4 ); vs . push_back ( 5 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 容量大小 vs . capacity () endl endl ; deque 特点 与 vector 的区别 vector int ( vs ). swap ( vs ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 容量大小 vs . capacity () endl endl ; } deque 则是一种双向开口的连续线性空间。所谓的双向开口意思是可以在头尾两端分 别做元素的插入和删除操作 一在于 deque 允许使用常数项时间对头端进行元素的插入和删除操作。 二在于 deque 没有容量的概念因为它是动态的以分段连续空间组合而成随时可以 增加一段新的空间并链接起来 api 示例 题目 // 构造函数 deque T deqT ; // 默认构造形式 deque ( beg , end ); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。 deque ( n , elem ); // 构造函数将 n 个 elem 拷贝给本身。 deque ( const deque deq ); // 拷贝构造函数 // 赋值操作 assign ( beg , end ); // 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign ( n , elem ); // 将 n 个 elem 拷贝赋值给本身。 deque operator ( const deque deq ); // 重载等号操作符 swap ( deq ); // 将 deq 与本身的元素互换 // 大小操作 deque . size (); // 返回容器中元素的个数 deque . empty (); // 判断容器是否为空 deque . resize ( num ); // 重新指定容器的长度为 num, 若容器变长则以默认值填充新 位置。如果容器变短则末尾超出容器长度的元素被删除。 deque . resize ( num , elem ); // 重新指定容器的长度为 num, 若容器变长则以 elem 值填充新位置 , 如果容器变短则末尾超出容器长度的元素被删除。 // 双端插入和删除操作 push_back ( elem ); // 在容器尾部添加一个数据 push_front ( elem ); // 在容器头部插入一个数据 pop_back (); // 删除容器最后一个数据 pop_front (); // 删除容器第一个数据 // 数据存取 at ( idx ); // 返回索引 idx 所指的数据如果 idx 越界抛出 out_of_range 。 operator []; // 返回索引 idx 所指的数据如果 idx 越界不抛出异常直接出 错。 front (); // 返回第一个数据。 back (); // 返回最后一个数据 // 插入操作 insert ( pos , elem ); // 在 pos 位置插入一个 elem 元素的拷贝返回新数据的位置。 insert ( pos , n , elem ); // 在 pos 位置插入 n 个 elem 数据无返回值。 insert ( pos , beg , end ); // 在 pos 位置插入 [beg,end) 区间的数据无返回值。 // 删除操作 clear (); // 移除容器的所有数据 erase ( beg , end ); // 删除 [beg,end) 区间的数据返回下一个数据的位置。 erase ( pos ); // 删除 pos 位置的数据返回下一个数据的位置。 有 5 名选手选手 ABCDE 10 个评委分别对每一名选手打分去除最高分去除评 委中最低分取平均分。 1. 创建五名选手放到 vector 中 2. 遍历 vector 容器取出来每一个选手执行 for 循环可以把 10 个评分 打分存到 deque 容器中 3. sort 算法对 deque 容器中分数排序 pop_back pop_front 去除最高和最低 分 4. deque 容器遍历一遍累加分数累加分数 /d.size() 5. person.score 平均分 代码 #includeiostream using namespace std ; #includevector #includedeque #includectime #includestring #includecstdlib #includealgorithm class Person { friend void printInfo ( vector Person v ); friend void startGame ( vector Person v ); string name ; double score ; public : Person (){} Person ( string name , double score ) { this - name name ; this - score score ; } }; void createPerson ( vector Person v ) { string str ABCDE ; for ( int i 0 ; i str . size (); i ) { string name 选手 ; name str [ i ]; Person p ( name , 0 ); v . push_back ( p ); } } void printInfo ( vector Person v ) { vector Person :: iterator it v . begin (); while ( it ! v . end ()) { cout ( * it ). name \t ( * it ). score endl ; it ; } } void startGame ( vector Person v ) { srand ( time ( NULL )); vector Person :: iterator it v . begin (); while ( it ! v . end ()) { deque int scores ; for ( int i 0 ; i 10 ; i ) { int s rand () % 41 60 ; scores . push_back ( s ); } cout 开始给 ( * it ). name 打分 endl ; for ( int i 0 ; i scores . size (); i ) { cout 评委 i 给出的分数为 : scores [ i ] endl ; } // 排序 默认从小到大 sort ( scores . begin (), scores . end ()); // 从大到小 //sort(scores.begin(),scores.end(),greaterint()); // 去掉一个最低分 scores . pop_front (); // 去掉一个最高分 scores . pop_back (); // 计算总分 int score accumulate ( scores . begin (), scores . end (), 0 ); double s score * 1.0 / scores . size (); cout ( * it ). name 的平均分为 : s endl ; ( * it ). score s ; it ; } } int main ( int argc , char * argv []) { vector Person persons ; createPerson ( persons ); startGame ( persons ); printInfo ( persons ); return 0 ; } stack 特点 常用函数 示例 先进后出 , 单向开口 , 没有迭代器 构造函数 stackT stkT;//stack 采用模板类实现 stack 对象的默认构造形式 stack(const stack stk);// 拷贝构造函数 赋值操作 stack operator(const stack stk);// 重载等号操作符 数据存取操作 push(elem);// 向栈顶添加元素 pop();// 从栈顶移除第一个元素 top();// 返回栈顶元素 大小操作 empty();// 判断堆栈是否为空 size();// 返回堆栈的大小 #includestack void test01 () { stack int s1 ; s1 . push ( 10 ); s1 . push ( 20 ); queue 特点 常用函数 示例 s1 . push ( 30 ); s1 . push ( 40 ); s1 . push ( 50 ); cout 栈容器大小 : s1 . size () endl ; while ( ! s1 . empty ()) { cout s1 . top () ; s1 . pop (); // 出栈 } } 先进先出 , 双向开口 , 没有迭代器 队头 : 出数据 队尾 : 入数据 构造函数 queueT queT;//queue 采用模板类实现 queue 对象的默认构造形式 queue(const queue que);// 拷贝构造函数 存取、插入和删除操作 push(elem);// 往队尾添加元素 pop();// 从队头移除第一个元素 back();// 返回最后一个元素 front();// 返回第一个元素 赋值操作 queue operator(const queue que);// 重载等号操作符 大小操作 empty();// 判断队列是否为空 size();// 返回队列的大小 #include queue void test02 () { queue int q1 ; q1 . push ( 10 ); q1 . push ( 20 ); q1 . push ( 30 ); q1 . push ( 40 ); q1 . push ( 50 ); list 特点 常用函数 cout 队容器大小 : q1 . size () endl ; while ( ! q1 . empty ()) { cout q1 . front () ; q1 . pop (); // 出队 } } 双向链表 , 双向迭代器 , 元素可重复 注意 : 双向迭代器不支持 1, 或 2 等操作 构造函数 listT lstT;//list 采用采用模板类实现 , 对象的默认构造形式 list(beg,end);// 构造函数将 [beg, end) 区间中的元素拷贝给本身。 list(n,elem);// 构造函数将 n 个 elem 拷贝给本身。 list(const list lst);// 拷贝构造函数。 数据元素插入和删除操作 push_back(elem);// 在容器尾部加入一个元素 pop_back();// 删除容器中最后一个元素 push_front(elem);// 在容器开头插入一个元素 pop_front();// 从容器开头移除第一个元素 insert(pos,elem);// 在 pos 位置插 elem 元素的拷贝返回新数据的位置。 insert(pos,n,elem);// 在 pos 位置插入 n 个 elem 数据无返回值。 insert(pos,beg,end);// 在 pos 位置插入 [beg,end) 区间的数据无返回值。 clear();// 移除容器的所有数据 erase(beg,end);// 删除 [beg,end) 区间的数据返回下一个数据的位置。 erase(pos);// 删除 pos 位置的数据返回下一个数据的位置。 remove(elem);// 删除容器中所有与 elem 值匹配的元素。 大小操作 示例 size();// 返回容器中元素的个数 empty();// 判断容器是否为空 resize(num);// 重新指定容器的长度为 num 若容器变长则以默认值填充新位 置。如果容器变短则末尾超出容器长度的元素被删除。 resize(num, elem);// 重新指定容器的长度为 num, 若容器变长则以 elem 值 填充新位置。如果容器变短则末尾超出容器长度的元素被删除。 赋值操作 assign(beg, end);// 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign(n, elem);// 将 n 个 elem 拷贝赋值给本身。 list operator(const list lst);// 重载等号操作符 swap(lst);// 将 lst 与本身的元素互换。 数据的存取 front();// 返回第一个元素。 back();// 返回最后一个元素。 反转排序 reverse();// 反转链表比如 lst 包含 1,3,5 元素运行此方法后 lst 就包 含 5,3,1 元素。 sort(); //list 排序 #includelist #includealgorithm void printListInt ( list int l ) { list int :: iterator it l . begin (); for (; it ! l . end (); it ) { cout * it ; } cout endl ; } void test03 () { list int l1 ; l1 . push_back ( 10 ); l1 . push_back ( 20 ); l1 . push_back ( 30 ); l1 . push_front ( 40 ); l1 . push_front ( 50 ); l1 . push_front ( 60 ); //60 50 40 10 20 30 cout 大小 : l1 . size () endl ; printListInt ( l1 ); list int :: iterator it l1 . begin (); // 双向迭代器不支持 1 //it2;//err set/multiset set 特点 multiset 特点 常用函数 it ; it ; l1 . insert ( it , 3 , 100 ); printListInt ( l1 ); // 删除所有 100 数据 l1 . remove ( 100 ); printListInt ( l1 ); // 链表反转 l1 . reverse (); printListInt ( l1 ); // 链表排序 // 标准 STL 算法 不能操作双向迭代器 //sort(l1.begin(), l1.end());//err l1 . sort (); printListInt ( l1 ); } Set 的特性是。所有元素都会根据元素的键值自动被排序。 set 容器的键值和实值 是同一个值。 Set 不允许两个元素 有相同的键值。 Set 容器的迭代器 是只读迭代器。 插入数据后 不允许修改 set 的键值。 multiset 特性及用法和 set 完全相同唯一的差别在于它允许键值重复。 set 和 multiset 的底层实现是红黑树红黑树为平衡二叉树的一种。 构造函数 setT st;//set 默认构造函数 mulitsetT mst; //multiset 默认构造函数 : set(const set st);// 拷贝构造函数 赋值操作 set operator(const set st);// 重载等号操作符 swap(st);// 交换两个集合容器 大小操作 size();// 返回容器中元素的数目 empty();// 判断容器是否为空 插入和删除操作 示例 1, 基本使用 insert(elem);// 在容器中插入元素。 clear();// 清除所有元素 erase(pos);// 删除 pos 迭代器所指的元素返回下一个元素的迭代器。 erase(beg, end);// 删除区间 [beg,end) 的所有元素 返回下一个元素的迭代 器。 erase(elem);// 删除容器中值为 elem 的元素。 查找操作 find(key);// 查找键 key 是否存在 , 若存在返回该键的元素的迭代器若不存 在返回 set.end(); count(key);// 查找键 key 的元素个数 lower_bound(keyElem);// 下限返回第一个 keykeyElem 元素的迭代器。 upper_bound(keyElem);// 上限返回第一个 keykeyElem 元素的迭代器。 equal_range(keyElem);// 返回容器中 key 与 keyElem 相等的上下限的两个迭 代器。 void printSetInt ( set int s ) { set int :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout * it ; } cout endl ; } void test01 () { set int s1 ; s1 . insert ( 20 ); s1 . insert ( 50 ); s1 . insert ( 10 ); s1 . insert ( 40 ); s1 . insert ( 30 ); printSetInt ( s1 ); //count(key);// 查找键 key 的元素个数 ( 结果只能是 0 或 1) cout s1 . count ( 30 ) endl ; //find(key);// 查找键 key 是否存在 , 若存在返回该键的元素的迭代器若不存 在返回 set.end(); set int :: const_iterator ret ; ret s1 . find ( 20 ); if ( ret s1 . end ()) { cout 未找到 endl ; } else { cout 找到的数据为 : * ret endl ; } } 2,set 容器根据键值排序 #include set using namespace std ; void printSetInt ( set int s ) { set int :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout * it ; } cout endl ; } void test01 () { set int s1 ; s1 . insert ( 30 ); s1 . insert ( 20 ); s1 . insert ( 10 ); s1 . insert ( 50 ); s1 . insert ( 40 ); printSetInt ( s1 ); } 3, 修改 set 容器的排序规则 #include iostream #include set using namespace std ; class MyGreater { public : bool operator ()( int v1 , int v2 ) { return v1 v2 ; } }; void printSetInt ( set int , MyGreater s ) { set int , MyGreater :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout * it ; } cout endl ; } void test01 () { set int , MyGreater s1 ; s1 . insert ( 30 ); s1 . insert ( 20 ); s1 . insert ( 10 ); s1 . insert ( 50 ); s1 . insert ( 40 ); printSetInt ( s1 ); } int main ( int argc , char * argv []) { test01 (); return 0 ; } 4:set 容器存放自定义数据 必须实现排序规则 #includestring class Person ; class GreaterPerson { public : bool operator ()( Person ob1 , Person ob2 ); }; class Person { friend class GreaterPerson ; friend void printSetPerson ( set Person , GreaterPerson s ); private : int num ; string name ; public : Person (){} Person ( int num , string name ) { this - num num ; this - name name ; } }; void printSetPerson ( set Person , GreaterPerson s ) { set Person , GreaterPerson :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout ( * it ). num ( * it ). name endl ; } } void test02 () { set Person , GreaterPerson s1 ; s1 . insert ( Person ( 101 , lucy )); s1 . insert ( Person ( 103 , bob )); s1 . insert ( Person ( 102 , tom )); s1 . insert ( Person ( 105 , 小炮 )); s1 . insert ( Person ( 106 , 小法 )); printSetPerson ( s1 ); } int main ( int argc , char * argv []) { test02 (); return 0 ; } bool GreaterPerson::operator ()( Person ob1 , Person ob2 ) { return ob1 . num ob2 . num ; } 5,multiset 值可以重复 #includeset void test02 () { multiset int mset ; mset . insert ( 10 ); mset . insert ( 10 ); mset . insert ( 10 ); multiset int :: const_iterator it mset . begin (); while ( it ! mset . end ()) { cout * it endl ; it ; } } 6, 上下限 void test03 () { set int s1 ; s1 . insert ( 20 ); s1 . insert ( 50 ); map/multimap 前置知识 : 对组 示例 s1 . insert ( 10 ); s1 . insert ( 40 ); s1 . insert ( 30 ); printSetInt ( s1 ); // 寻找下限 set int :: const_iterator ret ; ret s1 . lower_bound ( 30 ); if ( ret ! s1 . end ()) { cout 下限值为 : * ret endl ; } // 寻找上限 ret s1 . upper_bound ( 30 ); if ( ret ! s1 . end ()) { cout 上限值为 : * ret endl ; } // 寻找上下限 ,pair 对组 , 本质是一个结构体 , 其中一个成员存放上限 , 一个成员存储下 限 pair set int :: const_iterator , set int :: const_iterator pr ; pr s1 . equal_range ( 30 ); if ( pr . first ! s1 . end ()) { cout 下限值为 : * ( pr . first ) endl ; } if ( pr . second ! s1 . end ()) { cout 上限值为 : * ( pr . second ) endl ; } } int main ( int argc , char * argv []) { test03 (); return 0 ; } 对组 (pair) 将一对值组合成一个值这一对值可以具有不同的数据类型两个值可以分 别用 pair 的两个公有属性 first 和 second 访问。 map 特点 示例 示例 1: 存储基本数据类型 示例 2: 存储自定义类型 pair int , string p1 ( 1 , 小翠 ); // 创建方式 1 pair int , string p2 make_pair ( 2 , 酸菜 ); // 创建方式 2 //first: 键值 //second: 实值 cout p1 . first p1 . second endl ; cout p2 . first p2 . second endl ; 所有元素都会根据元素的键值自动排序。 Map 所有的元素都是 pair, 同时拥有实值和键值 pair 的第一元素被视为键值第二 元素被视为实值。 map 容器的迭代器是只读迭代器。键值不允许修改不能重复。 void test01 () { map int , string m1 ; // 方式一 m1 . insert ( pair int , string ( 10086 , 移动 )); // 方式二 : 推荐 m1 . insert ( make_pair ( 10010 , 联通 )); // 方式三 m1 . insert ( map int , string :: value_type ( 10000 , 电信 )); // 方式四 : m1 [ 9527 ] 星爷 ; map int , string :: const_iterator it m1 . begin (); for (; it ! m1 . end (); it ) { //*it pairint,string cout 键值 : ( * it ). first 实值 : ( * it ). second endl ; } } class Person { friend void printMapIntPerson ( map int , Person m ); private : int num ; string name ; float score ; public : Person (){} Person ( int num , string name , float score ) multimap 特点 综合案例 { this - num num ; this - name name ; this - score score ; } }; void printMapIntPerson ( map int , Person m ) { map int , Person :: const_iterator it m . begin (); for (; it ! m . end (); it ) { //*it int,Person cout 学号 : ( * it ). first 姓名 : ( * it ). second . name 分数 : ( * it ). second . score endl ; } } void test02 () { map int , Person m ; m . insert ( make_pair ( 103 , Person ( 103 , lucy , 77.7f ))); m . insert ( make_pair ( 101 , Person ( 101 , bob , 77.7f ))); m . insert ( make_pair ( 104 , Person ( 104 , tom , 77.7f ))); m . insert ( make_pair ( 102 , Person ( 102 , 德玛 , 77.7f ))); printMapIntPerson ( m ); } 允许键值重复 #define SALE_DEPATMENT 1 // 销售部门 #define DEVELOP_DEPATMENT 2 // 研发部门 #define FINACIAL_DEPATMENT 3 // 财务部门 #include iostream #include map #include string #include vector #include time.h using namespace std ; class Person { friend void showPersonOfDepartment ( multimap int , Person m , int op ); friend void personJoinDepartment ( vector Person v , multimap int , Person m ); private : string name ; int age ; int money ; string tel ; public : Person (){} Person ( string name , int age , int money , string tel ) { this - name name ; this - age age ; this - money money ; this - tel tel ; } }; void createPerson ( vector Person v ) { // 设置随机数种子 srand ( time ( NULL )); int i 0 ; string tmpName ABCDE ; for ( i 0 ; i 5 ; i ) { string name 员工 ; name tmpName [ i ]; int age rand () % 5 16 ; int money rand () % 10000 20000 ; string tel to_string ( rand ()); v . push_back ( Person ( name , age , money , tel )); } } void personJoinDepartment ( vector Person v , multimap int , Person m ) { // 逐个员工加入部门 vector Person :: iterator it v . begin (); for (; it ! v . end (); it ) { //*itPerson cout 请输入 ( * it ). name 加入的部门 :1( 销售 ) 、 2( 研发 ) 、 3( 财 务 ): ; int op 0 ; cin op ; // 加入部门 m . insert ( make_pair ( op , * it )); } } void showPersonOfDepartment ( multimap int , Person m , int op ) { //1 1 2 2 3 // 寻找 key 的位置 multimap int , Person :: const_iterator ret ; ret m . find ( op ); if ( ret m . end ()) { cout 未找到相关部门员工信息 endl ; return ; } // 统计部门员工个数 int count m . count ( op ); // 显示部门员工信息 switch ( op ) { case 1 : cout ---------------- 销售部门 ------------------ endl ; break ; case 2 : cout ---------------- 研发部门 ------------------ endl ; break ; case 3 : cout ---------------- 财务部门 ------------------ endl ; break ; } int i 0 ; for ( i 0 ; i count ; i , ret ) { //(*ret) 部门 , 员工 cout \t ( * ret ). second . name ( * ret ). second . age \ ( * ret ). second . money ( * ret ). second . tel endl ; } } int main ( int argc , char * argv []) { multimap int , Person m ; // 创建 vector 存放员工 vector Person v ; createPerson ( v ); // 将 5 名员工加入部门 personJoinDepartment ( v , m ); // 显示部门员工 cout 请输入你要显示的部门 1( 销售 ) 、 2( 研发 ) 、 3( 财务 ): ; int op 0 ; cin op ; showPersonOfDepartment ( m , op ); return 0 ; } 总结 vector 单端动态数组 随机访问迭代器 比如软件历史操作记录的存储我们经常要查看历史记录比如上一次的记录上上次 的记录但却不会去删除记录因为记录是事实的描述。 数据结构 : 数组 deque 双端动态数组 随机访问迭代器 deque 的使用场景比如排队购票系统对排队者的存储可以采用 deque 支持头端 的快速移除尾端的快速添加 stack 栈容器 没有迭代器 先进后出 queue 队列容器 没有迭代器 先进先出 list 链表容器 双向迭代器 比如公交车乘客的存储随时可能有乘客下车支持频繁的不确实位置元素的移除插入 数据结构 : 双链表 set 容器 只有键值 键值不能重复 自动排序 只读迭代器 比如对手机游戏的个人得分记录的存储存储要求从高 分到低分的顺序排列。 数据结构 : 红黑树 map 容器 键值 - 实值成对出现 键值不能重复 自动排序 只读迭代器 比如按 ID 号存储十万个用户想要快速要通过 ID 查找对应的用户。 数据结构 :红黑树 C-STL01- 容器 引入 我们想存储多个学员的信息 , 现在学员数量不定 通过以前学习的知识 , 我们可以创建一个数组存储学员的信息 但是这个数组大小是多少呢 ? 过大会导致空间浪费 , 小了又需要扩容 对其中的数据进行操作也较为复杂 每次删除数据后还要对其进行回收等操作 这样我们在编写代码时将大量的时间在这种无关业务的事情上被浪费 为了我们能更好的关心业务操作 程序人员从函数 (functions) 类别 (classes), 函数库 (function libraries), 类别库 (classlibraries) 、各种组件从模块化设计到面向对象 (object oriented ) 进行设计 , 提供 了为了建立数据结构和算法的一套标准并且降低他们之间的耦合关系以提升各自的独 立性、弹性、交互操作性 ( 相互合作性 ,interoperability), 诞生了 STL 概述 STL(Standard Template Library, 标准模板库 ), 是惠普实验室开发的一系列软件的统称。 STL 六大组件 容器 : 作用 : 容纳存储数据 分类 : 序列式容器 强调值的排序每个元素均有固定的位置 除非用删除或插入的操作改 变这个位置 如 vector, deque/queue, list; 关联式容器 : 非线性更准确的说是二叉树结构各元素之间没有严格的物理上的顺 序关系 ; 在数据中选择一个关键字 key 这个 key 对数据起到索引的作用方便查 找。 如 Set/multiset Map/multimap 容器 注意 : 容器可以嵌套容器 算法 : 作用 : 操作数据 , 如插入数据、删除数据、修改数据、排序等 分类 : 质变算法是指运算过程中会更改区间内的元素的内容。例如拷贝替换删 除等等 优点 常用容器 string 作用 : 存储字符的容器 常用操作 构造函数 非质变算法是指运算过程中不会更改区间内的元素内容例如查找、计数、 遍历、寻找极值等等 迭代器 作用 : 容器与算法之间的粘合剂 注意 : 每个容器都有自己的迭代器 分类 : 输入迭代器 提供对数据的只读访问 只读支持 、 、 输出迭代器 提供对数据的只写访问 只写支持 前向迭代器 提供读写操作并能向前推进迭代器 读写支持 、 、 双向迭代器 提供读写操作并能向前和向后操作 读写支持 、 -- 随机访问迭代器 提供读写操作并能以跳跃的方式访问容器的任意数据是 功能最强的迭代器读写支持 、 -- [n] 、 - n 、 、 、 、 仿函数 作用 : 为算法提供策略 适配器 作用 : 为算法提供更多的参数接口 空间配置器 作用 : 为容器和算法管理空间 有高可重用性 高性能 高移植性 跨平台 string();// 创建一个空的字符串 例如 : string str; string(const string str);// 使用一个 string 对象初始化另一个 string 对象 string(const char* s);// 使用字符串 s 初始化 string(int n, char c);// 使用 n 个字符 c 初始化 v 基本赋值操作 获取字符串长度 存取字符操作 示例 拼接操作 string operator(const char* s);//char 类型字符串赋值给当前的字符串 string operator(const string s);// 把字符串 s 赋给当前的字符串 string operator(char c);// 字符赋值给当前的字符串 string assign(const char *s);// 把字符串 s 赋给当前的字符串 string assign(const char *s, int n);// 把字符串 s 的前 n 个字符赋给当前的字符 串 string assign(const string s);// 把字符串 s 赋给当前字符串 string assign(int n, char c);// 用 n 个字符 c 赋给当前字符串 string assign(const string s, int start, int n);// 将 s 从 start 开始 n 个 字符赋值给字符串 int size(); int length(); char operator[](int n);// 通过 [] 方式取字符 , 下标越界不会抛出异常 char at(int n);// 通过 at 方法获取字符 , 下标越界会抛出异常 string str13 abcdefg ; char c1 str13 [ 2 ]; cout 获取单个字符 1: c1 endl ; char c2 str13 . at ( 5 ); cout 获取单个字符 2: c2 endl ; str13 [ 0 ] 1 ; cout str13 endl ; str13 . at ( 1 ) 2 ; cout str13 endl ; string operator(const string str);// 重载 操作符 string operator(const char* str);// 重载 操作符 string operator(const char c);// 重载 操作符 查找和替换 比较操作 string append(const char *s);// 把字符串 s 连接到当前字符串结尾 string append(const char *s, int n);// 把字符串 s 的前 n 个字符连接到当前字符 串结尾 string append(const string s);// 同 operator() string append(const string s, int pos, int n);// 把字符串 s 中从 pos 开始的 n 个字符连接到当前字符串结尾 string append(int n, char c);// 在当前字符串结尾添加 n 个字符 c int find(const string str, int pos 0) const; // 查找 str 第一次出现位置 , 从 pos 开始查找 int find(const char* s, int pos 0) const; // 查找 s 第一次出现位置 , 从 pos 开始查找 int find(const char* s, int pos, int n) const; // 从 pos 位置查找 s 的前 n 个字 符第一次位置 int find(const char c, int pos 0) const; // 查找字符 c 第一次出现位置 int rfind(const string str, int pos npos) const;// 查找 str 最后一次位 置 , 从 pos 开始查找 int rfind(const char* s, int pos npos) const;// 查找 s 最后一次出现位置 , 从 pos 开始查找 int rfind(const char* s, int pos, int n) const;// 从 pos 查找 s 的前 n 个字符最 后一次位置 int rfind(const char c, int pos 0) const; // 查找字符 c 最后一次出现位置 string replace(int pos, int n, const string str); // 替换从 pos 开始 n 个 字符为字符串 str string replace(int pos, int n, const char* s); // 替换从 pos 开始的 n 个字符 为字符串 s /** *compare 函数在 时返回 1 时返回 -1 时返回 0 。 * 比较区分大小写比较时参考字典顺序排越前面的越小。大写的 A 比小写的 a 小。 **/ int compare(const string s) const;// 与字符串 s 比较 int compare(const char *s) const;// 与字符串 s 比较 截取 插入和删除 string* 和 c-style 字符串转换 vector 特点 : 与数组的区别 api 构造函数 string substr(int pos 0, int n npos) const;// 返回由 pos 开始的 n 个字符 组成的字符串 string insert(int pos, const char* s); // 插入字符串 string insert(int pos, const string str); // 插入字符串 string insert(int pos, int n, char c);// 在指定位置插入 n 个字符 c string erase(int pos, int n npos);// 删除从 Pos 开始的 n 个字符 //string 转 char* string str itcast; const char* cstr str.c_str(); //char* 转 string char* s itcast; string str(s); 连续开辟 , 单向开口 , 随机访问迭代器 , 有容量 , 每次扩容是原来的 2 倍 底层数据结构 : 数组 vector 的结构类同于数组数组是静态的在定义时确定的数组的大小 而 vector 是动态的添加元素时如果空间不足时则会自动扩容器 2^n); 这被称为 vector 的未雨绸缪机制 整体来说 vector 比较灵活的而且 vector 是类模板可以存放任意类型的元素。 vectorT v; // 采用模板实现类实现默认构造函数 vector(v.begin(), v.end());// 将 v[begin(), end()) 区间中的元素拷贝给本 身。 vector(n, elem);// 构造函数将 n 个 elem 拷贝给本身。 vector(const vector vec);// 拷贝构造函数 迭代器 示例 赋值操作 本质就是 vector 中一个元素的指针 void fun01 () { // 创建一个空的 vector //vectorint vs; // 创建一个 vector 里面存储 5 个 10 //vectorint vs(5,10); int nums [ 5 ] { 1 , 3 , 5 , 7 , 9 }; // 将数组下标为 0~4 的 5 个元素存储到 vs 中 vector int vs ( nums , nums 5 ); // 获取 vs 中收个元素的地址赋值给其迭代器 vector int :: iterator it vs . begin (); // 判断迭代器是否已经移动到最后一位 while ( it ! vs . end ()) { // 获取迭代器指向的值 cout * it endl ; // 迭代器后移一位 it ; } cout -------------------- endl ; // 将 vs 的值赋值给 vs2 vector int vs2 ( vs ); vector int :: iterator it2 vs2 . begin (); while ( it2 ! vs2 . end ()) { cout * it2 endl ; it2 ; } } assign(beg, end);// 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign(n, elem);// 将 n 个 elem 拷贝赋值给本身。 vector operator(const vector vec);// 重载等号操作符 swap(vec);// 将 vec 与本身的元素互换 示例 插入与删除 示例 void fun02() { int nums[5] {1,3,5,7,9}; vectorint vs1(nums,nums5); vectorint vs2; //vs2.assign(vs1.begin(),vs1.end()); //vs2.assign(6,1); //vs2 vs1; vs2.swap(vs1); cout vs1 的内容 endl; vectorint::iterator it1 vs1.begin(); while (it1 ! vs1.end()) { cout *it1 endl; it1; } cout vs2 的内容 endl; vectorint::iterator it2 vs2.begin(); while (it2 ! vs2.end()) { cout *it2 endl; it2; } } push_back(ele); // 尾部插入元素 ele insert(const_iterator pos, int count, T ele); // 迭代器指向位置 pos 插入 count 个元素 ele. pop_back();// 删除最后一个元素 erase(const_iterator start, const_iterator end); // 删除迭代器从 start 到 end 之间的元素 , 删除 [start, end) 区间的所有元素 erase(const_iterator pos); // 删除迭代器指向的元素 clear(); // 删除容器中所有元素 void print_vector ( vector int v ) { vector int :: iterator it v . begin (); while ( it ! v . end ()) { cout * it \t ; it ; } cout endl ; 取值操作 示例 } void fun03 () { vector int vs ; // 尾部添加 vs . push_back ( 2 ); vs . push_back ( 4 ); vs . push_back ( 6 ); vs . push_back ( 8 ); vs . push_back ( 10 ); print_vector ( vs ); // 插入 vs . insert ( vs . begin (), 1 , 1 ); print_vector ( vs ); // 删除最后一个 vs . pop_back (); print_vector ( vs ); // 删除指定区间 , 包含开始位置 , 不包含结束位置 vs . erase ( vs . begin () 2 , vs . begin () 4 ); print_vector ( vs ); // 删除指定位置的元素 vs . erase ( vs . begin () 1 ); print_vector ( vs ); // 清空 vs . clear (); print_vector ( vs ); } at(int idx); // 返回索引 idx 所指的数据如果 idx 越界抛出 out_of_range 异常。 operator[](int idx); // 返回索引 idx 所指的数据越界时运行直接报错 front(); // 返回容器中第一个数据元素 back(); // 返回容器中最后一个数据元素 void fun04 () { vector int vs ; // 尾部添加 vs . push_back ( 2 ); vs . push_back ( 4 ); vs . push_back ( 6 ); vs . push_back ( 8 ); vs . push_back ( 10 ); 大小相关 示例 cout vs . at ( 1 ) endl ; cout vs [ 2 ] endl ; cout vs . front () endl ; cout vs . back () endl ; } int size(); // 返回容器中元素的个数 bool empty(); // 判断容器是否为空 返回 bool 值 0 1 void resize(int num); // 重新指定容器的长度为 num 若容器变长则以默认值填 充新位置。如果容器变短则末尾超出容器长度的元素被删除。 void resize(int num, elem); // 重新指定容器的长度为 num 若容器变长则以 elem 值填充新位置。如果容器变短则末尾超出容器长度的元素被删除。 int capacity(); // 容器的容量 void reserve(int len); // 容器预留 len 个元素长度 void fun05 () { vector int vs ; // 预留空间 //vs.reserve(10); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; cout 容量大小 vs . capacity () endl endl ; vs . resize ( 3 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; cout 容量大小 vs . capacity () endl endl ; vs . resize ( 5 , 10 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; cout 容量大小 vs . capacity () endl endl ; vs . reserve ( 3 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 是否为空 vs . empty () endl ; 存放自定义对象 容器嵌套 cout 容量大小 vs . capacity () endl endl ; } #includestring class Person { friend void printVectorPerson ( vector Person v ); private : int num ; string name ; public : Person (){} Person ( int num , string name ) { this - num num ; this - name name ; } }; void printVectorPerson ( vector Person v ) { vector Person :: iterator it v . begin (); for (; it ! v . end (); it ) { //*itPerson cout ( * it ). num ( * it ). name endl ; //coutit-num it-nameendl; } } void fun06 () { vector Person v1 ; v1 . push_back ( Person ( 100 , lucy )); v1 . push_back ( Person ( 101 , bob )); v1 . push_back ( Person ( 102 , tom )); v1 . push_back ( Person ( 103 , 德玛 )); printVectorPerson ( v1 ); } void fun07 () { vector int v1 ; v1 . push_back ( 10 ); v1 . push_back ( 20 ); v1 . push_back ( 30 ); v1 . push_back ( 40 ); v1 . push_back ( 50 ); 小技巧 使用 swap 缩小空间 vector int v2 ; v2 . push_back ( 100 ); v2 . push_back ( 200 ); v2 . push_back ( 300 ); v2 . push_back ( 400 ); v2 . push_back ( 500 ); vector int v3 ; v3 . push_back ( 1000 ); v3 . push_back ( 2000 ); v3 . push_back ( 3000 ); v3 . push_back ( 4000 ); v3 . push_back ( 5000 ); vector vector int v ; v . push_back ( v1 ); v . push_back ( v2 ); v . push_back ( v3 ); vector vector int :: iterator it v . begin (); for (; it ! v . end (); it ) { //*it vectorint vector int :: iterator mit ( * it ). begin (); for (; mit ! ( * it ). end (); mit ) { //*mitint cout * mit ; } cout endl ; } } void fun08 () { // 收缩空间 vector int vs ; vs . push_back ( 1 ); vs . push_back ( 2 ); vs . push_back ( 3 ); vs . push_back ( 4 ); vs . push_back ( 5 ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 容量大小 vs . capacity () endl endl ; deque 特点 与 vector 的区别 vector int ( vs ). swap ( vs ); print_vector ( vs ); cout 元素个数 vs . size () endl ; cout 容量大小 vs . capacity () endl endl ; } deque 则是一种双向开口的连续线性空间。所谓的双向开口意思是可以在头尾两端分 别做元素的插入和删除操作 一在于 deque 允许使用常数项时间对头端进行元素的插入和删除操作。 二在于 deque 没有容量的概念因为它是动态的以分段连续空间组合而成随时可以 增加一段新的空间并链接起来 api 示例 题目 // 构造函数 deque T deqT ; // 默认构造形式 deque ( beg , end ); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。 deque ( n , elem ); // 构造函数将 n 个 elem 拷贝给本身。 deque ( const deque deq ); // 拷贝构造函数 // 赋值操作 assign ( beg , end ); // 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign ( n , elem ); // 将 n 个 elem 拷贝赋值给本身。 deque operator ( const deque deq ); // 重载等号操作符 swap ( deq ); // 将 deq 与本身的元素互换 // 大小操作 deque . size (); // 返回容器中元素的个数 deque . empty (); // 判断容器是否为空 deque . resize ( num ); // 重新指定容器的长度为 num, 若容器变长则以默认值填充新 位置。如果容器变短则末尾超出容器长度的元素被删除。 deque . resize ( num , elem ); // 重新指定容器的长度为 num, 若容器变长则以 elem 值填充新位置 , 如果容器变短则末尾超出容器长度的元素被删除。 // 双端插入和删除操作 push_back ( elem ); // 在容器尾部添加一个数据 push_front ( elem ); // 在容器头部插入一个数据 pop_back (); // 删除容器最后一个数据 pop_front (); // 删除容器第一个数据 // 数据存取 at ( idx ); // 返回索引 idx 所指的数据如果 idx 越界抛出 out_of_range 。 operator []; // 返回索引 idx 所指的数据如果 idx 越界不抛出异常直接出 错。 front (); // 返回第一个数据。 back (); // 返回最后一个数据 // 插入操作 insert ( pos , elem ); // 在 pos 位置插入一个 elem 元素的拷贝返回新数据的位置。 insert ( pos , n , elem ); // 在 pos 位置插入 n 个 elem 数据无返回值。 insert ( pos , beg , end ); // 在 pos 位置插入 [beg,end) 区间的数据无返回值。 // 删除操作 clear (); // 移除容器的所有数据 erase ( beg , end ); // 删除 [beg,end) 区间的数据返回下一个数据的位置。 erase ( pos ); // 删除 pos 位置的数据返回下一个数据的位置。 有 5 名选手选手 ABCDE 10 个评委分别对每一名选手打分去除最高分去除评 委中最低分取平均分。 1. 创建五名选手放到 vector 中 2. 遍历 vector 容器取出来每一个选手执行 for 循环可以把 10 个评分 打分存到 deque 容器中 3. sort 算法对 deque 容器中分数排序 pop_back pop_front 去除最高和最低 分 4. deque 容器遍历一遍累加分数累加分数 /d.size() 5. person.score 平均分 代码 #includeiostream using namespace std ; #includevector #includedeque #includectime #includestring #includecstdlib #includealgorithm class Person { friend void printInfo ( vector Person v ); friend void startGame ( vector Person v ); string name ; double score ; public : Person (){} Person ( string name , double score ) { this - name name ; this - score score ; } }; void createPerson ( vector Person v ) { string str ABCDE ; for ( int i 0 ; i str . size (); i ) { string name 选手 ; name str [ i ]; Person p ( name , 0 ); v . push_back ( p ); } } void printInfo ( vector Person v ) { vector Person :: iterator it v . begin (); while ( it ! v . end ()) { cout ( * it ). name \t ( * it ). score endl ; it ; } } void startGame ( vector Person v ) { srand ( time ( NULL )); vector Person :: iterator it v . begin (); while ( it ! v . end ()) { deque int scores ; for ( int i 0 ; i 10 ; i ) { int s rand () % 41 60 ; scores . push_back ( s ); } cout 开始给 ( * it ). name 打分 endl ; for ( int i 0 ; i scores . size (); i ) { cout 评委 i 给出的分数为 : scores [ i ] endl ; } // 排序 默认从小到大 sort ( scores . begin (), scores . end ()); // 从大到小 //sort(scores.begin(),scores.end(),greaterint()); // 去掉一个最低分 scores . pop_front (); // 去掉一个最高分 scores . pop_back (); // 计算总分 int score accumulate ( scores . begin (), scores . end (), 0 ); double s score * 1.0 / scores . size (); cout ( * it ). name 的平均分为 : s endl ; ( * it ). score s ; it ; } } int main ( int argc , char * argv []) { vector Person persons ; createPerson ( persons ); startGame ( persons ); printInfo ( persons ); return 0 ; } stack 特点 常用函数 示例 先进后出 , 单向开口 , 没有迭代器 构造函数 stackT stkT;//stack 采用模板类实现 stack 对象的默认构造形式 stack(const stack stk);// 拷贝构造函数 赋值操作 stack operator(const stack stk);// 重载等号操作符 数据存取操作 push(elem);// 向栈顶添加元素 pop();// 从栈顶移除第一个元素 top();// 返回栈顶元素 大小操作 empty();// 判断堆栈是否为空 size();// 返回堆栈的大小 #includestack void test01 () { stack int s1 ; s1 . push ( 10 ); s1 . push ( 20 ); queue 特点 常用函数 示例 s1 . push ( 30 ); s1 . push ( 40 ); s1 . push ( 50 ); cout 栈容器大小 : s1 . size () endl ; while ( ! s1 . empty ()) { cout s1 . top () ; s1 . pop (); // 出栈 } } 先进先出 , 双向开口 , 没有迭代器 队头 : 出数据 队尾 : 入数据 构造函数 queueT queT;//queue 采用模板类实现 queue 对象的默认构造形式 queue(const queue que);// 拷贝构造函数 存取、插入和删除操作 push(elem);// 往队尾添加元素 pop();// 从队头移除第一个元素 back();// 返回最后一个元素 front();// 返回第一个元素 赋值操作 queue operator(const queue que);// 重载等号操作符 大小操作 empty();// 判断队列是否为空 size();// 返回队列的大小 #include queue void test02 () { queue int q1 ; q1 . push ( 10 ); q1 . push ( 20 ); q1 . push ( 30 ); q1 . push ( 40 ); q1 . push ( 50 ); list 特点 常用函数 cout 队容器大小 : q1 . size () endl ; while ( ! q1 . empty ()) { cout q1 . front () ; q1 . pop (); // 出队 } } 双向链表 , 双向迭代器 , 元素可重复 注意 : 双向迭代器不支持 1, 或 2 等操作 构造函数 listT lstT;//list 采用采用模板类实现 , 对象的默认构造形式 list(beg,end);// 构造函数将 [beg, end) 区间中的元素拷贝给本身。 list(n,elem);// 构造函数将 n 个 elem 拷贝给本身。 list(const list lst);// 拷贝构造函数。 数据元素插入和删除操作 push_back(elem);// 在容器尾部加入一个元素 pop_back();// 删除容器中最后一个元素 push_front(elem);// 在容器开头插入一个元素 pop_front();// 从容器开头移除第一个元素 insert(pos,elem);// 在 pos 位置插 elem 元素的拷贝返回新数据的位置。 insert(pos,n,elem);// 在 pos 位置插入 n 个 elem 数据无返回值。 insert(pos,beg,end);// 在 pos 位置插入 [beg,end) 区间的数据无返回值。 clear();// 移除容器的所有数据 erase(beg,end);// 删除 [beg,end) 区间的数据返回下一个数据的位置。 erase(pos);// 删除 pos 位置的数据返回下一个数据的位置。 remove(elem);// 删除容器中所有与 elem 值匹配的元素。 大小操作 示例 size();// 返回容器中元素的个数 empty();// 判断容器是否为空 resize(num);// 重新指定容器的长度为 num 若容器变长则以默认值填充新位 置。如果容器变短则末尾超出容器长度的元素被删除。 resize(num, elem);// 重新指定容器的长度为 num, 若容器变长则以 elem 值 填充新位置。如果容器变短则末尾超出容器长度的元素被删除。 赋值操作 assign(beg, end);// 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign(n, elem);// 将 n 个 elem 拷贝赋值给本身。 list operator(const list lst);// 重载等号操作符 swap(lst);// 将 lst 与本身的元素互换。 数据的存取 front();// 返回第一个元素。 back();// 返回最后一个元素。 反转排序 reverse();// 反转链表比如 lst 包含 1,3,5 元素运行此方法后 lst 就包 含 5,3,1 元素。 sort(); //list 排序 #includelist #includealgorithm void printListInt ( list int l ) { list int :: iterator it l . begin (); for (; it ! l . end (); it ) { cout * it ; } cout endl ; } void test03 () { list int l1 ; l1 . push_back ( 10 ); l1 . push_back ( 20 ); l1 . push_back ( 30 ); l1 . push_front ( 40 ); l1 . push_front ( 50 ); l1 . push_front ( 60 ); //60 50 40 10 20 30 cout 大小 : l1 . size () endl ; printListInt ( l1 ); list int :: iterator it l1 . begin (); // 双向迭代器不支持 1 //it2;//err set/multiset set 特点 multiset 特点 常用函数 it ; it ; l1 . insert ( it , 3 , 100 ); printListInt ( l1 ); // 删除所有 100 数据 l1 . remove ( 100 ); printListInt ( l1 ); // 链表反转 l1 . reverse (); printListInt ( l1 ); // 链表排序 // 标准 STL 算法 不能操作双向迭代器 //sort(l1.begin(), l1.end());//err l1 . sort (); printListInt ( l1 ); } Set 的特性是。所有元素都会根据元素的键值自动被排序。 set 容器的键值和实值 是同一个值。 Set 不允许两个元素 有相同的键值。 Set 容器的迭代器 是只读迭代器。 插入数据后 不允许修改 set 的键值。 multiset 特性及用法和 set 完全相同唯一的差别在于它允许键值重复。 set 和 multiset 的底层实现是红黑树红黑树为平衡二叉树的一种。 构造函数 setT st;//set 默认构造函数 mulitsetT mst; //multiset 默认构造函数 : set(const set st);// 拷贝构造函数 赋值操作 set operator(const set st);// 重载等号操作符 swap(st);// 交换两个集合容器 大小操作 size();// 返回容器中元素的数目 empty();// 判断容器是否为空 插入和删除操作 示例 1, 基本使用 insert(elem);// 在容器中插入元素。 clear();// 清除所有元素 erase(pos);// 删除 pos 迭代器所指的元素返回下一个元素的迭代器。 erase(beg, end);// 删除区间 [beg,end) 的所有元素 返回下一个元素的迭代 器。 erase(elem);// 删除容器中值为 elem 的元素。 查找操作 find(key);// 查找键 key 是否存在 , 若存在返回该键的元素的迭代器若不存 在返回 set.end(); count(key);// 查找键 key 的元素个数 lower_bound(keyElem);// 下限返回第一个 keykeyElem 元素的迭代器。 upper_bound(keyElem);// 上限返回第一个 keykeyElem 元素的迭代器。 equal_range(keyElem);// 返回容器中 key 与 keyElem 相等的上下限的两个迭 代器。 void printSetInt ( set int s ) { set int :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout * it ; } cout endl ; } void test01 () { set int s1 ; s1 . insert ( 20 ); s1 . insert ( 50 ); s1 . insert ( 10 ); s1 . insert ( 40 ); s1 . insert ( 30 ); printSetInt ( s1 ); //count(key);// 查找键 key 的元素个数 ( 结果只能是 0 或 1) cout s1 . count ( 30 ) endl ; //find(key);// 查找键 key 是否存在 , 若存在返回该键的元素的迭代器若不存 在返回 set.end(); set int :: const_iterator ret ; ret s1 . find ( 20 ); if ( ret s1 . end ()) { cout 未找到 endl ; } else { cout 找到的数据为 : * ret endl ; } } 2,set 容器根据键值排序 #include set using namespace std ; void printSetInt ( set int s ) { set int :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout * it ; } cout endl ; } void test01 () { set int s1 ; s1 . insert ( 30 ); s1 . insert ( 20 ); s1 . insert ( 10 ); s1 . insert ( 50 ); s1 . insert ( 40 ); printSetInt ( s1 ); } 3, 修改 set 容器的排序规则 #include iostream #include set using namespace std ; class MyGreater { public : bool operator ()( int v1 , int v2 ) { return v1 v2 ; } }; void printSetInt ( set int , MyGreater s ) { set int , MyGreater :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout * it ; } cout endl ; } void test01 () { set int , MyGreater s1 ; s1 . insert ( 30 ); s1 . insert ( 20 ); s1 . insert ( 10 ); s1 . insert ( 50 ); s1 . insert ( 40 ); printSetInt ( s1 ); } int main ( int argc , char * argv []) { test01 (); return 0 ; } 4:set 容器存放自定义数据 必须实现排序规则 #includestring class Person ; class GreaterPerson { public : bool operator ()( Person ob1 , Person ob2 ); }; class Person { friend class GreaterPerson ; friend void printSetPerson ( set Person , GreaterPerson s ); private : int num ; string name ; public : Person (){} Person ( int num , string name ) { this - num num ; this - name name ; } }; void printSetPerson ( set Person , GreaterPerson s ) { set Person , GreaterPerson :: const_iterator it s . begin (); for (; it ! s . end (); it ) { cout ( * it ). num ( * it ). name endl ; } } void test02 () { set Person , GreaterPerson s1 ; s1 . insert ( Person ( 101 , lucy )); s1 . insert ( Person ( 103 , bob )); s1 . insert ( Person ( 102 , tom )); s1 . insert ( Person ( 105 , 小炮 )); s1 . insert ( Person ( 106 , 小法 )); printSetPerson ( s1 ); } int main ( int argc , char * argv []) { test02 (); return 0 ; } bool GreaterPerson::operator ()( Person ob1 , Person ob2 ) { return ob1 . num ob2 . num ; } 5,multiset 值可以重复 #includeset void test02 () { multiset int mset ; mset . insert ( 10 ); mset . insert ( 10 ); mset . insert ( 10 ); multiset int :: const_iterator it mset . begin (); while ( it ! mset . end ()) { cout * it endl ; it ; } } 6, 上下限 void test03 () { set int s1 ; s1 . insert ( 20 ); s1 . insert ( 50 ); map/multimap 前置知识 : 对组 示例 s1 . insert ( 10 ); s1 . insert ( 40 ); s1 . insert ( 30 ); printSetInt ( s1 ); // 寻找下限 set int :: const_iterator ret ; ret s1 . lower_bound ( 30 ); if ( ret ! s1 . end ()) { cout 下限值为 : * ret endl ; } // 寻找上限 ret s1 . upper_bound ( 30 ); if ( ret ! s1 . end ()) { cout 上限值为 : * ret endl ; } // 寻找上下限 ,pair 对组 , 本质是一个结构体 , 其中一个成员存放上限 , 一个成员存储下 限 pair set int :: const_iterator , set int :: const_iterator pr ; pr s1 . equal_range ( 30 ); if ( pr . first ! s1 . end ()) { cout 下限值为 : * ( pr . first ) endl ; } if ( pr . second ! s1 . end ()) { cout 上限值为 : * ( pr . second ) endl ; } } int main ( int argc , char * argv []) { test03 (); return 0 ; } 对组 (pair) 将一对值组合成一个值这一对值可以具有不同的数据类型两个值可以分 别用 pair 的两个公有属性 first 和 second 访问。 map 特点 示例 示例 1: 存储基本数据类型 示例 2: 存储自定义类型 pair int , string p1 ( 1 , 小翠 ); // 创建方式 1 pair int , string p2 make_pair ( 2 , 酸菜 ); // 创建方式 2 //first: 键值 //second: 实值 cout p1 . first p1 . second endl ; cout p2 . first p2 . second endl ; 所有元素都会根据元素的键值自动排序。 Map 所有的元素都是 pair, 同时拥有实值和键值 pair 的第一元素被视为键值第二 元素被视为实值。 map 容器的迭代器是只读迭代器。键值不允许修改不能重复。 void test01 () { map int , string m1 ; // 方式一 m1 . insert ( pair int , string ( 10086 , 移动 )); // 方式二 : 推荐 m1 . insert ( make_pair ( 10010 , 联通 )); // 方式三 m1 . insert ( map int , string :: value_type ( 10000 , 电信 )); // 方式四 : m1 [ 9527 ] 星爷 ; map int , string :: const_iterator it m1 . begin (); for (; it ! m1 . end (); it ) { //*it pairint,string cout 键值 : ( * it ). first 实值 : ( * it ). second endl ; } } class Person { friend void printMapIntPerson ( map int , Person m ); private : int num ; string name ; float score ; public : Person (){} Person ( int num , string name , float score ) multimap 特点 综合案例 { this - num num ; this - name name ; this - score score ; } }; void printMapIntPerson ( map int , Person m ) { map int , Person :: const_iterator it m . begin (); for (; it ! m . end (); it ) { //*it int,Person cout 学号 : ( * it ). first 姓名 : ( * it ). second . name 分数 : ( * it ). second . score endl ; } } void test02 () { map int , Person m ; m . insert ( make_pair ( 103 , Person ( 103 , lucy , 77.7f ))); m . insert ( make_pair ( 101 , Person ( 101 , bob , 77.7f ))); m . insert ( make_pair ( 104 , Person ( 104 , tom , 77.7f ))); m . insert ( make_pair ( 102 , Person ( 102 , 德玛 , 77.7f ))); printMapIntPerson ( m ); } 允许键值重复 #define SALE_DEPATMENT 1 // 销售部门 #define DEVELOP_DEPATMENT 2 // 研发部门 #define FINACIAL_DEPATMENT 3 // 财务部门 #include iostream #include map #include string #include vector #include time.h using namespace std ; class Person { friend void showPersonOfDepartment ( multimap int , Person m , int op ); friend void personJoinDepartment ( vector Person v , multimap int , Person m ); private : string name ; int age ; int money ; string tel ; public : Person (){} Person ( string name , int age , int money , string tel ) { this - name name ; this - age age ; this - money money ; this - tel tel ; } }; void createPerson ( vector Person v ) { // 设置随机数种子 srand ( time ( NULL )); int i 0 ; string tmpName ABCDE ; for ( i 0 ; i 5 ; i ) { string name 员工 ; name tmpName [ i ]; int age rand () % 5 16 ; int money rand () % 10000 20000 ; string tel to_string ( rand ()); v . push_back ( Person ( name , age , money , tel )); } } void personJoinDepartment ( vector Person v , multimap int , Person m ) { // 逐个员工加入部门 vector Person :: iterator it v . begin (); for (; it ! v . end (); it ) { //*itPerson cout 请输入 ( * it ). name 加入的部门 :1( 销售 ) 、 2( 研发 ) 、 3( 财 务 ): ; int op 0 ; cin op ; // 加入部门 m . insert ( make_pair ( op , * it )); } } void showPersonOfDepartment ( multimap int , Person m , int op ) { //1 1 2 2 3 // 寻找 key 的位置 multimap int , Person :: const_iterator ret ; ret m . find ( op ); if ( ret m . end ()) { cout 未找到相关部门员工信息 endl ; return ; } // 统计部门员工个数 int count m . count ( op ); // 显示部门员工信息 switch ( op ) { case 1 : cout ---------------- 销售部门 ------------------ endl ; break ; case 2 : cout ---------------- 研发部门 ------------------ endl ; break ; case 3 : cout ---------------- 财务部门 ------------------ endl ; break ; } int i 0 ; for ( i 0 ; i count ; i , ret ) { //(*ret) 部门 , 员工 cout \t ( * ret ). second . name ( * ret ). second . age \ ( * ret ). second . money ( * ret ). second . tel endl ; } } int main ( int argc , char * argv []) { multimap int , Person m ; // 创建 vector 存放员工 vector Person v ; createPerson ( v ); // 将 5 名员工加入部门 personJoinDepartment ( v , m ); // 显示部门员工 cout 请输入你要显示的部门 1( 销售 ) 、 2( 研发 ) 、 3( 财务 ): ; int op 0 ; cin op ; showPersonOfDepartment ( m , op ); return 0 ; } 总结 vector 单端动态数组 随机访问迭代器 比如软件历史操作记录的存储我们经常要查看历史记录比如上一次的记录上上次 的记录但却不会去删除记录因为记录是事实的描述。 数据结构 : 数组 deque 双端动态数组 随机访问迭代器 deque 的使用场景比如排队购票系统对排队者的存储可以采用 deque 支持头端 的快速移除尾端的快速添加 stack 栈容器 没有迭代器 先进后出 queue 队列容器 没有迭代器 先进先出 list 链表容器 双向迭代器 比如公交车乘客的存储随时可能有乘客下车支持频繁的不确实位置元素的移除插入 数据结构 : 双链表 set 容器 只有键值 键值不能重复 自动排序 只读迭代器 比如对手机游戏的个人得分记录的存储存储要求从高 分到低分的顺序排列。 数据结构 : 红黑树 map 容器 键值 - 实值成对出现 键值不能重复 自动排序 只读迭代器 比如按 ID 号存储十万个用户想要快速要通过 ID 查找对应的用户。 数据结构 : 红黑树
