2021-11-04 《C++ Primer》学习记录：第9章（1）

第 9 章 顺序容器 9.1 顺序容器概述

顺 序 容 器 类 型 vector 可变大小数组。支持快速随机访向。 在尾部之外的位置插入或删除元素可能很慢 deque 双端队列。支持快速随机访问。 在头尾位置插入/删除速度很快 list 双向链表。只支持双向顺序访问。 在 list 中任何位置进行插入/删除操作速度都很快 forward_list 单向链表。只支持单向顺序访问。 在链表任何位置进行插入/删除操作速度都很快 array 固定大小数组。支持快速随机访问。 不能添加或删除元素 string 与 vector 相似的容器，但专门用于保存字符。随机访问快。 在尾部插入/删除速度快 \begin{array}{c} \hline \bold{顺序容器类型}\\ \hline \begin{array}{l l} \text{vector} & \text{可变大小数组。支持快速随机访向。}\\ & \text{在尾部之外的位置插入或删除元素可能很慢}\\ \\ \text{deque} & \text{双端队列。支持快速随机访问。}\\ & \text{在头尾位置插入/删除速度很快}\\ \\ \text{list} & \text{双向链表。只支持双向顺序访问。}\\ & \text{在 list 中任何位置进行插入/删除操作速度都很快}\\ \\ \text{forward\_list} & \text{单向链表。只支持单向顺序访问。}\\ & \text{在链表任何位置进行插入/删除操作速度都很快}\\ \\ \text{array} & \text{固定大小数组。支持快速随机访问。}\\ & \text{不能添加或删除元素}\\ \\ \text{string} & \text{与 vector 相似的容器，但专门用于保存字符。随机访问快。}\\ & \text{在尾部插入/删除速度快} \end{array}\\ \hline \end{array} 顺序容器类型vectordequelistforward_listarraystring​可变大小数组。支持快速随机访向。在尾部之外的位置插入或删除元素可能很慢双端队列。支持快速随机访问。在头尾位置插入/删除速度很快双向链表。只支持双向顺序访问。在 list 中任何位置进行插入/删除操作速度都很快单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快固定大小数组。支持快速随机访问。不能添加或删除元素与 vector 相似的容器，但专门用于保存字符。随机访问快。在尾部插入/删除速度快​​​

• vector、string
  • 元素保存在连续的内存空间中
  • 支持随机访问
  • 在容器的中间位置添加 / 删除元素非常耗时，需要移动后面的所有元素
• list、forward_list
  • 容器中任何位置的添加 / 删除操作都很快速
  • 不支持随机访问
  • 额外内存开销大
  • forward_list 的设计目标是达到与最好的手写单向链表数据结构相当的性能，没有 size() 操作，而其他的顺序容器都有，并且 size() 是一个快速常量时间的操作
• deque
  • 在中间位置添加或删除元素的代价很高
  • 支持随机访问
• array
  • 一种更安全、更容易使用的数组类型

​ 新标准库的容器比旧版本快得多（因为移动语义的出现，第 13.6 节）。现代 C++ 程序应该使用标准库容器，而不是更原始的数据结构，如内置数组。

（1）确定使用那种顺序容器

• 除非有很好的理由选择其它容器。否则使用 vector
• 有很多小的元素，并且空间的额外开销很重要。则不要使用 list 或 forward_list
• 要求随机访问。则使用 vector 或 deque
• 要求在容器的中间插入 / 删除元素。则使用 list 或 forward_list
• 需要在头尾位置插入元素，但不会在中间位置进行插入 / 删除操作。则使用 deque
• 如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
  • 可以使用 vector 保存数据，最后使用 sort() 重排元素
  • 如果必须在中间位置插入元素，可以考虑在输入阶段使用 list，输入完成后拷贝到 vector 中

9.2 容器共有的操作

