标准库容器是模板类型，用来保存给定类型的对象，类型几乎没有限制，在顺序容器中，元素是按顺序存放的，通过位置来访问。所有容器（除 array 外）都提供高效的动态内存管理。
顺序容器(sequential container)为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应，元素按照顺序存放，按位置来访问。
所有的顺序容器的性能不比精心设计的同类数据结构要差，所以应该多使用标准容器，而不是原始数据结构比如内置数组。

类型（六种）

如何选择？记住每种顺序容器的数据结构，理解这些数据结构的空间复杂度和查插删改的时间福再度，就知道如何选择了。
vector是数组，数组就是随机访问快，插入删除慢。
list、forward_list是链表，访问慢，插入删除快。
deque是双向队列，头尾插入删除快。

如果随机插入、随机访问的需求都要，哪个频率高，优先考虑哪个，一般都是访问远大于插删。
如果还不能确定用哪个，那用迭代器访问，避免使用下标随机访问，这样可以随时切换容器。

list<Sales_data> fuck;            // 容器都是类模板
deque<double>     fuck;            // 容器都是类模板
vector<vector<string>> lines;     // 容器的容器
//假定 noDefault 是一个没有默认构造函数的类型
vector<noDefault> v1(10, init);     // 正确：提供了元素初始化器
vector<noDefault> v2(10);             // 错误：必须提供一个元素初始化器

通用操作

顺序容器支持C++_通用容器的全部操作。
array不支持插删操作：插入、删除、resize。

插入操作

除了array，容器都是动态内存管理，插删都随时可能改变容器大小。

// 用对象初始化容器，或者插入对象，都是对象拷贝。
c.push_back(t)             // 尾部插入t，返回void    array和forward_list不支持
c.emplace_back(args)    // 同上，args创建的元素
c.emplace_back()                 // 调用元素默认构造函数
c.emplace_back("a", 1, 1.0);     // 在容器内存构建元素，参数是元素构造函数的参数
c.push_back(Elem("a", 1, 1.0));     // 先构建临时Elem，然后拷贝到容器内存中。
c.push_back("a", 1, 1.0);         // 参数错误
// 仅list、forward_list和deque支持
c.push_front(t)            // 首部插入t，返回void，
c.emplace_front(args)    // 同上，args创建的元素
c.insert(p, t)            // p元素之前插入t，返回指向插入的迭代器
c.emplace(p, args)        // 同上，args创建的元素
c.insert(p, n, t)        // p元素之前插入n个t，返回指向第一个迭代器
c.insert(p, 0, t) == p    // true
c.insert(p, b, e)        // 同上，不过是范围插入，b、e不能指向c
c.insert(p, e, e) == p    // true
c.insert(p, 初始值列表)    // 插入初始值列表
c.insert(p, {}) == p    // true

访问操作

c.back();    // 返回尾元素引用，容器空，函数未定义，forward_list不支持
c.front();    // 返回首元素引用，容器空，函数未定义
// 支持随机访问的容器：string、vector、deque、array
c[n];        // 下标n元素引用，n为size_type，越界行为未定义。
c.at(n);    // 下标n元素引用，越界out_of_range异常，多用at代替[]
auto &v1 = c.back();    // 元素的引用。
auto v2 = c.back();        // 元素的拷贝。

删除操作

array不支持插删

// forward_list不支持pop_back
c.pop_back();    // 删除c中尾元素。若c为空，则函数行为未定义。返回 void
// vector、string不支持pop_front
c.pop_front();    // 删除c中首元素。若c为空，则函数行为未定义。返回 void
// forward_list有自己的erase
c.erase(p);        // 删除迭代器 p 所指定的元素，返回一个指向被删元素之后元素的迭代器
c.erase(b, e);    // 删除迭代器 b 和 e 所指定范围内的元素。
                // 返回一个指向最后一个被删元素之后元素的迭代器
c.clear();        // 删除所有元素，返回void
//删除deque中除首尾位置之外，都会使迭代器、指针、引用失效
//vector、string删除点之后的迭代器、指针、引用都会失效
//删除前不检查元素是否存在，请确定元素存在。

resize

// resize不适用于array
// 注意，这是调整元素数量，并不是容器的空间容量。
c.resize(n);     // 调整c的size为n。如果原来超出，则删掉；如新扩充，则插入值初始化的元素
c.resize(n, t);  // 同上，新扩充的元素指定其值为t
// 如果resize缩小容器，则指向被删除元素的迭代器、引用和指针都会失效
// 对vector、string、deque进行resize可能导致迭代器、指针、引用失效。

插删（forward_list）

为什么forward_list有特殊的插入删除，这取决于单向链的数据结构特性，如下图要删除elem元素：

