顺序容器
一个容器就是一些特定类型对象的集合，顺序容器（sequence container） 为程序员提供了控制元素存储和访问顺序的能力。
顺序容器概述
下面列出了标准库中的顺序容器，不同容器有不同的性能折中：
- 想容器添加或从容器删除元素的代价。
- 非顺序访问容器中元素的代价。
| 容器类型 |
介绍 |
vector |
可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。 |
deque |
双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。 |
list |
双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快。 |
forward_list |
单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快。 |
array |
固定大小数组。支持快速随机访问。不能添加或者删除元素。 |
string |
与vector相似的容器，但专门用于保存字符。随机访问块。在尾部插入/删除速度快。 |
- 除了固定大小的
array 外，其他容器都提供高效、灵活的内存管理。
- 通常使用
vector 是最好的选择，除非你有很好的理由选择其他容器。
- 如果程序中有很多小的元素，且空间的额外开销很重要，则不要使用
list 或 forward_list。
- 如果程序要求随记访问元素，应使用
vector 或 deque。
- 如果程序要求在容器的中间插入或删除元素，应使用
list 或 forward_list。
- 如果程序需要再头尾位置插入或删除元素，但不会再中间位置进行操作，应使用
deque。
容器库概念
容器类型操作上形成了一种层次：
- 某些操作是所有容器类型都提供的。
- 另一些操作仅针对顺序容器、关联容器或无序容器。
类型
| 操作 |
解释 |
iterator |
此容器类型的迭代器类型 |
const_iterator |
可以读取元素但不能修改元素的迭代器类型 |
size_type |
无符号整数类型，足够保存此种容器类型最大可能的大小 |
difference_type |
带符号整数类型，足够保存两个迭代器之间的距离 |
value_type |
元素类型 |
reference |
元素的左值类型；和value_type &含义相同 |
const_reference |
元素的const左值类型，即const value_type & |
构造函数
| 操作 |
解释 |
C c; |
默认构造函数，构造空容器 |
C c1(c2);或C c1 = c2; |
构造c2的拷贝c1 |
C c(b, e) |
构造c，将迭代器b和e指定范围内的所有元素拷贝到c |
C c(a, b, c...) |
列表初始化c |
C c(n) |
只支持顺序容器，且不包括array，包含n个元素，这些元素进行了值初始化 |
C c(n, t) |
包含n个初始值为t的元素 |
- 只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
array具有固定大小。- 和其他容器不同，默认构造的
array是非空的。
- 直接复制：将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。
- 使用迭代器复制：不要求容器类型相同，容器内的元素类型也可以不同。
赋值和swap
| 操作 |
解释 |
c1 = c2; |
将c1中的元素替换成c2中的元素 |
c1 = {a, b, c...} |
将c1中的元素替换成列表中的元素（不适用于array） |
c1.swap(c2) |
交换c1和c2的元素 |
swap(c1, c2) |
等价于c1.swap(c2) |
c.assign(b, e) |
将c中的元素替换成迭代器b和e表示范围中的元素，b和e不能指向c中的元素 |
c.assign(il) |
将c中的元素替换成初始化列表il中的元素 |
c.assign(n, r) |
将c中的元素替换为n个值是t的元素 |
- 使用非成员版本的
swap是一个好习惯。
assign操作不适用于关联容器和array
大小
| 操作 |
解释 |
c.size() |
c中元素的数目（不支持forward_list） |
c.max_size() |
c中可保存的最大元素数目 |
c.empty() |
若c中存储了元素，返回false，否则返回true |
添加元素
| 操作 |
解释 |
c.push_back(t) |
在c尾部创建一个值为t的元素，返回void |
c.emplace_back(args) |
同上 |
c.push_front(t) |
在c头部创建一个值为t的元素，返回void |
c.emplace_front(args) |
同上 |
c.insert(p, t) |
在迭代器p指向的元素之前创建一个值是t的元素，返回指向新元素的迭代器 |
c.emplace(p, args) |
同上 |
c.insert(p, n, t) |
在迭代器p指向的元素之前插入n个值为t的元素，返回指向第一个新元素的迭代器；如果n是0，则返回p |
c.insert(p, b, e) |
将迭代器b和e范围内的元素，插入到p指向的元素之前；如果范围为空，则返回p |
c.insert(p, il) |
il是一个花括号包围中的元素值列表，将其插入到p指向的元素之前；如果il是空，则返回p |
- 因为这些操作会改变大小，因此不适用于
array。
forward_list有自己专有版本的insert和emplace。forward_list不支持push_back和emplace_back。- 当我们用一个对象去初始化容器或者将对象插入到容器时，实际上放入的是对象的拷贝。
emplace开头的函数是新标准引入的，这些操作是构造而不是拷贝元素。- 传递给
emplace的参数必须和元素类型的构造函数相匹配。
访问元素
| 操作 |
解释 |
c.back() |
返回c中尾元素的引用。若c为空，函数行为未定义 |
c.front() |
返回c中头元素的引用。若c为空，函数行为未定义 |
c[n] |
返回c中下标是n的元素的引用，n时候一个无符号证书。若n>=c.size()，则函数行为未定义 |
c.at(n) |
返回下标为n的元素引用。如果下标越界，则抛出out_of_range异常 |
- 访问成员函数返回的是引用。
at和下标操作只适用于string、vector、deque、array。back不适用于forward_list。- 如果希望下标是合法的，可以使用
at函数。
删除元素
| 操作 |
解释 |
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 |
- 会改变容器大小，不适用于
array。
forward_list有特殊版本的eraseforward_list不支持pop_backvector和string不支持pop_front
特殊的 forwad_list操作
- 链表在删除元素时需要修改前置节点的内容，双向链表会前驱的指针，但是单向链表没有保存，因此需要增加获取前置节点的方法。
forward_list定义了before_begin，即首前（off-the-begining）迭代器，允许我们再在首元素之前添加或删除元素。
| 操作 |
解释 |
lst.before_begin() |
返回指向链表首元素之前不存在的元素的迭代器，此迭代器不能解引用。 |
lst.cbefore_begin() |
同上，但是返回的是常量迭代器。 |
lst.insert_after(p, t) |
在迭代器p之后插入元素。t是一个对象 |
lst.insert_after(p, n, t) |
在迭代器p之后插入元素。t是一个对象，n是数量。若n是0则函数行为未定义 |
lst.insert_after(p, b, e) |
在迭代器p之后插入元素。由迭代器b和e指定范围。 |
lst.insert_after(p, il) |
在迭代器p之后插入元素。由il指定初始化列表。 |
emplace_after(p, args) |
使用args在p之后的位置，创建一个元素，返回一个指向这个新元素的迭代器。若p为尾后迭代器，则函数行为未定义。 |
lst.erase_after(p) |
删除p指向位置之后的元素，返回一个指向被删元素之后的元素的迭代器，若p指向lst的尾元素或者是一个尾后迭代器，则函数行为未定义。 |
lst.erase_after(b, e) |
类似上面，删除对象换成从b到e指定的范围。 |
改变容器大小
| 操作 |
解释 |
c.resize(n) |
调整c的大小为n个元素，若n<c.size()，则多出的元素被丢弃。若必须添加新元素，对新元素进行值初始化 |
c.resize(n, t) |
调整c的大小为n个元素，任何新添加的元素都初始化为值t |
获取迭代器
| 操作 |
解释 |
c.begin(), c.end() |
返回指向c的首元素和尾元素之后位置的迭代器 |
c.cbegin(), c.cend() |
返回const_iterator |
- 以
c开头的版本是C++11新标准引入的
- 当不需要写访问时，应该使用
cbegin和cend。
反向容器的额外成员
| 操作 |
解释 |
reverse_iterator |
按逆序寻址元素的迭代器 |
const_reverse_iterator |
不能修改元素的逆序迭代器 |
c.rbegin(), c.rend() |
返回指向c的尾元素和首元素之前位置的迭代器 |
c.crbegin(), c.crend() |
返回const_reverse_iterator |