容 器 操 作 类 型 别 名 iterator 此容器的迭代器类型 const_iterator 可以读取元素，但不能修改元素的迭代器类型 size_type 无符号整数类型，足以保存容器中最大可能的元素个数 differnce_type 带符号整数类型，足以保存两个迭代器之间的距离 value_type 元素类型 reference 元素的左值类型；即 value_type& const_reference 元素的 const 左值类型，即 const value_type& 构 造 函 数 C c; 默认构造函数，构造空容器 C c1(c2); 构造 c2 的拷贝 c1 C c(b, e); 构造 c，将迭代器 b 和 e 指定范围内的元素拷贝到 c C c{a, b, c...} 列表初始化 c 赋 值 与 s w a p c1 = c2 将 c1 中的元素替换为 c2 中的元素 c1 = {a, b, c...} 将 c1 中的元素替换为列表中的元素（array 不适用） a.swap(b) 交换 a 和 b 的元素 swap(a, b) 与上面等价 大 小 c.size() c 中的元素数目（forward_list 不适用） c.max_size() c 可保存的最大元素数目 c.empty() 若 c 中存储了元素，返回 false，否则返回 true 添 加 / 删 除 元 素 （array 不适用） c.insert( a r g s ) 将  a r g s  中的元素拷贝进 c c.emplace( i n i t s ) 使用  i n i t s  构造 c 中的一个元素 c.erase( a r g s ) 删除  a r g s  指定的元素 c.clear() 删除 c 中所有元素，返回 void 关 系 运 算 符 ==, != 所有容器都支持相等/不等运算符 = 关系运算符（无序关联容器不支持） 获 取 迭 代 器 c.begin(), c.end() 返回指向 c 的首元素和尾元素之后位置的迭代器 c.cbegin(), c,cend() 返回上述迭代器的 const 版本 反 向 容 器 的 额 外 成 员 （forward_list 不支持） reverse_iterator 按逆序寻址元素的迭代器 cont_reverse_iterator 不能修改元素的逆序迭代器 c.rbegin(), c.rend() 返回指向 c 的尾元素和首元素之前位置的迭代器 c.crbegin(), c.crend() 返回 cont_reverse_iterator \begin{array}{c} \hline \bold{容器操作}\\ \hline \begin{array}{l l} \bold{类型别名} & \\ \text{iterator} & \text{此容器的迭代器类型}\\ \text{const\_iterator} & \text{可以读取元素，但不能修改元素的迭代器类型}\\ \text{size\_type} & \text{无符号整数类型，足以保存容器中最大可能的元素个数}\\ \text{differnce\_type} & \text{带符号整数类型，足以保存两个迭代器之间的距离}\\ \text{value\_type} & \text{元素类型}\\ \text{reference} & \text{元素的左值类型；即 value\_type\&}\\ \text{const\_reference} & \text{元素的 const 左值类型，即 const value\_type\&}\\ \\ \bold{构造函数} & \\ \text{C c;} & \text{默认构造函数，构造空容器}\\ \text{C c1(c2);} & \text{构造 c2 的拷贝 c1}\\ \text{C c(b, e);} & \text{构造 c，将迭代器 b 和 e 指定范围内的元素拷贝到 c}\\ \text{C c\{a, b, c...\}} & \text{列表初始化 c}\\ \\ \bold{赋值与 swap} & \\ \text{c1 = c2} & \text{将 c1 中的元素替换为 c2 中的元素}\\ \text{c1 = \{a, b, c...\}} & \text{将 c1 中的元素替换为列表中的元素（array 不适用）}\\ \text{a.swap(b)} & \text{交换 a 和 b 的元素}\\ \text{swap(a, b)} & \text{与上面等价}\\ \\ \bold{大小} & \\ \text{c.size()} & \text{c 中的元素数目（forward\_list 不适用）}\\ \text{c.max\_size()} & \text{c 可保存的最大元素数目}\\ \text{c.empty()} & \text{若 c 中存储了元素，返回 false，否则返回 true}\\ \\ \bold{添加 / 删除元素} & \\ \text{（array 不适用）}\\ \text{c.insert(}args\text{)} & \text{将 }args\text{ 中的元素拷贝进 c}\\ \text{c.emplace(}inits\text{)} & \text{使用 }inits\text{ 构造 c 中的一个元素}\\ \text{c.erase(}args\text{)} & \text{删除 }args\text{ 指定的元素}\\ \text{c.clear()} & \text{删除 c 中所有元素，返回 void}\\ \\ \bold{关系运算符} & \\ \text{==, !=} & \text{所有容器都支持相等/不等运算符}\\ \text{=} & \text{关系运算符（无序关联容器不支持）}\\ \\ \bold{获取迭代器} & \\ \text{c.begin(), c.end()} & \text{返回指向 c 的首元素和尾元素之后位置的迭代器}\\ \text{c.cbegin(), c,cend()} & \text{返回上述迭代器的 const 版本}\\ \\ \bold{反向容器的额外成员} & \\ \text{（forward\_list 不支持）}\\ \text{reverse\_iterator} & \text{按逆序寻址元素的迭代器}\\ \text{cont\_reverse\_iterator} & \text{不能修改元素的逆序迭代器}\\ \text{c.rbegin(), c.rend()} & \text{返回指向 c 的尾元素和首元素之前位置的迭代器}\\ \text{c.crbegin(), c.crend()} & \text{返回 cont\_reverse\_iterator}\\ \end{array}\\ \hline \end{array} 容器操作类型别名iteratorconst_iteratorsize_typediffernce_typevalue_typereferenceconst_reference构造函数C c;C c1(c2);C c(b, e);C c{a, b, c...}赋值与swapc1 = c2c1 = {a, b, c...}a.swap(b)swap(a, b)大小c.size()c.max_size()c.empty()添加/删除元素（array 不适用）c.insert(args)c.emplace(inits)c.erase(args)c.clear()关系运算符==, !==获取迭代器c.begin(), c.end()c.cbegin(), c,cend()反向容器的额外成员（forward_list 不支持）reverse_iteratorcont_reverse_iteratorc.rbegin(), c.rend()c.crbegin(), c.crend()​此容器的迭代器类型可以读取元素，但不能修改元素的迭代器类型无符号整数类型，足以保存容器中最大可能的元素个数带符号整数类型，足以保存两个迭代器之间的距离元素类型元素的左值类型；即 value_type&元素的 const 左值类型，即 const value_type&默认构造函数，构造空容器构造 c2 的拷贝 c1构造 c，将迭代器 b 和 e 指定范围内的元素拷贝到 c列表初始化 c将 c1 中的元素替换为 c2 中的元素将 c1 中的元素替换为列表中的元素（array 不适用）交换 a 和 b 的元素与上面等价c 中的元素数目（forward_list 不适用）c 可保存的最大元素数目若 c 中存储了元素，返回 false，否则返回 true将 args 中的元素拷贝进 c使用 inits 构造 c 中的一个元素删除 args 指定的元素删除 c 中所有元素，返回 void所有容器都支持相等/不等运算符关系运算符（无序关联容器不支持）返回指向 c 的首元素和尾元素之后位置的迭代器返回上述迭代器的 const 版本按逆序寻址元素的迭代器不能修改元素的逆序迭代器返回指向 c 的尾元素和首元素之前位置的迭代器返回 cont_reverse_iterator​​​

