C++ STL之容器介绍（vector、list、set、map）

1 STL基本概念

• C++有两大思想，面向对象和泛型编程。
• 泛型编程指编写代码时不必指定具体的数据类型，而是使用模板来代替实际类型，这样编写的函数或类可以在之后应用于各种数据类型。而STL就是C++泛型编程的一个杰出例子。
• STL（Standard Template Library）即标准模板库。STL通过使用模板实现了容器和算法的分离，允许程序员编写与类型无关的代码，这正是泛型编程的核心思想。

2 STL六大组件

• STL分为六大组件，分别是容器、算法、迭代器、仿函数、适配器和空间配置器。
• 容器：各种数据结构，主要用来存放数据。如vector、list、map等。
• 算法：各种常见的算法，用来处理元素。如sort、find、copy、for_each等。
• 迭代器：连接容器和算法的桥梁
• 仿函数：行为类似函数，可作为算法的某种策略
• 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
• 空间配置器：负责空间的配置与管理

3 容器概述

• 容器分为序列式容器和关联式容器
• 序列式容器：有序集合，其内的每个元素均有确凿的位置 - 取决于插入时机和地点，与元素值无关。主要有vector、deque、list和forward_list。
• 关联式容器：已排序集合，元素位置取决于其value（或key）和给定的某个排序准则。主要有set、multiset、map、multimap。

• 类型	容器	迭代器	特点
  序列容器	vector - 动态数组	迭代器支持随机访问 插入元素可能导致所有迭代器失效 删除元素会使指向被删除元素及之后元素的迭代器失效	支持快速随机访问 但在末尾以外位置插入或删除元素效率较低
  	deque - 双端队列	迭代器支持随机访问 插入和删除元素都可能导致迭代器失效	两端都可以高效地进行插入和删除操作 随机访问效率没有vector高
  	list - 双向链表	迭代器不支持随机访问 插入新元素不会使现有迭代器失效 删除元素只会使指向被删除元素的迭代器失效	支持高效的中间插入和删除操作，但访问速度较慢
  关联容器	set/multiset	插入元素不会使迭代器失效 删除元素只会使指向被删除元素的迭代器失效	查找、插入和删除操作的时间复杂度为 O(log n)。
  	map/multimap	插入元素不会使迭代器失效 删除元素只会使指向被删除元素的迭代器失效	查找、插入和删除操作的时间复杂度为 O(log n)。
  容器适配器	stack - 栈	无迭代器	先进后出的数据结构
  	queue - 队列	无迭代器	先进先出的数据结构

4 vector

• vector是动态数组。动态扩展时，会将原数据拷贝到一块新的内存中，再释放原内存空间。
• vector迭代器支持随机访问，即可以进行+2，+3，+n操作。不支持随机访问的迭代器只能进行++操作。
• 结构图示
  • 

4.1 vector构造

• vector<T> v：默认构造
• vector(v.begin(), v.end())：将[begin, end)区间的元素拷贝给本身
• vector(n, elem)：将n个elem元素拷贝给本身
• vector(const vector &vec)：拷贝构造
• vector构造示例

  •   #include <iostream>#include <string>#include <vector>int main() {// 默认构造std::vector<int> v1;// 插入数据v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);v1.push_back(50);// 通过区间方式构造std::vector<int> v2(v1.begin(), v1.end());// 构造时放入5个100std::vector<int> v3(10, 100);// 拷贝构造std::vector<int> v4(v3);system("pause");return 0;}
    

4.2 vector赋值

• vector& operator=(const vector &vec)
• assign(beg, end)：将[beg, end)区间的元素赋值给本身
• assign(n, elem)：将n个elem元素赋值给本身
• vector赋值示例

  •   #include <iostream>#include <string>#include <vector>int main() {// 默认构造std::vector<int> v1;// 插入数据v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);v1.push_back(50);// 通过=赋值std::vector<int> v2;v2 = v1;// 通过assign赋值一个区间的值std::vector<int> v3;v3.assign(v1.begin(), v1.end());// 通过assign赋值5个100std::vector<int> v4;v4.assign(5, 100);system("pause");return 0;}
    

4.3 vector容量和大小

• empty(): 判断容器是否为空
• capacity(): 容器的容量
• size(): 容器中元素个数
• resize(int num): 重新指定容器的长度为num，若容器变长，则以默认值填充新位置。若容器变短，则末尾超出长度的元素被删除。
• resize(int num, const value_type& value): 同上，只不过在容器变长时以value填充新位置。
• void reserve(int len): 容器预留len长度的空间，预留位置不初始化，元素不可访问。预留容器的空间可以减少vector在动态扩展时的扩展次数。

