[toc]
前言
顺序容器
迭代器及顺序容器介绍
| 类型 |
说明 |
| *iter |
返回迭代器iter所指元素的引用 |
| iter->men |
解引用iter并获取元素名为mem的成员，等价于(*iter).mem |
| iter++ |
令iter指示容器中的下一个元素 |
| iter– |
令iter指示容器中的上一个元素 |
| iter1==iter2 |
判断两个迭代器是否相等，即是否指示同一个元素 |
| iter1!=iter2 |
判断两个迭代器是否不相等 |
- 表1.2 迭代器支持的运算符补充（适用vector、string、deque和array等容器）
| 类型 |
说明 |
| iter + n |
迭代器加上一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比向前移动了n个元素 |
| iter - n |
迭代器减去一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比向后移动了n个元素 |
| iter += n |
迭代器加法的复合赋值语句 |
| iter -= n |
迭代器减法的复合赋值语句 |
| iter1 - iter2 |
同一个容器中两个迭代器相减，结果是两个迭代器所指元素之间的距离 |
| >、>=、<、<= |
迭代器的关系运算符 |
特别注意：所有顺序容器都提供了 快速顺序访问 元素的能力。
| 顺序容器 |
名称 |
访问类型 |
说明 |
| string |
字符串 |
快速随机访问 |
支持表1.1和表1.2所述的所有运算 |
| vector |
动态数组 |
快速随机访问 |
支持表1.1和表1.2所述的所运算 |
| deque |
双端队列 |
快速随机访问 |
支持表1.1和表1.2所述的所有运算 |
| list |
双端链表 |
双向顺序访问 |
迭代器只重载了++运算符，没有重载+加法运算符，仅支持表1.1所述的迭代器运算 |
| forward list |
单向链表 |
单向顺序访问 |
仅支持表1.1所述的除了递减运算符之外的其他迭代器运算 |
| array |
固定大小数组 |
快速随机访问 |
支持表1.1和表1.2所述所有迭代器运算 |
(1) 快速随机访问指的是：通过下标运算符[ ]（类重载）访问容器中的元素，访问速度快，但是这种方式有一个缺点，即当访问越界时，程序会直接奔溃；
另外，可以通过at(int index)方法，返回索引index所指的容器中的数据元素，如果index越界，程序抛出out_of_range异常，这种数据获取的方式更加安全，但at()方法的访问速度相比[ ]较慢。
(2) 顺序访问指的是：list双端链表的数据元素并不是保存在连续的内存空间中，list的迭代器中重载了++运算符，即可以通过迭代器（指针）循环操作访问list中的数据元素，但是list禁止通过下标运算符的方式访问数据元素。
划重点：C ++迭代器用于对数据结构中的元素进行顺序访问或随机访问。因此，对于根据定义不允许顺序或随机访问的数据结构（queue、stack等），迭代器没有任何意义。
string容器 字符串
vector容器 动态数组
vector动态数组，vector将元素保存在连续的内存空间中；由于元素是连续存储的，因此通过元素的下标来计算元素地址是非常快速的。
vector是单口容器，在尾部插入和删除元素效率很高，在尾部之外的位置插入或删除元素会引起元素的移动，效率低。
当vector空间被充满的时候，在插入新的数据元素时，vector会重新申请一块更大的内存空间，将原空间的数据拷贝到新的内存空间，然后释放旧的内存空间，最后将新的数据元素插入到vector中。
vector构造函数
| 类型 |
说明 |
| vector v; |
默认构造函数，采用模板实现类实现 |
| vector v(src.begin(), src.end()); |
将src[begin(), end())区间中的元素赋给v |
| vector v(n, elem); |
将n个elem数据元素赋给v |
| vector v(const vector &src); |
拷贝构造函数 |
例如：
1
2
| int arr[] = { 1, 2, 3, 4, 5 };
vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));
|
vector常用赋值操作
| 类型 |
说明 |
| void assign(src.begin(), src.end()); |
将src[begin(), end())区间中的元素赋给v |
| void assign(int n, T elem); |
将n个elem数据元素赋给v |
| vector& operator=(const vector &src); |
重载赋值运算符= |
| void swap(vector src); |
将src与v互换 |
例如：
1
2
3
| int arr[] = { 1, 2, 3, 4, 5 };
vector<int> v;
v.assign(arr, arr + sizeof(arr) / sizeof(arr[0]));
|
vector大小操作
| 类型 |
说明 |
| size(); |
返回容器中元素的个数 |
| capacity(); |
返回容器的容量 |
| empty(); |
判断容器是否为空 |
| resize(int num); |
重新指定容器的长度为num，若容器变长，则以默认值填充新位置；若容器变短，则删除超出长度的元素 |
| resize(int num, T elem); |
重新指定容器的长度为num，若容器变长，则以elem值填充新位置；若容器变短，则删除超出长度的元素 |
| reserve(int len); |
容器预留len个元素长度，预留位置不初始化，不能立即访问 |
vector数据存取操作
| 类型 |
说明 |
| at(int index); |
返回索引index所指的数据元素 |
| operator[](int index); |
返回索引index所指的数据元素 |
| front(); |
返回容器中的第一个数据元素 |
| back(); |
返回容器中的最后一个数据元素 |
vector插入和删除操作
| 类型 |
说明 |
| insert(const_iterator pos, int num, T elem); |
在pos位置插入num个elem数据元素 |
| push_back(T elem); |
在尾部插入数据元素elem |
| pop_back(); |
删除尾部最后一个元素 |
| erase(const_iterator start, const_iterator end); |
删除迭代器[start, end)之间的数据元素 |
| erase(const_iterator pos); |
删除迭代器pos指向的数据元素 |
| clear(); |
删除容器中的所有数据元素 |
deque容器 双端队列
- deque双端队列允许常数时间内对头部进行元素插入和删除操作；
- deque双端队列没有容量的概念，原因在于vector动态数组是将数据元素保存在连续的内存空间中，而deque双端队列的数据元素的存储空间是由分段的连续空间组合而成，随时可以增加一段新的空间并链接起来。
deque构造函数
| 类型 |
说明 |
| deque(); |
默认构造函数，采用模板实现类实现 |
| deque(src.begin(), src.end()); |
将src[begin(), end())区间中的元素赋给d |
| deque(int n, T elem); |
将n个elem数据元素赋给d |
| deque(const deque &src); |
拷贝构造函数 |
deque常用赋值操作
| 类型 |
说明 |
| void assign(src.begin(), src.end()); |
将src[begin(), end())区间中的元素赋给d |
| void assign(int n, T elem); |
将n个elem数据元素赋给d |
| deque & operator=(const deque &src); |
重载赋值运算符= |
| swap(deque src); |
将src与d互换 |
deque大小操作
| 类型 |
说明 |
| size(); |
返回容器中元素的个数 |
| empty(); |
判断容器是否为空 |
| resize(int num); |
重新指定容器的长度为num，若容器变长，则以默认值填充新位置；若容器变短，则删除超出长度的元素 |
| resize(int num, T elem); |
重新指定容器的长度为num，若容器变长，则以elem值填充新位置；若容器变短，则删除超出长度的元素 |
deque数据存取操作
| 类型 |
说明 |
| at(int index); |
返回索引index所指的数据元素 |
| operator[](int index); |
返回索引index所指的数据元素 |
| front(); |
返回容器中的第一个数据元素 |
| back(); |
返回容器中的最后一个数据元素 |
deque插入和删除操作
| 类型 |
说明 |
| push_back(T elem); |
在尾部插入数据元素elem |
| push_front(T elem); |
在头部插入数据元素elem |
| pop_back(); |
删除尾部最后一个元素 |
| pop_front(); |
删除头部第一个元素 |
| insert(const_iterator pos, int num, T elem); |
在pos位置插入num个elem元素 |
| insert(const_iterator pos, T elem); |
在pos位置插入elem元素 |
| insert(const_iterator pos, src.begin(), src.end()); |
在pos位置插入src[begin, end)区间的元素 |
list容器 双向链表
顺序容器适配器
stack容器 栈
queue容器 队列
关联容器
set容器
map容器