9.2.1 迭代器

（1）所有容器迭代器支持的操作 标 准 容 器 迭 代 器 的 运 算 符 *iter 返回迭代器 iter 所指元素的引用 iter —> mem 解引用 iter 并获取该元素的名为 mem 的成员，等价于 (*iter).mem + + iter 令 iter 指示容器中的下一个元素 − − iter 令 iter 指示容器中的上一个元素（forward_list 迭代器不支持） iter1 == iter2 判断两个迭代器是否相等，如果两个迭代器指示的是同一个元素 iter1 != iter2 或者它们是同一个容器的尾后迭代器，则相等；反之，不相等 \begin{array}{c} \hline \bold{标准容器迭代器的运算符}\\ \hline \begin{array}{l l} \text{*iter} & \text{返回迭代器 iter 所指元素的引用}\\ \text{iter —> mem} & \text{解引用 iter 并获取该元素的名为 mem 的成员，等价于 (*iter).mem}\\ ++\text{iter} & \text{令 iter 指示容器中的下一个元素}\\ --\text{iter} & \text{令 iter 指示容器中的上一个元素（forward\_list 迭代器不支持）}\\ \text{iter1 == iter2} & \text{判断两个迭代器是否相等，如果两个迭代器指示的是同一个元素}\\ \text{iter1 != iter2} & \text{或者它们是同一个容器的尾后迭代器，则相等；反之，不相等} \end{array}\\ \hline \end{array} 标准容器迭代器的运算符*iteriter —> mem++iter−−iteriter1 == iter2iter1 != iter2​返回迭代器 iter 所指元素的引用解引用 iter 并获取该元素的名为 mem 的成员，等价于 (*iter).mem令 iter 指示容器中的下一个元素令 iter 指示容器中的上一个元素（forward_list 迭代器不支持）判断两个迭代器是否相等，如果两个迭代器指示的是同一个元素或者它们是同一个容器的尾后迭代器，则相等；反之，不相等​​​