4.4 vector插入和删除

• push_back(elem): 尾部插入元素。
• pop_back(): 删除尾部元素。
• iterator insert(pos, elem): 迭代器指向位置pos处插入元素elem，返回新元素的位置。
• iterator insert(pos, count, elem): 迭代器执行位置pos处插入count个元素elem，返回新元素的位置。
• iterator erase(pos): 删除迭代器pos指向的元素，返回下一个数据的位置。
• iterator erase(first, last): 删除迭代器从first带last之间的元素，返回下一个数据的位置。
• clear(): 删除容器中所有元素。
• 插入删除示例

  •   #include <iostream>#include <string>#include <vector>#include <algorithm>void printVector(std::vector<int>& vec) {// 遍历数据std::cout << "vector: ";for (std::vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {std::vector<int> v;// 插入数据v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);printVector(v);v.pop_back();printVector(v);v.insert(v.begin(), 1024);printVector(v);v.insert(v.begin(), 2, 520);printVector(v);// 删除v.erase(v.begin());printVector(v);system("pause");return 0;}
    

• 打印结果

  •   vector: 10 20 30 40vector: 10 20 30vector: 1024 10 20 30vector: 520 520 1024 10 20 30vector: 520 1024 10 20 30请按任意键继续. . .
    

• vector插入自定义数据类型

  •   #include <iostream>#include <string>#include <vector>#include <algorithm>class Person {public:Person(int code, std::string name) {mCode = code;mName = name;}int mCode;std::string mName;};void vPrint(Person data) {std::cout << "code: " << data.mCode << std::endl;std::cout << "name: " << data.mName << std::endl;}int main() {Person p1(10010, "Tom");Person p2(10020, "Jack");Person p3(10030, "Lucy");Person p4(10040, "Mary");std::vector<Person> v;// 插入数据v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);// 通过迭代器遍历数据for (std::vector<Person>::iterator iter = v.begin(); iter != v.end(); iter++) {std::cout << "code " << (*iter).mCode << std::endl;std::cout << "name " << (*iter).mName << std::endl;}// 通过算法遍历std::for_each(v.begin(), v.end(), vPrint);system("pause");return 0;}
    

4.5 vector数据存取

• at( size_type pos ): 返回索引pos处的数据
• operator[]( size_type pos ): 返回索引pos处的数据
• front(): 返回容器中第一个元素
• back(): 返回容器中最后一个元素
• 数据存储示例

  •   #include <iostream>#include <string>#include <vector>void printVector(std::vector<int>& vec) {// 遍历数据std::cout << "vector[]: ";for (int i = 0; i < vec.size(); i++) {std::cout << vec[i] << " ";}std::cout << std::endl;std::cout << "vector at: ";for (int i = 0; i < vec.size(); i++) {std::cout << vec.at(i) << " ";}std::cout << std::endl;}int main() {std::vector<int> v;// 插入数据v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);printVector(v);system("pause");return 0;}
    

4.6 通过swap缩小容器容量

• void swap( vector& other ): 交换两个容器中的元素。常用的一个场景是缩小容器容量
• 示例如下

  •   #include <iostream>#include <string>#include <vector>int main() {// 默认构造std::vector<int> v1;// 插入50万个数据for (int i = 0; i < 500000; i++) {v1.push_back(i);}// 容器中元素为50万，容器容量可能为70万std::cout << "v1.size: " << v1.size() << std::endl;std::cout << "v1.cap: " << v1.capacity() << std::endl;// 后续如果要删除元素，比如只剩下3个元素了// 此时容器元素个数为3，但容器容量依然是70万，造成资源浪费v1.resize(3);std::cout << "v1.size: " << v1.size() << std::endl;std::cout << "v1.cap: " << v1.capacity() << std::endl;// 通过匿名对象交换容器// 匿名对象中的元素会被系统自动回收std::vector<int>(v1).swap(v1);// v1此时的元素个数和容量都为3std::cout << "v1.size: " << v1.size() << std::endl;std::cout << "v1.cap: " << v1.capacity() << std::endl;system("pause");return 0;}
    

5 deque

• deque是双端队列，可以在头部进行插入删除操作
• vector对于头部的插入删除效率低，数据量越大，效率越低。deque对头部的插入删除速度比vector快。vector访问元素的速度比deque快。
• deque容器的迭代器支持随机访问。
• 结构图示
  • 
