Sequential Containers

提供控制元素存储和访问顺序的能力。

顺序容器概述

不同容器在以下方面都有不同的性能折中：

向容器中添加或从中删除元素的cost;
非顺序访问容器中元素的代价

vector: 可变大小数组。支持快速随机访问（快速搜索）。除了push_back之外，其他位置插入和删除元素可能很慢。
deque: 双端队列。支持快速随机访问。在头尾插入/删除很快。
list: 双向链表。只支持双向顺序访问。插入/删除元素很快。
forward_list: 单向链表。只支持单向访问。插入/删除元素很快。
array: 固定大小数组。支持快速随机访问。不能添加和删除元素。
string: 与vector类似，专门用来保存字符。随机访问快，在尾部插入删除块。

确定使用哪个容器的规则：主要考虑的两点：是否需要在中间插入或删除元素；是否需要随机访问。

除非有理由选择其他容器，优先使用vector
如果程序有很多很小的元素，且空间的额外开销很重要，则不要使用list或forward_lsit
如果程序需要在头尾插入或删除元素，但不会在中间插入或删除元素，使用deque
如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素则
- 首先确认是否真的需要在容器中间添加元素
- 如果必须在中间插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中

如果不确定使用哪种容器，可以在程序中只使用vector和list的公共操作：使用迭代器，不使用下标操作（随机访问速度不确定）。

容器库概览

顺序容器只是容器的一类。一些操作所有容器都可执行，另外一些只有顺序容器、关联容器或无序容器可用，以及一些容器特有操作。
容器均定义为模板类，大部分容器需要提供元素类型的信息。

顺序容器构造函数可以接受容器大小的参数，但当容器的元素类型不存在默认构造的函数时，可以定义一个保存这种类型对象的容器，但在构造这种容器时不能只传递一个元素数目的参数。

vector<noDefault> v1(10, init); // 正确提供了容器的初始化器。

vector<int> vec = {1, 2, 3, 4, 5};
vector<int>::iterator iter;
for(iter = vec.begin(); iter != vec.end(); ++iter)
    cout << *iter;

iterator: 迭代器
value_type: 元素类型
赋值与swap
a.swap(b) 交换a, b中的元素
swap(a,b)
添加删除
c.insert(args)将args中的元素拷贝进c
c.emplace(inits)使用inits构建c中的一个元素
c.erase(args)删除args指定的元素
c.clear()删除c中的所有元素
获取迭代器
c.begin(), c.end()
c.cbegin(), c.cend()
反向容器的额外成员（不支持forward_list）
reverse_iterator按逆序寻址元素的迭代器
const_reverse_iterator不能修改元素的逆序迭代器
c.rbegin(), c.rend()指向尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend()

迭代器

一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置。通常称为begin和end。这个范围是左闭合区间：[begin, end)

如果begin与end相等，则范围为空
如果begin与end不等，则范围至少包含一个元素，begin指向第一个元素
可以对begin递增，使得begin == end

容器类型成员

size_type, iterator, const_iterator, value_type, reverse_iterator

容器定义和初始化

将一个容器初始化为另一个容器的拷贝：整个拷贝；指定迭代器范围（除了array）
列表初始化：{‘a’, ‘b’, ‘c’}
与顺序容器大小相关的构造函数：vector ivec(10, -1);
标准库的array具有固定大小
sawp(c1, c2) / c1.swap(c2): 交换元素，比拷贝元素快得多
seq.assign(b, e): 将seq中的元素替换为b和e所表示范围内的元素，迭代器b, e不能指向seq中的元素
容器大小操作。size, empty, max_size。forward_list支持max_size和empty，但是不支持size。
每个容器都支持 == 和 !=。除了无序关联容器外的所有容器都支持>, <, >=, <=。

顺序容器操作

添加

forward有自己的insert和emplace，不支持push_back和emplace_bach。
vector和string不支持push_front和emplace_front。
push_back&push_front
emplace_back&emplace_front: 由args创建的元素进行添加
insert(p, t): 在p处插入t
insert(p, n, t): 在p之前插入n个值为t的元素，返回第一个添加的元素的指针，如果n = 0，则返回p
insert(p, b, e): 将b和e迭代器之间的元素插入到p之前
insert(p, il): 将列表il{}中的值插入到p之前

访问

c.front() & c.back(): 返回c中首元素和尾元素的引用
c[n] & c.at(n): 返回下标为n的元素的引用

删除元素

forward_list有特殊版本的erase，forward_list不支持pop_back，vector和string不支持pop_front。
pop_back & pop_front
erase(p)
erase(b, e)
clear