（2）部分顺序容器迭代器支持的操作 v e c t o r 和 s t r i n g 迭 代 器 支 持 的 运 算 iter + n 迭代器加上一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比 向前移动了若干个元素。结果迭代器或者指示容器内的一个元素，或者指 示容器尾元素的下一位置。 iter － n 迭代器减去一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比 向后移动了若干个元素。结果迭代器或者指示容器内的一个元素，或者指 示容器尾元素的下一位置。 iter1 += n 迭代器加法的复合赋值语句，将 iter1 加 n 的结果赋给 iter1 iter1 －= n 迭代器减法的复合赋值语句，将 iter1 减 n 的结果赋给 iter1 iter1 － iter2 两个迭代器相减的结果是它们之间的距离，也就是说，将运算符右侧的迭 代器向前移动差值个元素后将得到左侧的迭代器。参与运算的两个迭代器 必须指向的是同一个容器中的元素或者尾元素的下一位置。 >, >=, =, =, =, word) iter = lst.insert(iter, word); // 等价于调用 push_front()

（3）使用 emplace 操作

​ 当调用 push() 或 insert() 成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个 emplace() 成员函数时，则是将参数传递给元素类型的构造函数。emplace() 成员使用这些参数在容器管理的内存空间中直接构造元素。例如：

// 在 c 的末尾构造一个 Sales_data 对象
// 使用三个参数的 Sales_data 构造函数
c.emplace_back("978-0590353403", 25, 15.99);
// 错误：没有接受三个参数的 push_back 版本
c.push_back("978-0590353403", 25, 15.99);
// 正确：创建一个临时的 Sales_data 对象传递给 push_back 
c.push_back(Sales_data("978-0590353403", 25, 15.99));

c.emplace_back();      // 使用 Sales_data 的默认构造函数

​ 调用 emplace_back() 时，会在容器管理的内存空间中直接创建对象。

​ 调用 push_back() 则会创建一个局部临时对象，并将其压入容器中。

9.3.2 访问元素