• deque工作原理：deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据。中控器维护的是每段缓冲区的地址。图示如下
  • 
• deque的构造、赋值、遍历、数据存取和vector基本类似，这里就不再介绍。

5.1 deque容量和大小

• empty()：判断容器是否为空。
• size()：返回容器中元素个数。
• resize(num)：重新指定容器的长度为num。若容器变长，则以默认值填充新位置。若容器变短，则末尾超出容器长度的元素被删除。
• resize(num, elem)：同上，重新指定容器长度为num，容器变长则以elem填充。

5.2 deque插入和删除

• push_back(elem)：容器尾部插入数据。
• push_front(elem)：容器头部插入数据。
• pop_back()：删除容器尾部最后一个数据。
• pop_front()：删除容器头部第一个容器。
• iterator intsert(pos, elem)：在pos位置插入一个elem数据，返回新数据的位置。
• iterator intsert(pos, n, elem)：在pos位置插入n个elem数据，返回新数据的位置。
• iterator intsert(pos, beg, end)：在pos位置插入[beg, end)区间的数据，返回新数据的位置。
• clear()：清空容器的所有数据。
• iterator erase(beg, end)：删除[beg, end)区间的数据，返回下一个数据的位置。
• iterator erase(pos)：删除pos位置的数据，返回下一个数据的位置。
• 代码示例

  •   #include <iostream>#include <string>#include <deque>void printDeque(std::deque<int> & de) {std::cout << "deque: ";for (std::deque<int>::iterator iter = de.begin(); iter != de.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {// 默认构造std::deque<int> d1;// 尾部插入d1.push_back(10);d1.push_back(20);d1.push_back(30);printDeque(d1);// 头部插入d1.push_front(40);d1.push_front(50);d1.push_front(60);printDeque(d1);// 删除尾部元素d1.pop_back();printDeque(d1);// 删除头部元素d1.pop_front();printDeque(d1);// insert插入std::deque<int>::iterator iter1 = d1.insert(d1.begin(), 1024);printDeque(d1);std::cout << "*iter1: " << *iter1 << std::endl;// insert插入多个元素std::deque<int>::iterator iter2 = d1.insert(d1.begin(), 2, 256);printDeque(d1);std::cout << "*iter2: " << *iter2 << std::endl;std::deque<int> d2;d2.push_back(1);d2.push_back(2);d2.push_back(3);// insert 区间插入std::deque<int>::iterator iter3 = d1.insert(d1.begin(), d2.begin(), d2.end());printDeque(d1);std::cout << "*iter3: " << *iter3 << std::endl;// 删除指定位置元素std::deque<int>::iterator iter4 = d1.begin();iter4++;std::deque<int>::iterator iter5 = d1.erase(iter4);printDeque(d1);std::cout << "*iter5: " << *iter5 << std::endl;// 删除所有元素d1.clear();system("pause");return 0;}
    

• 打印结果

  •   deque: 10 20 30deque: 60 50 40 10 20 30deque: 60 50 40 10 20deque: 50 40 10 20deque: 1024 50 40 10 20*iter1: 1024deque: 256 256 1024 50 40 10 20*iter2: 256deque: 1 2 3 256 256 1024 50 40 10 20*iter3: 1deque: 1 3 256 256 1024 50 40 10 20*iter5: 3请按任意键继续. . .
    

5.3 deque排序

• sort(iterator beg, iterator end)：对beg和end区间内元素进行排序
• 迭代器支持随机访问的容器都可以使用sort进行排序
• 代码示例

  •   #include <iostream>#include <string>#include <deque>#include <algorithm>void printDeque(std::deque<int> & de) {std::cout << "deque: ";for (std::deque<int>::iterator iter = de.begin(); iter != de.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {// 默认构造std::deque<int> d1;// 尾部插入d1.push_back(10);d1.push_back(900);d1.push_back(23);d1.push_back(250);d1.push_back(18);printDeque(d1);sort(d1.begin(), d1.end());printDeque(d1);system("pause");return 0;}
    

• 结果打印

  •   deque: 10 900 23 250 18deque: 10 18 23 250 900请按任意键继续. . .
    

6 stack

• stack是栈，一种先进后出的数据结构，只有一个出口。
• 栈中只有顶端元素才可以被外部使用，因此栈没有遍历操作。
• 结构图示
  • 

6.1 stack赋值操作

• stack& operator=(const stack &stk)

6.2 stack数据存取