删除elem3后，需要elem2指向elem3之后的elem4，但是单向链表节点是无法获得前驱的，也就是无法获得elem2，C++采取了另外一种方法，那就是在elem2的时候删除elem2的下一个节点，这样需要通过后继就能做到elem2指向elem4了。插入删除操作取名insert_after、erease_after也就非常好理解了。

lst.before_begin();             // c.begin()迭代器，不能访问，仅做标记。
lst.cbefore_begin();               // const版
lst.insert_after(p, t);         // p之后插入t，返回指向t的迭代器，也就是最后一个插入元素
lst.insert_after(p, n, t);         // 范围插入：p之后插入n个t，返回p+n的迭代器，也就是最后一个插入
lst.insert_after(p, 0, t) == p    // true   
lst.insert_after(p, b, e);         // 范围插入：返回p+b-e，b、e不能指向lst
lst.insert_after(p, e, e) == p     //true
lst.insert_after(p, il);         // 范围插入：il初始化列表
lst.emplace_after(p, args);        // 构建args后插入，返回指向构建后元素的迭代器。
lst.erase_after(p);             // 删除p之后元素，返回指向被删元素之后元素的迭代器。
lst.erase_after(b,e);             // 范围删除：b，e

迭代器运算

除了支持标准库的迭代器运算，顺序容器还有特有的迭代运算。

iter + n     // 迭代器加上一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比
             // 向前移动了若干个元素，结果迭代器或者指示容器内的一个元素，或者指
             // 示容器尾元素的下一位置
iter - n     // 迭代器减去一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比
            // 向后移动了若干个元素。结果迭代器或者指示容器内的一个元素，或者指
            // 示容器尾元素的下一位置
iter += n     // 迭代器加法的复合赋值语句，将iterl 加 n 的结果赋给 iter
iter -= n     // 迭代器减法的复合赋值语句，将iterl 减 n 的结果赋给 iter
iter1 - iter2         // 两个迭代器相减的结果是它们之间的距离，也就是说，将运算符右侧的迭
                    // 代器向前移动差值个元素后将得到左侧的迭代器。参与运算的两个迭代器
                    // 必须指向的是同一个容器中的元素或者尾元素的下一位置。
                    // 返回difference_type类型，如：
                    // vector<int>::difference_type
                    // string::difference_type
// 迭代器的关系运算符
iter1 > iter2        // iter1指向的元素是否在iter2前面
>=, <, <=            // 原理同上，迭代器必须指向相同容器。       
/***************迭代器运算例子**********************/
auto mid = vi.begin () + (vi.size() >> 1);    // 中间元素迭代器
if (iter < mid)                                // 前半部分元素
// 迭代器二分搜索法，text必须是有序的
auto beg = text.begin(), end = text.end();    // 首尾迭代器
auto mid = text.begin() + (end - beg) / 2;     // 中间元素迭代器
// 当还有元素尚未检查并且我们还没有找到 sought 时执行循环
while (mid != end && *mid != sought) {    
    if(sought < *mid)                     // 我们要找的元素在前半部分吗 ？
        end = mid;                      // 如果是，调整搜索范围使得忽略掉后半部分
    else                                   // 我们要找的元素在后半部分
        beg = mid + 1 ;                 // 在m过之后寻找
        mid = beg + (end - beg ) / 2 ;     // 新的中间点
}

迭代器失效

插入、删除可能会导致当前的迭代器、引用、指针失效。访问失效的，相当于非法访问内存，这是非常严重的错误。
利用好insert、erase的返回值（迭代器），可以大大降低这种风险。
获取end迭代器很快，不要去保存它，插删基本都会让它失效。

• 插入一个元素时：
  • vector、string：
    • 发生内存重分配，全部失效
    • 没发生，插入位置之前的不失效，之后的全部失效
  • deque：
    • 插入首尾位置，迭代器失效，引用、指针不失效
    • 插入非首尾，全部失效
  • list、forward_list：
    • 全部仍然有效
• 删除一个元素：
  • 被删的肯定全部失效。
  • list、forward_list：
    • 其他全部仍然有效
  • deque：
    • 删除首元素，全部仍然有效
    • 删除尾元素，尾后失效，其他有效
    • 删除首尾之外，全部失效
  • vector、string：
    • 被删元素之前，仍然有效
    • 被删元素之后，失效

下面这个例子就利用了插删的返回值，保证了在循环中连续地插删。

// 傻瓜循环，删除偶数元素，复制每个奇数元素
vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for(auto iter = vi.begin(); iter != vi.end(); ){
    if(*iter % 2) {
        iter = vi.insert(iter, *iter);     // 在iter前面插入。
        iter += 2;                         // 指向插入之后
    } 
    else iter = vi.erase(iter);            // 指向被删元素之后的元素
}