在 顺 序 容 器 中 访 问 元 素 的 操 作 c.back() 返回 c 中尾元素的引用。若 c 为空，函数行为未定义。 c.front() 返回 c 中尾元素的引用。若 c 为空，函数行为未定义。 c[n] 返回 c 中下标为 n 的元素的引用，n 为无符号整数。 若 n >= c.size()，函数行为未定义 c.at(n) 返回下标为 n 的元素的引用。 若下标越界，则抛出 out_of_range 异常 \begin{array}{c} \hline \bold{在顺序容器中访问元素的操作}\\ \hline \begin{array}{l l} \text{c.back()} & \text{返回 c 中尾元素的引用。若 c 为空，函数行为未定义。}\\ \\ \text{c.front()} & \text{返回 c 中尾元素的引用。若 c 为空，函数行为未定义。}\\ \\ \text{c[n]} & \text{返回 c 中下标为 n 的元素的引用，n 为无符号整数。}\\ & \text{若 n >= c.size()，函数行为未定义}\\ \\ \text{c.at(n)} & \text{返回下标为 n 的元素的引用。}\\ & \text{若下标越界，则抛出 out\_of\_range 异常}\\ \end{array}\\ \hline \end{array} 在顺序容器中访问元素的操作c.back()c.front()c[n]c.at(n)​返回 c 中尾元素的引用。若 c 为空，函数行为未定义。返回 c 中尾元素的引用。若 c 为空，函数行为未定义。返回 c 中下标为 n 的元素的引用，n 为无符号整数。若 n >= c.size()，函数行为未定义返回下标为 n 的元素的引用。若下标越界，则抛出 out_of_range 异常​​​

​ 包括 array 在内的每个顺序容器都有一个 front() 成员函数，而除 forward_list 之外的所有顺序容器都有一个 back() 成员函数。这两个操作分别返回首元素和尾元素的引用。

​ at() 和下标操作只适用于 string、vector、deque 和 array。

（1）访问成员函数返回的是引用

​ 在容器中访问元素的成员函数返回的都是引用。如果使用 auto 变量来保存函数的返回值，注意引用和非引用的区别：

if (!c.empty()) {
    c.front() = 42;
    auto &v = c.back();       // 获得引用
    v = 1024;                 // 改变 c 中的元素
    auto v2 = c.back();       // 获得拷贝
    v2 = 0;                   // 未改变 c 中的元素
}

（2）下标操作和安全的随机访问

​ 下标运算符并不检查下标是否在合法范围内，编译器也并不检查这种错误。

​ 如果希望确保下标是合法的，可以使用 at() 成员函数，在下标越界时会抛出异常。

9.3.3 删除元素

顺 序 容 器 的 删 除 操 作 c.pop_back() 删除 c 中尾元素。若 c 为空，函数行为未定义。函数返回 void c.pop_front() 删除 c 中首元素。若 c 为空，函数行为未定义。函数返回 void c.erase(p) 删除迭代器 p 所指定的元素，返回指向其后面的元素的迭代器。 若 p 指向尾元素，则返回尾后迭代器； 若 p 为尾后迭代器，则函数行为未定义； c.erase(b, e) 删除迭代器 b 和 e 所指定范围内的元素，返回指向该区间后面 一个元素的迭代器，即 e。 若 e 为尾后迭代器，函数也返回尾后迭代器 c.clear() 删除 c 中的所有元素，返回 void \begin{array}{c} \hline \bold{顺序容器的删除操作}\\ \hline \begin{array}{l l} \text{c.pop\_back()} & \text{删除 c 中尾元素。若 c 为空，函数行为未定义。函数返回 void}\\ \\ \text{c.pop\_front()} & \text{删除 c 中首元素。若 c 为空，函数行为未定义。函数返回 void}\\ \\ \text{c.erase(p)} & \text{删除迭代器 p 所指定的元素，返回指向其后面的元素的迭代器。}\\ & \text{若 p 指向尾元素，则返回尾后迭代器；}\\ & \text{若 p 为尾后迭代器，则函数行为未定义；}\\ \\ \text{c.erase(b, e)} & \text{删除迭代器 b 和 e 所指定范围内的元素，返回指向该区间后面}\\ & \text{一个元素的迭代器，即 e。}\\ & \text{若 e 为尾后迭代器，函数也返回尾后迭代器}\\ \\ \text{c.clear()} & \text{删除 c 中的所有元素，返回 void}\\ \end{array}\\ \hline \end{array} 顺序容器的删除操作c.pop_back()c.pop_front()c.erase(p)c.erase(b, e)c.clear()​删除 c 中尾元素。若 c 为空，函数行为未定义。函数返回 void删除 c 中首元素。若 c 为空，函数行为未定义。函数返回 void删除迭代器 p 所指定的元素，返回指向其后面的元素的迭代器。若 p 指向尾元素，则返回尾后迭代器；若 p 为尾后迭代器，则函数行为未定义；删除迭代器 b 和 e 所指定范围内的元素，返回指向该区间后面一个元素的迭代器，即 e。若 e 为尾后迭代器，函数也返回尾后迭代器删除 c 中的所有元素，返回 void​​​