• push(elem)：向栈顶添加元素（入栈）。
• pop()：从栈顶移除元素（出栈）。
• top()：返回栈顶元素。

6.3 stack 大小操作

• empty()：判断栈是否为空。
• size()：返回栈大小。
• 使用示例

  •   #include <iostream>#include <string>#include <stack>int main() {// 默认构造std::stack<int> st1;// 入栈st1.push(10);st1.push(20);st1.push(30);st1.push(40);// 获取栈顶元素std::cout << "stack top: " << st1.top() << std::endl;std::cout << "stack size: " << st1.size() << std::endl;while (!st1.empty()) {std::cout << "stack top: " << st1.top() << std::endl;// 出栈st1.pop();}std::cout << "stack size: " << st1.size() << std::endl;system("pause");return 0;}
    

• 打印结果

  •   stack top: 40stack size: 4stack top: 40stack top: 30stack top: 20stack top: 10stack size: 0请按任意键继续. . .
    

7 queue

• queue是队列，一种先进先出的数据结构。
• 队列允许从一端新增元素，另一端移除元素。队列中只有队头和队尾才可以被外部使用，因此队列不允许有遍历行为。
• 结构图示
  • 

7.1 queue构造

• queue<T> que：默认构造。
• queue(const queue &que)：拷贝构造。

7.2 queue赋值

• queue& operator=(const queue &que)

7.3 queue数据存取

• push(elem)：队尾添加元素（入队）。
• pop()：移除队头元素（出队）。
• back()：返回队尾元素。
• front()：返回队头元素。

7.4 queue大小操作

• empty()：判断队列是否为空。
• size()：返回队列大小。
• 使用示例

  •   #include <iostream>#include <string>#include <queue>int main() {// 默认构造std::queue<int> que1;// 入队que1.push(10);que1.push(20);que1.push(30);que1.push(40);std::cout << "size: " << que1.size() << std::endl;while (!que1.empty()) {// 查看队头和队尾元素std::cout << "front: " << que1.front()  << ", back: "<< que1.back() << std::endl;// 出队que1.pop();}std::cout << "size: " << que1.size() << std::endl;system("pause");return 0;}
    

• 打印结果

  •   size: 4front: 10, back: 40front: 20, back: 40front: 30, back: 40front: 40, back: 40size: 0请按任意键继续. . .
    

8 list

• list是链表，一种物理存储单元上非连续的存储结构。list可以在任意位置进行快速插入和删除元素，但遍历速度没有vector快。list的迭代器属于双向迭代器。
• list插入和删除都不会造成原有list迭代器的失效。list的迭代器不支持随机访问。
• STL中的链表是一个双向循环链表。
• 结构图示
  • 

8.1 list构造

• list<T> lst：默认构造
• list(begin, end)：将[begin, end)区间的元素拷贝给本身
• list(n, elem)：将n个elem元素拷贝给本身
• list(const list &lst)：拷贝构造。
• 使用示例

  •   #include <iostream>#include <string>#include <list>void printList(std::list<int>& lst) {std::cout << "list: ";for (std::list<int>::iterator iter = lst.begin(); iter != lst.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {// 默认构造std::list<int> lst1;// 添加数据lst1.push_back(10);lst1.push_back(20);lst1.push_back(30);lst1.push_back(40);printList(lst1);// 区间方式构造std::list<int> lst2(lst1.begin(), lst1.end());printList(lst2);// 拷贝构造std::list<int> lst3(lst2);printList(lst3);std::list<int> lst4(5, 10);printList(lst4);system("pause");return 0;}
    

• 打印结果

  •   list: 10 20 30 40list: 10 20 30 40list: 10 20 30 40list: 10 10 10 10 10请按任意键继续. . .
    

8.2 list赋值和交换

• assign(beg, end)：将[beg, end)区间的数据拷贝给本身。
• assign(n, elem)：将n个elem元素拷贝给本身。
• list& operator=(const list &lst)
• swap(lst)：将lst元素与本身元素互换。
• 使用示例

  •   #include <iostream>#include <string>#include <list>void printList(std::list<int>& lst) {std::cout << "list: ";for (std::list<int>::iterator iter = lst.begin(); iter != lst.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {// 默认构造std::list<int> lst1;// 添加数据lst1.push_back(10);lst1.push_back(20);lst1.push_back(30);lst1.push_back(40);printList(lst1);// 赋值std::list<int> lst2;lst2 = lst1;printList(lst2);std::list<int> lst3;lst3.assign(lst1.begin(), lst1.end());printList(lst3);std::list<int> lst4;lst4.assign(5, 10);printList(lst4);// 交换std::list<int> lst5;// 添加数据lst5.push_back(100);lst5.push_back(200);lst5.push_back(300);lst5.push_back(400);std::cout << "交换前" << std::endl;printList(lst1);printList(lst5);lst1.swap(lst5);std::cout << "交换前" << std::endl;printList(lst1);printList(lst5);system("pause");return 0;}
    

