c++容器
顺序容器
一个容器就是一些特点类型对象的集合，顺序容器为程序提供了控制元素存储和访问顺序的能力，这种顺序不依赖元素的值，而是与元素加入容器时的位置相对应。
| 顺序容器类型 | 含义 |
|---|---|
| vector | 可变大小数组，支持快速随机访问，在尾部以外插入/删除元素很慢 |
| deque | 双端队列，支持快速随机访问，在头尾部位置插入/删除速度很快 |
| list | 双向链表，只支持双向顺序访问，在list中任何位置进行插/删都很快 |
| forward_list | 单向链表，只支持单向顺序访问，在任何位置进行插/删都很快 |
| array | 固定大小数组，支持快速随机访问，不能添/删元素 |
| string | 与vector相似的容器，但专门用于保存字符，随访快，尾插/删快 |
通常vector是最好的选择，除非你有更好的理由选择其他容器。
容器操作
| 类型别名 | 含义 |
|---|---|
| iteration | 此容器类型的迭代器类型 |
| const_iterator | 可以读取元素，但不能修改元素的迭代器类型 |
| size_type | 无符号整数类型，足够保存此种容器类型最大可能容器的大小 |
| difference_type | 带符号整数类型，足够保存两个迭代器之间的距离 |
| value_type | 元素类型 |
| reference | 元素的左值类型，与value_type相同 |
| conse_reference | 元素的const左值类型 |
容器定义和初始化
| 构造函数 | 含义 |
|---|---|
| C c | 默认构造函数，如果C是一个array，则C中元素默认方式和初始化，否则C为空 |
| C c(c2)/C c1=c2 | c1为c2的拷贝，c1与c2必须为相同类型，array两者还需有相同大小 |
| C c{a,b,c…}/C c={a,b,c…} | c初始化为初始化列表中元素的拷贝 |
| C c{b,e} | c初始化为迭代器b和e指定范围中元素的拷贝 |
| C seq(n) | seq包含n个元素，这些元素进行了值初始化(string不适用) |
| C seq(n,t) | seq包含n个初始化值t的元素 |
赋值和swap
| 操作 | 含义 |
|---|---|
| c1=c2 | 将c1中的元素替换为c2中元素的拷贝 |
| c1={a,b,c…} | 将c1中元素替换为初始化列表中元素的拷贝，array不可用 |
| swap(c1,c2)/c1.swap(c2) | 交换c1和c2的元素，swap通常比c2向c1拷贝快得多 |
| seq.assign(b,e) | 将seq中元素替换为迭代器b和e所表示的范围中的元素 |
| seq.assign(il) | 将seq中元素替换为il中的元素 |
| seq.assingn(n,t) | 将seq中元素替换为n个值为t的元素 |
赋值相关运算会导致指向左边容器内部的迭代器，引用和指针失效、而swap操作将容器交换不会导致失效（array与string除外）。
增删元素
增删元素会导致容器的大小发生改变，所以array不支持以下操作。
| 操作 | 含义 |
|---|---|
| c.push_back(t)/c.emplace_back(args) | 在c尾部插入一个为t或args为初始值的元素，返回void |
| c.push_front(t)/c.emplace_front(args) | 在c头部插入一个为t或args为初始值的元素，返回void |
| c.insert(p,t)/c.emolace(p,args) | 在迭代器p指向的元素前创建一个初始值为t或args的元素，返回指向指向新元素的迭代器 |
| c.insert(p,n,t) | 在迭代器p指向的元素前创建n个初始值为t的元素，返回指向添加的第一个新元素的迭代器，若n为0则返回p |
| c.insert(p,b,e) | 将迭代器b和e指定的范围的元素插入p所指定的元素之前，b和e不能指向c中的元素，返回指向新添加的第一个元素的迭代器，若范围为空，则返回p |
| c.insert(p,il) | il为花括号包含的列表将这些值插入p所指向的值之前，返回指向新添加的第一个元素的迭代器，若范围为空，则返回p |
| c.pop_back() | 删除c中尾元素，若c为空，则函数为定义。函数返回void |
| c.pop_front() | 删除c中首元素，若c为空，则函数为定义。函数返回void |
| c.erase(p) | 删除迭代器p所指向的元素，返回一个指向删除元素之后元素的迭代器，若删除的元素为尾元素，则返回尾后迭代器，若p为尾后迭代器，则函数行为未定义 |
| c.erase(b,e) | 删除迭代器b和e所指定范围内的元素。返回一个指向最后一个被删除元素之后元素的迭代器，若e本身为尾后迭代器，则返回尾后迭代器 |
| c.clear() | 删除c中所有元素，返回void |
向一个vector，string或deque插入元素会使所有指向容器的迭代器，引用和指针失效
关联容器
关联容器支持高效的关键字查找和访问。两个主要的关联容器类型是map和set。
关联容器按字典顺序排列的。
| 容器名 | 介绍 |
|---|---|
| map | 关联数组，保存键值对 |
| set | 关联字即值，即只保存关键字的容器 |
pair
map的value_type为pair。
| 操作 | 含义 |
|---|---|
| pair<T1,T2> p | p为一个pair，两个类型分别为T1，T2的成员初始化 |
| pair<T1,T2> p(v1,v2)/pair<T1,T2> p={v1,v2} | p为一个成员类型为T1,T2的pair，first和second分别用v1，v2初始化 |
| make_pair(v1,v2) | 返回一个用v1和v2初始化的pair |
| p.first | 返回p中的first的数据成员 |
| p.second | 返回p的second的数据成员 |
| p1==p2/p1!=p1 | 当first和second分别相等时，两个pair相等 |
关联容器操作
| 操作 | 含义 |
|---|---|
| key_type | 此容器类型的关键字类型 |
| mapped_type | 每个关键字关联的类型，只适用于map |
set的迭代器是const的，可以读取元素的值，但不能修改。
增删元素
对map进行insert操作时，必须记住元素类型是pair
| 操作 | 含义 |
|---|---|
| c.insert(v)/c.emplase(args) | v为value_type类型的对象，args用来构造一个元素，当元素关键字不能插入，返回pair，其中包含一个迭代器，指向具有指定关键字的元素，以及一个指示插入是否成功的bool |
| c.insert(b,e)/c.insert(il) | b和e为迭代器，表plem一个value_type类型的范围,il为这种值的花括号列表，返回void |
| c.insert(p,v)/c.emplace(p,args) | 将迭代器·p作为一个提示，指示从哪里开始搜索新元素应该存储的位置，返回迭代器，指向具有给定关键字的元素 |
| c.erase(k) | 从c中删除每个关键字为k的元素，返回删除数据数量 |
| c.erase(p) | 从c中删除p指定的元素，p必须指向一个填充元素，返回一个指向p之后元素的迭代器，若p指向尾元素，则返回c.end() |
| c.erase(b,e) | 删除迭代器b和e所表范围中的元素，返回e |
访问元素
| c.find(k) | 返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器 |
| c.count(k) | 返回关键字为k的个数 |
参考资料
C++primer中文版(第五版) 电子工业出版社。