​ 删除 deque 中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。

​ 指向 vector 或 string中删除点之后位置的迭代器、引用和指针都会失效。

（1）erase 返回值的使用

​ 下面的循环删除一个 list 中所有的奇数元素：

list lst = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto it = lst.begin();
while (it != lst.end()) {
    if (*it % 2)              // 如果为奇数
        it = lst.erase(it);   // 删除
    else ++it;
}

9.3.4 特殊的 forward_list 操作

​ 因为单向链表数据结构的特殊性，forward_list 将通常的操作进行了以下的改名：

• insert -->insert_after
• emplace -->emplace_after
• erase -->erase_after

​ 同时，forward_list 定义了 before_begin() 操作，返回一个首前迭代器，来达到其他容器操作的等价效果： 在 f o r w a r d _ l i s t 中 插 入 或 删 除 元 素 的 操 作 lst.before_begin() 返回指向链表首元素之前不存在的元素迭代器。该迭代器 lst.before_cbegin() 不能解引用。cbefore_begin() 返回 const 版本 lst.insert_after(p, t) 在迭代器 p 之后的位置插入元素。t 为对象，n 为数量； lst.insert_after(p, n, t) b 和 e 为表示范围的一对迭代器，il 为一个花括号列表； lst.insert_after(p, b, e) 如果范围是空，则返回 p； lst.insert_after(p, il) 如果 p 为尾后迭代器，则函数行为未定义 emplace_after(p,  a r g s ) 使用  a r g s  在 p 指定的位置之后创建一个元素。返回一个 指向这个新元素的迭代器。 若 p 为尾后迭代器，则函数行为未定义 lst.erase_after(p) 删除 p 指向的位置之后的元素，或删除从 b 之后直到（不 lst.erase_after(b, e) 包含）e 之间的元素。返回一个指向被删除元素之后元素的 迭代器。 若不存在这样的元素，则返回尾后迭代器； 若 p 指向 lst 的尾元素或者尾后迭代器，则函数行为未定义 \begin{array}{c} \hline \bold{在 forward\_list 中插入或删除元素的操作}\\ \hline \begin{array}{l l} \text{lst.before\_begin()} & \text{返回指向链表首元素之前不存在的元素迭代器。该迭代器}\\ \text{lst.before\_cbegin()} & \text{不能解引用。cbefore\_begin() 返回 const 版本}\\ \\ \text{lst.insert\_after(p, t)} & \text{在迭代器 p 之后的位置插入元素。t 为对象，n 为数量；}\\ \text{lst.insert\_after(p, n, t)} & \text{b 和 e 为表示范围的一对迭代器，il 为一个花括号列表；}\\ \text{lst.insert\_after(p, b, e)} & \text{如果范围是空，则返回 p；}\\ \text{lst.insert\_after(p, il)} & \text{如果 p 为尾后迭代器，则函数行为未定义}\\ \\ \text{emplace\_after(p, }args\text{)} & \text{使用 }args \text{ 在 p 指定的位置之后创建一个元素。返回一个}\\ & \text{指向这个新元素的迭代器。}\\ & \text{若 p 为尾后迭代器，则函数行为未定义}\\ \\ \text{lst.erase\_after(p)} & \text{删除 p 指向的位置之后的元素，或删除从 b 之后直到（不}\\ \text{lst.erase\_after(b, e)} & \text{包含）e 之间的元素。返回一个指向被删除元素之后元素的}\\ & \text{迭代器。}\\ & \text{若不存在这样的元素，则返回尾后迭代器；}\\ & \text{若 p 指向 lst 的尾元素或者尾后迭代器，则函数行为未定义}\\ \end{array}\\ \hline \end{array} 在forward_list中插入或删除元素的操作lst.before_begin()lst.before_cbegin()lst.insert_after(p, t)lst.insert_after(p, n, t)lst.insert_after(p, b, e)lst.insert_after(p, il)emplace_after(p, args)lst.erase_after(p)lst.erase_after(b, e)​返回指向链表首元素之前不存在的元素迭代器。该迭代器不能解引用。cbefore_begin() 返回 const 版本在迭代器 p 之后的位置插入元素。t 为对象，n 为数量；b 和 e 为表示范围的一对迭代器，il 为一个花括号列表；如果范围是空，则返回 p；如果 p 为尾后迭代器，则函数行为未定义使用 args 在 p 指定的位置之后创建一个元素。返回一个指向这个新元素的迭代器。若 p 为尾后迭代器，则函数行为未定义删除 p 指向的位置之后的元素，或删除从 b 之后直到（不包含）e 之间的元素。返回一个指向被删除元素之后元素的迭代器。若不存在这样的元素，则返回尾后迭代器；若 p 指向 lst 的尾元素或者尾后迭代器，则函数行为未定义​​​ ​ 使用 forward_list 实现上一小节的目标时，需要使用两个迭代器——一个指向要处理的元素，另一个指向其前趋：