• 打印结果

  •   list: 10 20 30 40list: 10 20 30 40list: 10 20 30 40list: 10 10 10 10 10交换前list: 10 20 30 40list: 100 200 300 400交换前list: 100 200 300 400list: 10 20 30 40请按任意键继续. . .
    

8.3 list容量和大小

• empty()：判断容器是否为空。
• size()：返回容器中元素个数。
• resize(num)：重新指定容器的长度为num。若容器变长，则以默认值填充新位置。若容器变短，则末尾超出容器长度的元素被删除。
• resize(num, elem)：同上，重新指定容器长度为num，容器变长则以elem填充。

8.4 list插入和删除

• push_back(elem)：容器尾部插入一个元素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()：移除容器中所有元素
• erese(beg, end)：删除[beg, end)区间的元素，返回下一个元素的位置
• erese(pos)：删除pos位置处的元素，返回下一个元素的位置
• remove(elem)：删除容器中所有与elem值匹配的元素
• 使用示例

  •   #include <iostream>#include <string>#include <list>void printList(std::list<int>& lst) {std::cout << "list: ";for (std::list<int>::iterator iter = lst.begin(); iter != lst.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {// 默认构造std::list<int> lst1;// 尾部添加数据lst1.push_back(10);lst1.push_back(20);lst1.push_back(30);lst1.push_back(40);// 头部添加元素lst1.push_front(50);lst1.push_front(60);printList(lst1);// 尾部删除lst1.pop_back();// 头部删除lst1.pop_front();printList(lst1);std::list<int>::iterator iter;// insert插入iter = lst1.begin();iter++;lst1.insert(iter, 1024);printList(lst1);// 删除iter = lst1.begin();lst1.erase(iter);printList(lst1);// 移除lst1.push_back(30);lst1.push_back(30);lst1.remove(30);printList(lst1);system("pause");return 0;}
    

• 打印结果

  •   list: 60 50 10 20 30 40list: 50 10 20 30list: 50 1024 10 20 30list: 1024 10 20 30list: 1024 10 20请按任意键继续. . .
    

8.5 list数据存取

• front()：返回容器中第一个元素
• back()：返回容器中最后一个元素

8.6 list反转和排序

• reverse()：反转链表
• sort()：链表排序
• 使用示例

  •   #include <iostream>#include <string>#include <list>void printList(std::list<int>& lst) {std::cout << "list: ";for (std::list<int>::iterator iter = lst.begin(); iter != lst.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}bool myCompare(int data1, int data2) {// 设置降序return data1 > data2;}int main() {// 默认构造std::list<int> lst1;// 尾部添加数据lst1.push_back(10);lst1.push_back(200);lst1.push_back(54);lst1.push_back(1024);lst1.push_back(521);printList(lst1);// 反转lst1.reverse();printList(lst1);// 排序 - 升序lst1.sort();printList(lst1);// 排序 - 降序lst1.sort(myCompare);printList(lst1);system("pause");return 0;}
    

• 打印结果

  •   list: 10 200 54 1024 521list: 521 1024 54 200 10list: 10 54 200 521 1024list: 1024 521 200 54 10请按任意键继续. . .
    

9 pair对组

• pair是成对出现的数据，利用对组可以返回两个数据

9.1 创建方式

• pair<type, type> p(value1, value2)
• pair<type, type> p = make_pair(value1, value2)
• 使用示例

  •   #include <iostream>#include <string>int main() {// 第一种创建方式std::pair<int, std::string> pa(10010, "Tom");std::cout << "pa.first: " << pa.first << ", pa.second: " << pa.second << std::endl;// 第二种创建方式std::pair<int, std::string> pa2 = std::make_pair(10020, "Mary");std::cout << "pa2.first: " << pa2.first << ", pa2.second: " << pa2.second << std::endl;system("pause");return 0;}
    

• 打印结果

  •   pa.first: 10010, pa.second: Tompa2.first: 10020, pa2.second: Mary请按任意键继续. . .
    

10 set/multiset

