当前位置：首页 > news >正文
C++ STL之容器介绍（vector、list、set、map）

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