forward_list flst = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto prev = flst.before_begin();        // flst 的首前元素
auto curr = flst.begin();               // flst 的第一个元素
while (curr != flst.end()) {            // 仍有元素要处理
    if (*curr % 2)                      // 若元素为奇数
        curr = flst.erase_after(prev);  // 删除并移动 curr
    else {
        prev = curr;                    // prev 指向 curr 移动后的前一个元素
        ++curr;                         // 移动 curr
    }
}

9.3.5 改变容器大小

​ 可以使用 resize() 来增大或缩小容器：

• 如果当前大小大于所要求的大小，容器后部的元素会被删除；
• 如果当前大小小于所要求的大小，会将新元素添加到容器后部。

list ilist(10, 42);    // 10 个 int，每个都为 42
ilist.resize(15);           // 将 5 个值为 0 的元素添加到 ilist 的末尾
ilist.resize(25, -1);       // 将 10 个值为 -1 的元素添加到 ilist 的末尾
ilist.resize(5);            // 从 ilist 末尾删除 20 个元素

顺 序 容 器 大 小 操 作 c.resize(n) 调整 c 的大小为 n 个元素 c.resize(n, t) 调整 c 的大小为 n 个元素。任何新添加的元素都初始化为 t \begin{array}{c} \hline \bold{顺序容器大小操作}\\ \hline \begin{array}{l l} \text{c.resize(n)} & \text{调整 c 的大小为 n 个元素}\\ \text{c.resize(n, t)} & \text{调整 c 的大小为 n 个元素。任何新添加的元素都初始化为 t} \end{array}\\ \hline \end{array} 顺序容器大小操作c.resize(n)c.resize(n, t)​调整 c 的大小为 n 个元素调整 c 的大小为 n 个元素。任何新添加的元素都初始化为 t​​​

​ 如果 resize() 缩小容器，则指向被删除元素的迭代器、引用和指针都会失效；

​ 对 vector、string 或 deque 进行 resize() 可能导致迭代器、指针和引用失效。

9.3.6 容器操作可能使迭代器失效

• 在向容器添加元素后：

  • vector、string：

    1）存储空间被重新分配。

    ​ 则指向容器的迭代器、指针和引用都会失效。

    2）存储空间未重新分配。

    ​ 指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。

  • deque：

    插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。

  • list、forward_list：

    指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。