• set/multiset属于关联式容器，底层结构是用二叉树实现（通常为平衡二叉树），所有元素会在插入时自动排序。
• set不允许容器中有重复的元素，multiset允许容器中有重复的元素。
• 结构图示
  • 

10.1 set构造和赋值

• set<T> st：默认构造
• set(const set& st)：拷贝构造
• set& operator=(const set& st)：赋值
• 使用示例

  •   #include <iostream>#include <string>#include <vector>#include <algorithm>#include <set>void printSet(std::set<int>& st) {// 遍历数据std::cout << "list: ";for (std::set<int>::iterator iter = st.begin(); iter != st.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {std::set<int> st;// 插入数据st.insert(10);st.insert(100);st.insert(100);st.insert(15);st.insert(520);st.insert(2);printSet(st);// 拷贝构造std::set<int> st2(st);printSet(st2);// 赋值std::set<int> st3;st3 = st;printSet(st3);system("pause");return 0;}
    

• 打印结果

  •   #include <iostream>#include <string>#include <vector>#include <algorithm>#include <set>void printSet(std::set<int>& st) {// 遍历数据std::cout << "list: ";for (std::set<int>::iterator iter = st.begin(); iter != st.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {std::set<int> st;// 插入数据st.insert(10);st.insert(100);st.insert(100);st.insert(15);st.insert(520);st.insert(2);printSet(st);// 拷贝构造std::set<int> st2(st);printSet(st2);// 赋值std::set<int> st3;st3 = st;printSet(st3);system("pause");return 0;}
    

10.2 set大小和交换

• size()：获取容器中元素个数。
• empty()：判断容器是否为空。
• swap(st)：交换两个容器。

10.3 set插入和删除

• insert(elem)：插入元素。
• clear()：清除所有元素。
• erase(pos)：删除pos迭代器指向的元素，返回下一个元素的迭代器。
• erase(beg, end)：删除区间[beg, end)的所有元素，返回下一个元素的迭代器。
• erase(elem)：删除容器中值为elem的元素。

10.4 set查找和统计

• find(key)：查找key是否存在，若存在，返回该键的元素的迭代器，若不存在，返回set.end()。
• count(key)：统计key的元素个数。对于set容器，只有0或者1。
• 使用示例

  •   #include <iostream>#include <string>#include <vector>#include <algorithm>#include <set>void printSet(std::set<int>& st) {// 遍历数据std::cout << "list: ";for (std::set<int>::iterator iter = st.begin(); iter != st.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;}int main() {std::set<int> st;// 插入数据st.insert(10);st.insert(100);st.insert(100);st.insert(15);st.insert(520);st.insert(2);printSet(st);std::set<int>::iterator iter = st.find(100);if (iter != st.end()) {std::cout << "*iter: " << *iter << std::endl;}std::cout << "st.count(100): " << st.count(100) << std::endl;system("pause");return 0;}
    

• 打印结果

  •   list: 2 10 15 100 520*iter: 100st.count(100): 1请按任意键继续. . .
    

10.5 set和multiset区别

• set不可以插入重复数据，而multiset可以。
• set插入数据的同时会返回插入结果，表示是否插入成功。multiset不会检测数据，因此可以插入重复数据。
• 示例

  •   #include <iostream>#include <set>int main() {std::set<int> st;// 插入数据std::pair<std::set<int>::iterator, bool> ret;// 返回值为pair, 第一个参数为插入位置迭代器，第二个参数表示是否插入成功ret = st.insert(100);if (ret.second) {// 插入成功std::cout << "插入成功: " << *ret.first <<std::endl;}else {// 插入失败std::cout << "插入失败" << std::endl;}ret = st.insert(100);if (ret.second) {// 插入成功std::cout << "插入成功: " << *ret.first << std::endl;}else {// 插入失败std::cout << "插入失败" << std::endl;}std::multiset<int> mst;std::set<int>::iterator iter;// 返回值为插入位置迭代器iter = mst.insert(200);std::cout << "*iter: " << *iter << std::endl;iter = mst.insert(200);std::cout << "*iter: " << *iter << std::endl;system("pause");return 0;}
    

• 打印结果

  •   插入成功: 100插入失败*iter: 200*iter: 200请按任意键继续. . .
    

10.6 set容器排序

• set容器默认排序规则是从小到大，利用仿函数，可以改变默认排序规则。
• set存放内置数据类型
• 使用示例

  •   #include <iostream>#include <string>#include <vector>#include <algorithm>#include <set>// 利用仿函数指定排序规则为从大到小class myCompare {public:bool operator()(int data1, int data2) {return data1 > data2;}};int main() {std::set<int> st;// 插入数据st.insert(10);st.insert(100);st.insert(15);st.insert(520);st.insert(2);std::cout << "st: ";for (std::set<int>::iterator iter = st.begin(); iter != st.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;// 指定排序规则为从大到小// 利用仿函数std::set<int, myCompare> st2;st2.insert(10);st2.insert(100);st2.insert(15);st2.insert(520);st2.insert(2);std::cout << "st2: ";for (std::set<int, myCompare>::iterator iter = st2.begin(); iter != st2.end(); iter++) {std::cout << *iter << " ";}std::cout << std::endl;system("pause");return 0;}
    

• 打印结果

  •   st: 2 10 15 100 520st2: 520 100 15 10 2请按任意键继续. . .
    

• set存放自定义数据类型
• 使用示例

  •   #include <iostream>#include <string>#include <set>class Person {public:Person(int code, std::string name) {mCode = code;mName = name;}int mCode;std::string mName;};// 利用仿函数指定排序规则class myComparePerson {public:bool operator()(const Person &p1, const Person &p2) {return p1.mCode < p2.mCode;}};int main() {std::set<Person, myComparePerson> st;Person p1(10010, "Tom");Person p2(10080, "Jack");Person p3(10000, "Mary");Person p4(11100, "Lucy");// 插入数据st.insert(p1);st.insert(p2);st.insert(p3);st.insert(p4);for (std::set<Person, myComparePerson>::iterator iter = st.begin(); iter != st.end(); iter++) {std::cout << iter->mCode << " " << iter->mName << std::endl;}system("pause");return 0;}
    

• 打印结果

  •   10000 Mary10010 Tom10080 Jack11100 Lucy请按任意键继续. . .
    

11 map/multimap

• map中所有元素都是pair，pair中第一个元素为key（键值），起到索引作用，第二个元素为value（值），所有元素都会根据元素的键值自动排序。
• map/multimap属于关联式容器，底层结构是用二叉树实现（通常为平衡二叉树）。
• map中不允许容器中有重复key值，multimap允许容器中有重复key值。
• 结构图示
  • 

11.1 map构造和赋值

• map<T1, T2> mp：默认构造
• map(const map &mp)：拷贝构造
• map& operator=(const map& mp)：等号赋值。
• 使用示例

  •   #include <iostream>#include <string>#include <map>void printMap(std::map<int, std::string>& mp) {// 遍历数据for (std::map<int, std::string>::iterator iter = mp.begin(); iter != mp.end(); iter++) {std::cout << "iter->first: " << iter->first << ", iter->second: " << iter->second << std::endl;}}int main() {std::map<int, std::string> mp;// 插入数据mp.insert(std::pair<int, std::string>(10010, "AA"));mp.insert(std::pair<int, std::string>(11000, "BB"));mp.insert(std::pair<int, std::string>(11110, "CC"));mp.insert(std::pair<int, std::string>(10000, "DD"));mp.insert(std::pair<int, std::string>(10001, "EE"));std::cout << "mp: " << std::endl;printMap(mp);// 拷贝构造std::map<int, std::string> mp2(mp);std::cout << "mp2: " << std::endl;printMap(mp2);// 赋值std::map<int, std::string> mp3;mp3 = mp;std::cout << "mp3: " << std::endl;printMap(mp3);system("pause");return 0;}
    

• 打印结果

  •   mp:iter->first: 10000, iter->second: DDiter->first: 10001, iter->second: EEiter->first: 10010, iter->second: AAiter->first: 11000, iter->second: BBiter->first: 11110, iter->second: CCmp2:iter->first: 10000, iter->second: DDiter->first: 10001, iter->second: EEiter->first: 10010, iter->second: AAiter->first: 11000, iter->second: BBiter->first: 11110, iter->second: CCmp3:iter->first: 10000, iter->second: DDiter->first: 10001, iter->second: EEiter->first: 10010, iter->second: AAiter->first: 11000, iter->second: BBiter->first: 11110, iter->second: CC请按任意键继续. . .
    

11.2 map大小和交换

• size()：返回容器中元素个数。
• empty()：判断容器是否为空。
• swap(st)：交换两个容器数据。

11.3 map插入和删除