• 删除一个元素后：

  • list、forward list：

    指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。

  • deque：

    1）在首尾之外的任何位置删除元素。

    ​ 指向被删除元素外其他元素的迭代器、引用或指针也会失效。

    2）删除 deque 的首 / 尾元素。

    ​ 首前 / 尾后迭代器会失效，但其他迭代器、引用和指针不受影响。

  • vector、string：

    指向被删元素之前元素的迭代器、引用和指针仍有效。

    注意∶当我们删除元素时，尾后迭代器总是会失效。

（1）使用 insert() 和 erase() 的返回值更新迭代器

// 傻瓜循环，删除偶数元素，复制每个奇数元素
vector vi = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto iter = vi.begin());      // 调用 begin() 而不是 cbegin()，因为我们要改变 vi 
while(iter != vi.end()) {
    if (*iter % 2){
        iter = vi.insert(iter, *iter);    // 复制当前元素
        iter += 2;            // 向前移动迭代器，跳过当前元素以及插入到它之前的元素
        else
            iter = vi.erase (iter);       // 删除偶数元素
            // 不应向前移动迭代器，iter 指向我们删除的元素之后的元素
    }
}

（2）不要保存 end() 返回的尾后迭代器

​ 当我们添加 / 删除 vector 或 string 的元素后，或在 deque 中首元素之外任何位置添加 / 删除元素后，原来 end() 返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用 end()，而不能在循环之前保存 end() 返回的迭代器，一直当作容器末尾使用。

​ 通常 C++ 标准库的实现中 end() 操作都很快，部分就是因为这个原因。

9.4 容器适配器

​ 除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue 和priority_queue。容器、迭代器和函数都有适配器。

​ 一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。例如，stack 适配器接受一个顺序容器（除 array 或 forward_list 外），并使其操作起来像一个 stack 一样。 所 有 容 器 适 配 器 都 支 持 的 操 作 和 类 型 size_type 一种类型，足以保存当前类型的最大对象的大小 value_type 元素类型 container_type 实现适配器的底层容器类型 A a; 创建一个名为 a 的空适配器 A a(c); 创建一个名为 a 的适配器，带有容器 c 的一个拷贝 关系运算符 每个适配器都支持所有关系运算符（6 个） a.empty() 若 a 包含任何元素，返回 false；否则返回 true a.size() 返回 a 中的数目 swap(a, b) 交换 a 和 b 的内容，a 和 b 必须具有相同的类型 a.swap(b) 底层容器类型也必须相同 \begin{array}{c} \hline \bold{所有容器适配器都支持的操作和类型}\\ \hline \begin{array}{l l} \text{size\_type} & \text{一种类型，足以保存当前类型的最大对象的大小}\\ \text{value\_type} & \text{元素类型}\\ \text{container\_type} & \text{实现适配器的底层容器类型}\\ \text{A a;} & \text{创建一个名为 a 的空适配器}\\ \text{A a(c);} & \text{创建一个名为 a 的适配器，带有容器 c 的一个拷贝}\\ \text{关系运算符} & \text{每个适配器都支持所有关系运算符（6 个）}\\ \text{a.empty()} & \text{若 a 包含任何元素，返回 false；否则返回 true}\\ \text{a.size()} & \text{返回 a 中的数目}\\ \text{swap(a, b)} & \text{交换 a 和 b 的内容，a 和 b 必须具有相同的类型}\\ \text{a.swap(b)} & \text{底层容器类型也必须相同}\\ \end{array}\\ \hline \end{array} 所有容器适配器都支持的操作和类型size_typevalue_typecontainer_typeA a;A a(c);关系运算符a.empty()a.size()swap(a, b)a.swap(b)​一种类型，足以保存当前类型的最大对象的大小元素类型实现适配器的底层容器类型创建一个名为 a 的空适配器创建一个名为 a 的适配器，带有容器 c 的一个拷贝每个适配器都支持所有关系运算符（6 个）若 a 包含任何元素，返回 false；否则返回 true返回 a 中的数目交换 a 和 b 的内容，a 和 b 必须具有相同的类型底层容器类型也必须相同​​​ ​ 默认情况下，下面三种适配器的底层容器为：

• stack：deque
• queue：deque
• priority_queue：vector