• insert(elem)：插入元素。
• clear()：清除所有元素。
• erase(pos)：删除pos迭代器指向的元素，返回下一个元素的迭代器。
• erase(beg, end)：删除区间[beg, end)的所有元素，返回下一个元素的迭代器。
• erase(elem)：删除容器中值为elem的元素。
• 使用示例

  •   #include <iostream>#include <string>#include <map>void printMap(std::map<int, std::string>& mp) {// 遍历数据for (std::map<int, std::string>::iterator iter = mp.begin(); iter != mp.end(); iter++) {std::cout << "iter->first: " << iter->first << ", iter->second: " << iter->second << std::endl;}}int main() {std::map<int, std::string> mp;// 插入数据// 第一种插入方式mp.insert(std::pair<int, std::string>(10010, "AA"));mp.insert(std::pair<int, std::string>(11000, "BB"));// 第二种插入方式mp.insert(std::make_pair(11110, "CC"));mp.insert(std::make_pair(10000, "DD"));// 第三种插入方式mp.insert(std::map<int, std::string>::value_type(10001, "EE"));// 第四种插入方式(不建议使用)mp[11111] = "FF";std::cout << "mp: " << std::endl;printMap(mp);// 删除// 根据迭代器删除mp.erase(mp.begin());std::cout << "根据迭代器删除: " << std::endl;printMap(mp);// 根据key值删除mp.erase(11111);std::cout << "根据key值删除: " << std::endl;printMap(mp);system("pause");return 0;}
    

• 打印结果

  •   mp:iter->first: 10000, iter->second: DDiter->first: 10001, iter->second: EEiter->first: 10010, iter->second: AAiter->first: 11000, iter->second: BBiter->first: 11110, iter->second: CCiter->first: 11111, iter->second: FF根据迭代器删除:iter->first: 10001, iter->second: EEiter->first: 10010, iter->second: AAiter->first: 11000, iter->second: BBiter->first: 11110, iter->second: CCiter->first: 11111, iter->second: FF根据key值删除:iter->first: 10001, iter->second: EEiter->first: 10010, iter->second: AAiter->first: 11000, iter->second: BBiter->first: 11110, iter->second: CC请按任意键继续. . .
    

11.4 map查找和统计

• find(key)：查找key是否存在，若存在，返回该键的元素的迭代器，若不存在，返回map.end()。
• count(key)：统计key的元素个数。对于map容器，只有0或者1。
• 使用示例

  •   #include <iostream>#include <string>#include <map>void printMap(std::map<int, std::string>& mp) {// 遍历数据for (std::map<int, std::string>::iterator iter = mp.begin(); iter != mp.end(); iter++) {std::cout << "iter->first: " << iter->first << ", iter->second: " << iter->second << std::endl;}}int main() {std::map<int, std::string> mp;// 插入数据mp.insert(std::pair<int, std::string>(10010, "AA"));mp.insert(std::pair<int, std::string>(11000, "BB"));mp.insert(std::pair<int, std::string>(11110, "CC"));mp.insert(std::pair<int, std::string>(10000, "DD"));mp.insert(std::pair<int, std::string>(10001, "EE"));// 查找std::map<int, std::string>::iterator iter = mp.find(11110);if (iter != mp.end()) {std::cout << "找到了" << std::endl;std::cout << "key: " << iter->first << ", value: " << iter->second << std::endl;}else {std::cout << "未找到" << std::endl;}// 统计std::cout << "mp.count(10000): " << mp.count(10000) <<std::endl;system("pause");return 0;}
    

• 打印结果

  •   找到了key: 11110, value: CCmp.count(10000): 1请按任意键继续. . .
    

11.5 map容器排序

• map容器默认排序规则是从小到大，利用仿函数，可以改变默认排序规则。
• 使用示例

  •   #include <iostream>#include <string>#include <map>class myCompare {public:bool operator()(int data1, int data2) {return data1 > data2;}};int main() {std::map<int, std::string, myCompare> mp;// 插入数据mp.insert(std::pair<int, std::string>(10010, "AA"));mp.insert(std::pair<int, std::string>(11000, "BB"));mp.insert(std::pair<int, std::string>(11110, "CC"));mp.insert(std::pair<int, std::string>(10000, "DD"));mp.insert(std::pair<int, std::string>(10001, "EE"));for (std::map<int, std::string, myCompare>::iterator iter = mp.begin(); iter != mp.end(); iter++) {std::cout << "iter->first: " << iter->first << ", iter->second: " << iter->second << std::endl;}system("pause");return 0;}
    

• 打印结果

  •   iter->first: 11110, iter->second: CCiter->first: 11000, iter->second: BBiter->first: 10010, iter->second: AAiter->first: 10001, iter->second: EEiter->first: 10000, iter->second: DD请按任意键继续. . .