9.1 顺序容器概述

所有顺序容器都提供了快速顺序访问元素的能力。但是，这些容器在以下方面都有不同的性能折中：

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

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

string 和 vector 将元素保存在连续的内存空间中。 由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在这两种容器的中间位置添加或删除元素就会非常耗时：在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储。而且，添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必须移动到新的存储空间中。

list 和 forward_list 两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问：为了访问一个元素，我们只能遍历整个容器。而且，与vector、deque 和 array 相比，这两个容器的额外内存开销也很大。

deque是一个更为复杂的数据结构。与 string 和 vector 类似，deque 支持快速的随机访问。与 string 和 vector 一样，在 deque 的中间位置添加或删除元素的代价（可能）很高。但是，在 deque 的两端添加或删除元素都是很快的，与 list 或 forward_list 添加删除元素的速度相当。forward_list 和 array 是新 C++ 标准增加的类型。与内置数组相比，array 是一种更安全、更容易使用的数组类型。与内置数组类似，array 对象的大小是固定的。因此，array 不支持添加和删除元素以及改变容器大小的操作。

forward_list 的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list 没有 size 操作，因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言，size 保证是一个快速的常量时间的操作。

最佳实践：如果你不确定应该使用哪种容器，那么可以在程序中只使用 vector 和 list 公共的操作：使用迭代器，不使用下标操作，避免随机访问。这样，在必要时选择使用 vector 或 list 都很方便。

Tip：通常，使用 vector 是最好的选择。
如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
- 首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向 vector 追加数据，然后再调用标准库的 sort 函数来重排容器中的元素，从而避免在中间位置添加元素。
- 如果必须在中间位置插入元素，考虑在输入阶段使用 1ist，一旦输入完成，将 list 中的内容拷贝到一个 vector 中。

9.2 容器库概览

容器均定义为模板类，必须提供额外信息来生成特定的容器类型。
Note：较旧的编译器可能需要在两个尖括号之间键入空格，例如，vector<vector<string> >。

顺序容器构造函数的一个版本接受容器大小参数，它使用了元素类型的默认构造函数。但某些类没有默认构造函数。我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数：

1
2
3

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

常用容器操作：

容器操作
类型别名
iterator	此容器类型的迭代器类型
const_iterator	可以读取元素，但不能修改元素的迭代器类型
size_type	无符号整数类型，足够保存此种容器类型最大可能容器的大小
difference_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（array 不支持）
C c{a, b, c...};	列表初始化 c
赋值与 swap
c1 = c2	将 c1 中的元素替换为 c2 中元素
c1 = {a, b, c...}	将 c1 中的元素替换为列表中元素（不适用于 array）
a.swap(b)	交换 a 和 b 的元素
swap(a,b)	与 a.swap(b) 等价
大小
c.size()	c 中元素的数目（不支持 forward_list）
c.max_size()	c 可保存的最大元素数目
c.empty()	若 c 中存储了元素，返回 false，否则返回 true
添加/删除元素（不适用于 array）注：在不同容器中，这些操作的接口都不同
c.insert(args)	将 args 中的元素拷贝进 c
c.emplace(inits)	使用 inits 构造 c 中的一个元素
c.erase(args)	删除 args 指定的元素
c.clear()	删除 c 中的所有元素，返回 void
关系运算符
==, !=	所有容器都支持相等（不等）运算符
<, <=, >, >=	关系运算符（无序关联容器不支持）
获取迭代器
c.begin(), c.end()	返回指向 c 的首元素和尾元素之后位置的迭代器
c.cbegin(), c.cend()	返回 const_iterator
反向容器的额外成员（不支持 forward_list）
reverse_iterator	按逆序寻址元素的迭代器
const_reverse_iterator	不能修改元素的逆序迭代器
c.rbegin(), c.rend()	返回指向 c 的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend()	返回 const_reverse_iterator

9.2.1 迭代器

forward_list 迭代器不支持递减运算符（- -）（因为是单向的——博主注）。
一个选代器范围（iterator range）由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置（one past the last element），这两个迭代器通常被称为 begin 和 end，begin 和 end 必须指向相同的容器，end 可以与 begin 指向相同的位置，但不能指向 begin 之前的位置。迭代器范围是左闭合区间（left-inclusive interval）。
假定 begin 和 end 构成一个合法的迭代器范围，则：
- 如果 begin 与 end 相等，则范围为空
- 如果 begin 与 end 不等，则范围至少包含一个元素，且 begin 指向该范围中的第一个元素
- 可以对 begin 递增若干次，使得 begin == end
练习 9.6： 下面程序有何错误？你应该如何修改它？
1
2
3
4
list<int> lst1;
list<int>::iterator iter1 = lst1.begin(),
iter2 = lst1.end();
while (iter1 < iter2) /*...*/
vscode 提示信息为：没有与这些操作数匹配的 “<” 运算符 — 操作数类型为: std::_List_iterator < std::_List_iterator

9.2.2 容器类型成员

反向迭代器就是一种反向遍历容器的迭代器，与正向迭代器相比，各种操作的含义也都发生了颠倒。例如，对一个反向迭代器执行 ++ 操作，会得到上一个元素。
如果需要元素类型，可以使用容器的 value_type。如果需要元素类型的一个引用，可以使用 reference 或 const_reference。

9.2.3 begin 和 end 成员

begin 和 end 操作生成指向容器中第一个元素和尾元素之后位置的迭代器。这两个迭代器最常见的用途是形成一个包含容器中所有元素的迭代器范围。begin 和 end 有多个版本：带 r 的版本返回反向迭代器；以 c 开头的版本则返回 const 迭代器：

list<string> a = {"Milton", "Shakespeare", "Austen"};
auto itl = a.begin();   // list<string>::iterator
auto it2 = a.rbegin();  // list<string>::reverse_iterator
auto it3 = a.cbegin();  // list<string>::const_iterator
auto it4 = a.crbegin(); // list<string>::const_reverse iterator

当我们对一个非常量对象调用这些成员时，得到的是返回 iterator 的版本。只有在对一个 const 对象调用这些函数时，才会得到一个 const 版本。与 const 指针和引用类似，可以将一个普通的 iterator 转换为对应的 const_iterator，但反之不行。

当 auto 与 begin 或 end 结合使用时，获得的迭代器类型依赖于容器类型，与我们想要如何使用迭代器毫不相干。但以 c 开头的版本还是可以获得 const_iterator 的，而不管容器的类型是什么。

Best Practices：当不需要写访问时，应使用 cbegin 和 cend。

9.2.4 容器定义和初始化

除 array 之外，其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器大小和元素初始值的参数。

容器定义和初始化
C c;	默认构造函数。如果 c 是一个 array，则 c 中元素按默认方式初始化；否则 c 为空
C c1(c2)	c1 初始化为 c2 的拷贝。c1 和 c2 必须是相同类型（即，它们必须是相同的容器类型，且保存的是相同的元素类型；对于 array 类型，两者还必须具有相同大小）
C c1 = c2
C c{a, b, c...}	c 初始化为初始化列表中元素的拷贝。列表中元素的类型必须与 c 的元素类型相容。对于 array 类型，列表中元素数目必须等于或小于 array 的大小，任何遗漏的元素都进行值初始化
C c = {a, b, c...}
C c(b, e)	c 初始化为迭代器 b 和 e 指定范围中的元素的拷贝。范围中元素的类型必须与 c 的元素类型相容（array 不适用）
只有顺序容器（不包括 array）的构造函数才能接受大小参数
C seq(n)	seq 包含 n 个元素，这些元素进行了值初始化；此构造函数是 explicit 的（string 不适用）
C seq(n, t)	seq 包含 n 个初始化为值 t 的元素

将一个新容器创建为另一个容器的拷贝的方法有两种：可以直接拷贝整个容器，或者（array 除外）拷贝由一个迭代器对指定的元素范围（指针对也可以——博主注）。为了创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配。不过，当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。而且，新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换为要初始化的容器的元素类型即可。

// 每个容器有三个元素，用给定的初始化器进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char *> articles = {"a", "an", "the"};
list<string> list2(authors);     // 正确：类型匹配
deque<string> authList(authors); // 错误：容器类型不匹配
vector<string> words(articles);  // 错误：容器类型必须匹配
// 正确：可以将 const char* 元素转换为 string
forward_list<string> words(articles.begin(), articles.end());

Note：当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。

接受两个迭代器参数的构造函数用这两个迭代器表示我们想要拷贝的一个元素范围。与以往一样，两个迭代器分别标记想要拷贝的第一个元素和尾元素之后的位置。新容器的大小与范围中元素的数目相同。新容器中的每个元素都用范围中对应元素的值进行初始化。由于两个迭代器表示一个范围，因此可以使用这种构造函数来拷贝一个容器中的子序列（很实用，这个技巧在一些 LeetCode 题目中经常会用到——博主注）。

在新标准中，我们可以对一个容器进行列表初始化。
除了与关联容器相同的构造函数外，顺序容器（array 除外）还提供另一个构造函数，它接受一个容器大小和一个（可选的）元素初始值。如果我们不提供元素初始值，则标准库会创建一个值初始化器。如果元素类型是内置类型或者是具有默认构造函数的类类型，可以只为构造函数提供一个容器大小参数。如果元素类型没有默认构造函数，除了大小参数外，还必须指定一个显式的元素初始值。

Note：只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
与内置数组一样，标准库 array 的大小也是类型的一部分。当定义一个 array 时，除了指定元素类型，还要指定容器大小。array 大小固定的特性也影响了它所定义的构造函数的行为。与其他容器不同，一个默认构造的 array 是非空的：它包含了与其大小一样多的元素。这些元素都被默认初始化。

如果我们对 array 进行列表初始化，初始值的数目必须等于或小于 array 的大小。如果初始值数目小于 array 的大小，则它们被用来初始化 array 中靠前的元素，所有剩余元素都会进行值初始化（对 array 的列表赋值也是如此——博主注）。在这两种情况下，如果元素类型是一个类类型，那么该类必须有一个默认构造函数，以使值初始化能够进行：

1
2
3

array<int, 10> ia1;                                  // 10 个默认初始化的 int
array<int, 10> ia2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 列表初始化
array<int, 10> ia3 = {42};                           // ia3[0] 为42，剩余元素为 0

虽然我们不能对内置数组类型进行拷贝或对象赋值操作，但 array 并无此限制：

int digs[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int cpy[10] = digs; // 错误：内置数组不支持拷贝或赋值
array<int, 10> digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
array<int, 10> copy = digits; // 正确：只要数组类型匹配即合法

与其他容器一样，array 也要求初始值的类型必须与要创建的容器类型相同。此外，array 还要求元素类型和大小也都一样，因为大小是 array 类型的一部分。

9.2.5 赋值和 swap

与赋值相关的运算符可用于所有容器。赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝。与内置数组不同，标准库 array 类型允许赋值。赋值号左右两边的运算对象必须具有相同的类型。由于右边运算对象的大小可能与左边运算对象的大小不同，因此 array 类型不支持 assign，关联容器同样不支持：

容器的 assign 操作
seq.assign(b, e)	将 seq 中的元素替换为迭代器 b 和 e 所表示的范围中的元素。迭代器 b 和 e 不能指向 seq 中的元素
seq.assign(il)	将 seq 中的元素替换为初始化列表 il 中的元素
seq.assign(n, t)	将 seq 中的元素替换为 n 个值为 t 的元素

WARNING：赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而 swap 操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效（容器类型为 array 和 string 的情况除外）。

assign 操作用参数所指定的元素（的拷贝）替换左边容器中的所有元素：

list<string> names;
vector<const char *> oldstyle;
// names = oldstyle; // 错误：容器类型不匹配
// 正确：可以将 const char* 转换为 string
names.assign(oldstyle.cbegin(), oldstyle.cend());

WARNING：由于其旧元素被替换，因此传递给 assign 的迭代器不能指向调用 assign 的容器。

assign 的第二个版本接受一个整型值和一个元素值。它用指定数目且具有相同给定值的元素替换容器中原有的元素：

// 等价于 slist1.clear();
// 后跟 slist1.insert(slist1.begin(), 10, "Hiya!");
list<string> slist1(1);     // 1 个元素，为空 string
slist1.assign(10, "Hiya!"); // 10 个元素，每个都是 "Hiya!"

swap 操作交换两个相同类型容器的内容，被交换的两个容器大小可以不同。除 array 外，交换两个容器内容的操作保证会很快——元素本身并未交换，swap 只是交换了两个容器的内部数据结构。

Note：除 array 外，swap 不对任何元素进行拷贝、删除或插入操作，因此可以保证在常数时间内完成。

元素不会被移动的事实意味着，除 string 外，指向容器的迭代器、引用和指针在 swap 操作之后都不会失效。它们仍指向 swap 操作之前所指向的那些元素。但是，在 swap 之后，这些元素已经属于不同的容器了。与其他容器不同，对一个 string 调用 swap 会导致迭代器、引用和指针失效。与其他容器不同，swap 两个 array 会真正交换它们的元素。因此，交换两个 array 所需的时间与 array 中元素的数目成正比。因此，对于 array，在 swap 操作之后，指针、引用和迭代器所绑定的元素保持不变，但元素值已经与另一个 array 中对应元素的值进行了交换。在新标准库中，容器既提供成员函数版本的 swap，也提供非成员版本的 swap。而早期标准库版本只提供成员函数版本的 swap。非成员版本的 swap 在泛型编程中是非常重要的。统一使用非成员版本的 swap 是一个好习惯。

9.2.6 容器大小操作

max_size 返回一个大于或等于该类型容器所能容纳的最大元素数的值。forward_list 支持 max_size 和 empty，但不支持 size。

9.2.7 关系运算符

每个容器类型都支持相等运算符（== 和 !=）；除了无序关联容器外的所有容器都支持关系运算符（>、>=、<、<=）。关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。即，我们只能将一个 vector<int> 与另一个 vector<int> 进行比较，而不能将一个 vector<int> 与一个 list<int> 或一个 vector<double> 进行比较。比较两个容器实际上是进行元素的逐对比较。这些运算符的工作方式与 string 的关系运算类似：

如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等；否则两个容器不等。
如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
如果两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不相等的元素的比较结果。

vector<int> v1 = {1, 3, 5, 7, 9, 12};
vector<int> v2 = {1, 3, 9};
vector<int> v3 = {1, 3, 5, 7};
vector<int> v4 = {1, 3, 5, 7, 9, 12};
v1 < v2   // true；v1 和 v2 在元素 [2] 处不同：v1[2] 小于等于 v2[2]
v1 < v3   // false；所有元素都相等，但 v3 中元素数目更少
v1 == v4  // true；每个元素都相等，且 v1 和 v4 大小相同
v1 == v2  // false；v2 元素数目比 v1 少

Note：只有当其元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器。

9.3 顺序容器操作

顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。

9.3.1 向顺序容器添加元素

除 array 外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。下面这些操作会改变容器的大小，array 不支持这些操作。forward_list 有自己专有版本的 insert 和 emplace。forward_list 不支持 push_back 和 emplace_back。vector 和 string 不支持 push_front 和 emplace_front。

向顺序容器添加元素的操作
c.push_back(t)	在 c 的尾部创建一个值为 t 或由 args 创建的元素。返回 void
c.emplace_back(args)	在 c 的尾部创建一个值为 t 或由 args 创建的元素。返回 void
c.push_front(t)	在 c 的头部创建一个值为 t 或由 args 创建的元素。返回 void
c.emplace_front(args)	在 c 的头部创建一个值为 t 或由 args 创建的元素。返回 void
c.insert(p, t)	在迭代器 p 指向的元素之前创建一个值为 t 或由 args 创建的元素。返回指向新添加的元素的迭代器
c.emplace(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

WARNING：向一个 vector、string 或 deque 插入元素会使所有指向容器的迭代器、引用和指针失效。

在一个 vector 或 string 的尾部之外的任何位置，或是一个 deque 的首尾之外的任何位置添加元素，都需要移动元素。而且，向一个 vector 或 string 添加元素可能引起整个对象存储空间的重新分配。重新分配一个对象的存储空间需要分配新的内存，并将元素从旧的空间移动到新的空间中。
对 push_back 的调用在 container 尾部创建了一个新的元素，将 container 的 size 增大了 1。
关键概念：容器元素是拷贝。当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。
除了 push_back，list、forward_list 和 deque 容器还支持名为 push_front 的类似操作。deque 像 vector 一样提供了随机访问元素的能力，但它提供了 vector 所不支持的 push_front。deque 保证在容器首尾进行插入和删除元素的操作都只花费常数时间。与 vector 一样，在 deque 首尾之外的位置插入元素会很耗时。
insert 成员提供了更一般的添加功能，它允许我们在容器中任意位置插入 0 个或多个元素。vector、deque、list 和 string 都支持 insert 成员。forward_list 提供了特殊版本的 insert 成员。每个 insert 函数都接受一个迭代器作为其第一个参数。迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置，包括容器尾部之后的下一个位置（意即 insert 的迭代器参数可以是尾后迭代器——博主注）。

将元素插入到 vector、deque 和 string 中的任何位置都是合法的。然而，这样做可能很耗时。
insert 函数下面的这个用法将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化：
1
svec.insert(svec.end(), 10, "Anna");

接受一对迭代器或一个初始化列表的 insert 版本将给定范围中的元素插入到指定位置之前：

vector<string> v = {"quasi", "simba", "frollo", "scar"};
// 将 v 的最后两个元素添加到 slist 的开始位置
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "will",
                           "go", "at", "the", "end"});
// 运行时错误：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器
slist.insert(slist.begin(), slist.begin(), slist.end());

如果我们传递给 insert 一对迭代器，它们不能指向添加元素的目标容器。

在新标准下，接受元素个数或范围的 insert 版本返回指向第一个新加入元素的迭代器。（在旧版本的标准库中，这些操作返回 void。）如果范围为空，不插入任何元素，insert 操作会将第一个参数返回。

通过使用 insert 的返回值，可以在容器中一个特定位置反复插入元素：
1
2
3
4
list<string> lst;
auto iter = lst.begin();
while (cin >> word)
iter = lst.insert(iter, word); // 等价于调用 push_front
上面的代码循环向链表头部插入数据。
新标准引入了三个新成员——emplace_front、emplace 和 emplace_back，这些操作构造而不是拷贝元素。这些操作分别对应 push_front、insert 和 push_back，允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。

当调用 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));

其中对 emplace_back 的调用和第二个 push_back 调用都会创建新的 Sales_data 对象。在调用 emplace_back 时，会在容器管理的内存空间中直接创建对象。 而调用 push_back 则会创建一个局部临时对象，并将其压入容器中。emplace 函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配。（emplace 相关操作更加高效——博主注）

Note：emplace 函数在容器中直接构造元素。传递给 emplace 函数的参数必须与元素类型的构造函数相匹配。

9.3.2 访问元素

如果容器中没有元素，访问操作的结果是未定义的。包括 array 在内的每个顺序容器都有一个 front 成员函数，而除 forward_list 之外的所有顺序容器都有一个 back 成员函数。这两个操作分别返回首元素和尾元素的引用。在解引用一个迭代器或调用 front 或 back 之前应检查容器中是否有元素存在。
值得注意：迭代器 end 指向的是容器尾元素之后的（不存在的）元素。为了获取尾元素，必须首先递减此迭代器。另一个重要之处是，在调用 front 和 back（或解引用 begin 和 end 返回的迭代器）之前，要确保容器非空。

at 和下标操作只适用于 string、vector、deque 和 array。back 不适用于 forward_list。

在顺序容器中访问元素的操作
c.back()	返回 c 中尾元素的引用。若 c 为空，函数行为未定义
c.front()	返回 c 中首元素的引用。若 c 为空，函数行为未定义
c[n]	返回 c 中下标为 n 的元素的引用，n 是一个无符号整数。若 n >= c.size()，则函数行为未定义
c.at(n)	返回下标为 n 的元素的引用。如果下标越界，则抛出 out_of_range 异常

WARNING：对一个空容器调用 front 和 back，就像使用一个越界的下标一样，是一种严重的程序设计错误。

在容器中访问元素的成员函数（即，front、back、下标和 at）返回的都是引用。如果容器是一个 const 对象，则返回值是 const 的引用。如果容器不是 const 的，则返回值是普通引用，我们可以用来改变元素的值。
下标运算符并不检查下标是否在合法范围内。使用越界的下标是一种严重的程序设计错误，而且编译器并不检查这种错误。如果我们希望确保下标是合法的，可以使用 at 成员函数。at 成员函数类似下标运算符，但如果下标越界，at 会抛出一个 out_of_range 异常。

9.3.3 删除元素

array 不支持删除操作，forward_list 有特殊版本的 erase。forward_list 不支持 pop_back；vector 和 string 不支持 pop_front。

顺序容器的删除操作
c.pop_back()	删除 c 中尾元素。若 c 为空，则函数行为未定义。函数返回 void
c.pop_front()	删除 c 中首元素。若 c 为空，则函数行为未定义。函数返回 void
c.erase(p)	删除迭代器 p 所指定的元素，返回一个指向被删元素之后元素的迭代器，若 p 指向尾元素，则返回尾后（off-the-end）迭代器。若 p 是尾后迭代器，则函数行为未定义
c.erase(b, e)	删除迭代器 b 和 e 所指定范围内的元素。返回一个指向最后一个被删元素之后元素的迭代器，若 e 本身就是尾后迭代器，则函数也返回尾后迭代器
c.clear()	删除 c 中的所有元素。返回 void

WARNING：删除 deque 中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向 vector 或 string 中删除点之后位置的迭代器、引用和指针都会失效。

与 vector 和 string 不支持 push_front 一样，这些类型也不支持 pop_front。类似的，forward_list 不支持 pop_back。与元素访问成员函数类似，不能对一个空容器执行弹出操作。这些操作返回 void。如果你需要弹出的元素的值，就必须在执行弹出操作之前保存它。
成员函数 erase 从容器中指定位置删除元素。我们可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素。两种形式的 erase 都返回指向删除的（最后一个）元素之后位置的迭代器。

练习 9.26： 使用下面代码定义的 ia，将 ia 拷贝到一个 vector 和一个 list 中。使用单迭代器版本的 erase 从 list 中删除奇数元素，从 vector 中删除偶数元素。

1	int ia[]={0，1，1，2，3，5，8，13，21，55，89}；

解：

// 练习 9.26
int ia[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89};
std::vector<int> iv(ia, ia + sizeof(ia) / sizeof(int));
std::list<int> il(ia, ia + sizeof(ia) / sizeof(int));
for (auto iter = iv.begin(); iter != iv.end();)
{
if (*iter % 2)
iter = iv.erase(iter);
else
++iter;
}
std::cout << "new vector: " << std::endl;
for (auto &i : iv)
{
std::cout << i << ", ";
}
std::cout << endl;
for (auto iter = il.begin(); iter != il.end();)
{
if (0 == (*iter % 2))
iter = il.erase(iter);
else
++iter;
}
std::cout << "new list: " << std::endl;
for (auto &i : il)
{
std::cout << i << ", ";
}
std::cout << endl;


## 9.3.4 特殊的 forward_list 操作

48. `forward_list` 是单向链表。在一个单向链表中，没有简单的方法来获取一个元素的前驱。出于这个原因，**在一个 `forward_list` 中添加或删除元素的操作是通过改变给定元素之后的元素来完成的**。`forward_list` 并未定义 `insert`、`emplace` 和 `erase`，而是定义了名为 `insert_after`、`emplace_after` 和 `erase_after` 的操作，为了支持这些操作，`forward_list` 也定义了 `before_begin`，它返回一个**首前**（off-the-beginning）迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素（亦即在链表首元素之前添加删除元素）。

    <style type="text/css">
    .tg {border-collapse:collapse;border-spacing:0;}
    .tg td{border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;
    overflow:hidden;padding:10px 5px;word-break:normal;}
    .tg th{border-color:black;border-style:solid;border-width:1px;font-family:Arial, sans-serif;font-size:14px;
    font-weight:normal;overflow:hidden;padding:10px 5px;word-break:normal;}
    .tg .tg-cly1{text-align:left;vertical-align:middle}
    .tg .tg-lboi{border-color:inherit;text-align:left;vertical-align:middle}
    .tg .tg-7btt{border-color:inherit;font-weight:bold;text-align:center;vertical-align:top}
    .tg .tg-0pky{border-color:inherit;text-align:left;vertical-align:top}
    .tg .tg-0lax{text-align:left;vertical-align:top}
    </style>
    <table class="tg">
    <thead>
      <tr>
        <th class="tg-7btt" colspan="2"><center>在 forward_list 中插入或删除元素的操作</center></th>
      </tr>
    </thead>
    <tbody>
      <tr>
        <td class="tg-0pky">lst.before_begin()</td>
        <td class="tg-lboi" rowspan="2">返回指向链表首元素之前不存在的元素的迭代器。此迭代器不能解引用。cbefore_begin() 返回一个 const_iterator</td>
      </tr>
      <tr>
        <td class="tg-0pky">lst.cbefore_begin()</td>
      </tr>
      <tr>
        <td class="tg-0pky">lst.insert_after(p, t)</td>
        <td class="tg-lboi" rowspan="4">在迭代器 p 之后的位置插入元素。t 是一个对象，n 是数量，b 和 e 是表示范围的一对迭代器（b 和 e 不能指向 lst 内），il 是一个花括号列表。返回一个指向最后一个插入元素的迭代器。如果范围为空，则返回 p。若 p 为尾后迭代器，则函数行为未定义</td>
      </tr>
      <tr>
        <td class="tg-0pky">lst.insert_after(p, n, t)</td>
      </tr>
      <tr>
        <td class="tg-0lax">lst. insert_after(p, b, e)</td>
      </tr>
      <tr>
        <td class="tg-0lax">lst.insert_after(p, il)</td>
      </tr>
      <tr>
        <td class="tg-0lax">emplace_after(p, args)</td>
        <td class="tg-0lax">使用 args 在 p 指定的位置之后创建一个元素。返回一个指向这个新元素的迭代器。若 p 为尾后迭代器，则函数行为未定义</td>
      </tr>
      <tr>
        <td class="tg-0lax">lst.erase_after(p)</td>
        <td class="tg-cly1" rowspan="2">删除 p 指向的位置之后的元素，或删除从 b 之后直到（但不包含）e 之间的元素。返回一个指向被删元素之后元素的迭代器，若不存在这样的元素，则返回尾后迭代器。如果 p 指向 lst 的尾元素或者是一个尾后迭代器，则函数行为未定义</td>
      </tr>
      <tr>
        <td class="tg-0lax">lst.erase_after(b, e)</td>
      </tr>
    </tbody>
    </table>

49. **练习 9.27：** 编写程序，查找并删除 `forward_list<int>` 中的奇数元素。

    解：

    ```cpp
    // 练习 9.27
    std::forward_list<int> fl = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89};
    for (auto prev = fl.before_begin(), curr = fl.begin(); curr != fl.end();)
    {
        if (*curr % 2)
        {
            curr = fl.erase_after(prev);
        }
        else
        {
            prev = curr;
            ++curr;
        }
    }
    std::cout << "new forward_list:" << std::endl;
    for (auto &i : fl)
        std::cout << i << ", ";
    std::cout << endl;

练习 9.28： 编写函数，接受一个 forward_list<string> 和两个 string 共三个参数。函数应在链表中查找第一个 string，并将第二个 string 插入到紧接着第一个 string 之后的位置。若第一个 string 未在链表中，则将第二个 string 插入到链表末尾。

解：

// 练习 9.28
void func(std::forward_list<std::string> &fl, const std::string &str1, const std::string &str2)
{
    if (fl.empty())
    {
        fl.push_front(str2);
        return;
    }

    auto prev = fl.before_begin();
    auto curr = fl.begin();
    for (; curr != fl.end(); ++prev, ++curr)
    {
        if (str1 == *curr)
        {
            fl.insert_after(curr, str2);
            return;
        }
    }
    fl.insert_after(prev, str2);
}

9.3.5 改变容器大小

可以用 resize 来增大或缩小容器，与往常一样，array 不支持 resize。如果当前大小大于所要求的大小，容器后部的元素会被删除；如果当前大小小于新大小，会将新元素添加到容器后部：

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

resize 操作接受一个可选的元素值参数，用来初始化添加到容器中的元素。如果调用者未提供此参数，新元素进行值初始化。如果容器保存的是类类型元素，且 resize 向容器添加新元素，则我们必须提供初始值，或者元素类型必须提供一个默认构造函数。

顺序容器大小操作
c.resize(n)	调整 c 的大小为 n 个元素。若 n < c.size()，则多出的元素被丢弃。若必须添加新元素，对新元素进行值初始化
c.resize(n, t)	调整 c 的大小为 n 个元素。任何新添加的元素都初始化为值 t

WARNING：如果 resize 缩小容器，则指向被删除元素的迭代器、引用和指针都会失效；对 vector、string 或 deque 进行 resize 可能导致迭代器、指针和引用失效。

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

向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。

在向容器添加元素后：
- 如果容器是 vector 或 string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
- 对于 deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
- 对于 list 和 forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。
当我们删除一个元素后：
- 对于 list 和 forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
- 对于 deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除 deque 的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
- 对于 vector 和 string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。

添加/删除 vector、string 或 deque 元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用或指针。如果循环中调用的是 insert 或 erase，那么更新迭代器很容易。这些操作都返回迭代器，我们可以用来更新：

// 删除偶数元素，复制奇数元素
std::vector<int> ivec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto iter = ivec.begin(); iter != ivec.end();)
{
    if (*iter % 2)
    {
        iter = ivec.insert(iter, *iter);
        iter += 2;
    }
    else
    {
        iter = ivec.erase(iter);
    }
}
std::cout << "new vector:" << std::endl;
for (auto &i : ivec)
    std::cout << i << ", ";
std::cout << std::endl;

当我们添加/删除 vector 或 string 的元素后，或在 deque 中首元素之外任何位置添加/删除元素后，原来 end 返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用 end，而不能在循环之前保存 end 返回的迭代器，一直当作容器末尾使用（begin 也是如此，LeetCode 341 题犯过类似错误——博主注）。

Tip：如果在一个循环中插入/删除 deque、string 或 vector 中的元素，不要缓存 end 返回的迭代器。

练习 9.31： 条目 53 中删除偶数值元素并复制奇数值元素的程序不能用于 list 或 forward_list。为什么？修改程序，使之也能用于这些类型。

解：list 中没有重载 + 运算符和 += 运算符，只能使用自增运算符和自减运算符移动迭代器；forward_list 中没有重载 + 运算符、+= 运算符和自减运算符，只能使用自增运算符移动迭代器，同时 forward_list 中没有 insert、emplace 和 erase 方法，取而代之的是 insert_after、emplace_after 和 erase_after。

// 练习 9.31：删除偶数元素，复制奇数元素
std::list<int> il = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto iter = il.begin(); iter != il.end();)
{
    if (*iter % 2)
    {
        iter = il.insert(iter, *iter);
        ++iter;
        ++iter;
    }
    else
    {
        iter = il.erase(iter);
    }
}
std::cout << "new list:" << std::endl;
for (auto &i : il)
    std::cout << i << ", ";
std::cout << endl;

9.4 vector 对象是如何增长的

为了支持快速随机访问，vector 将元素连续存储——每个元素紧挨着前一个元素存储。

假定容器中元素是连续存储的，且容器的大小是可变的，考虑向 vector 或 string 中添加元素会发生什么：如果没有空间容纳新元素，容器不可能简单地将它添加到内存中其他位置——因为元素必须连续存储。容器必须分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。如果我们每添加一个新元素，vector 就执行一次这样的内存分配和释放操作，性能会慢到不可接受。为了避免这种代价，标准库实现者采用了可以减少容器空间重新分配次数的策略。当不得不获取新的内存空间时，vector 和 string 的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用，可用来保存更多的新元素。这样，就不需要每次添加新元素都重新分配容器的内存空间了。（vector 往往是成倍扩容——博主注）

shrink_to_fit 只适用于 vector、string 和 deque。capacity 和 reserve 只适用于 vector 和 string。

容器大小管理操作
c.shrink_to_fit()	请将 capacity() 减少为与 size() 相同大小
c.capacity()	不重新分配内存空间的话，c 可以保存多少元素
c.reserve(n)	分配至少能容纳 n 个元素的内存空间

Note：reserve 并不改变容器中元素的数量，它仅影响 vector 预先分配多大的内存空间。

如果需求大小小于或等于当前容量，reserve 什么也不做。特别是，当需求大小小于当前容量时，容器不会退回内存空间。因此，在调用 reserve 之后，capacity 将会大于或等于传递给 reserve 的参数。

调用 reserve 永远也不会减少容器占用的内存空间。类似的，同样不能使用 resize 来减少容器预留的内存空间。
在新标准库中，我们可以调用 shrink_to_fit 来要求 deque、vector 或 string 退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是，具体的实现可以选择忽略此请求。也就是说，调用 shrink_to_fit 也并不保证一定退回内存空间。
容器的 size 是指它已经保存的元素的数目；而 capacity 则是在不分配新的内存空间的前提下它最多可以保存多少元素。
Note：每个 vector 实现都可以选择自己的内存分配策略。但是必须遵守的一条原则是：只有当迫不得已时才可以分配新的内存空间。
只有在执行 insert 操作时 size 与 capacity 相等，或者调用 resize 或 reserve 时给定的大小超过当前 capacity，vector 才可能重新分配内存空间。 会分配多少超过给定容量的额外空间，取决于具体实现。
练习 9.37： 为什么 list 或 array 没有 capacity 成员函数？

答：因为 list 是链式存储结构，array 是定长的顺序存储结构。

9.5 额外的 string 操作

9.5.1 构造 string 的其他方法

构造 string 的其他方法：

构造 string 的其他方法
string s(cp, n)	s 是 cp 指向的数组中前 n 个字符的拷贝。此数组至少应该包含 n 个字符
string s(s2, pos2)	s 是 string s2 从下标 pos2 开始的字符的拷贝。若 pos2 > s2.size()，构造函数的行为未定义
string s(s2, pos2, len2)	s 是 string s2 从下标 pos2 开始 len2 个字符的拷贝。若 pos2 > s2.size()，构造函数的行为未定义。不管 len2 的值是多少，构造函数至多拷贝 s2.size() - pos2 个字符

观察下面的代码段

const char *cp = "Hel1o World!!!"; // 以空字符结束的数组
char noNull[] = {'H', 'i'};        // 不是以空字符结束
string s1(cp);                     // 拷贝 cp 中的字符直到遇到空字符；s1 == "Hello     World!!!"
string s2(noNull, 2);              // 从 noNull 拷贝两个字符；s2 == "Hi"
string s3(noNull);                 // 未定义：noNull 不是以空字符结束
string s4(cp + 6, 5);              // 从 cp[6] 开始拷贝 5 个字符；s4 == "World"
string s5(s1, 6, 5);               // 从 s1[6] 开始拷贝 5 个字符；s5 == "World"
string s6(s1, 6);                  // 从 s1[6] 开始拷贝,直至 s1 末尾；s6 == "World!!!"
string s7(s1, 6, 20);              // 正确,只拷贝到 s1 末尾；s7 == "World!!!"
string s8(s1, 16);                 // 抛出一个 out_of_range 异常

通常当我们从一个 const char* 创建 string 时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符时停止。如果我们还传递给构造函数一个计数值，数组就不必以空字符结尾。如果我们未传递计数值且数组也未以空字符结尾，或者给定计数值大于数组大小，则构造函数的行为是未定义的。

当从一个 string 拷贝字符时，我们可以提供一个可选的开始位置和一个计数值。开始位置必须小于或等于给定的 string 的大小。如果位置大于 size，则构造函数抛出一个 out_of_range 异常。如果我们传递了一个计数值，则从给定位置开始拷贝这么多个字符。不管我们要求拷贝多少个字符，标准库最多拷贝到 string 结尾，不会更多。

substr 操作返回一个 string，它是原始 string 的一部分或全部的拷贝。可以传递给 substr 一个可选的开始位置和计数值：

string s("hello world");
string s2 = s.substr(0, 5);  // s2 = hello
string s3 = s.substr(6);     // s3 = world
string s4 = s.substr(6, 11); // s3 = world
string s5 = s.substr(12);    // 抛出一个 out_of_range 异常

如果开始位置超过了 string 的大小，则 substr 函数抛出一个 out_of_range 异常。如果开始位置加上计数值大于 string 的大小，则 substr 会调整计数值，只拷贝到 string 的末尾。

子字符串操作
s.substr(pos, n)	返回一个 string，包含 s 中从 pos 开始的 n 个字符的拷贝。pos 的默认值为 0。n 的默认值为 s.size() - pos，即拷贝从 pos 开始的所有字符

练习 9.41： 编写程序，从一个 vector<char> 初始化一个 string。

解：

1 2	std::vector<char> ivec = {'0', '1', '2', '3'}; std::string str(ivec.begin(), ivec.end());

练习 9.42： 假定你希望每次读取一个字符存入一个 string 中，而且知道最少需要读取 100 个字符，应该如何提高程序的性能？

解：预先为 string reserve 不小于 100 个字符的容量。

9.5.2 改变 string 的其他方法

string 类型支持顺序容器的赋值运算符以及 assign、insert 和 erase 操作，除了接受迭代器的 insert 和 erase 版本外，string 还提供了接受下标的版本。下标指出了开始删除的位置，或是 insert 到给定值之前的位置：
1
2
s.insert(s.size(), 5, '!'); // 在 s 末尾插入 5 个感叹号
s.erase(s.size() - 5, 5); // 从 s 删除最后 5 个字符
标准库 string 类型还提供了接受 C 风格字符数组的 insert 和 assign 版本。例如，我们可以将以空字符结尾的字符数组 insert 到或 assign 给一个 string：
1
2
3
const char *cp = "Stately, plump Buck";
s.assign(cp, 7); // s == "Stately"
s.insert(s.size(), cp + 7); // s == "Stately, plump Buck"

我们也可以指定将来自其他 string 或子字符串的字符插入到当前 string 中或赋予当前 string：

string s = "some string", s2 = "some other string";
s.insert(0, s2); // 在 s 中位置 0 之前插入 s2 的拷贝
// 在 s[0] 之前插入 s2 中 s2[0] 开始的 s2.size() 个字符
s.insert(0, s2, 0, s2.size());

string 类定义了两个额外的成员函数；append 和 replace，这两个函数可以改变 string 的内容。append 用于向 string 末尾追加字符串，replace 用于对 string 中的字符进行替换：
1
s.replace(11, 3, "Fifth"); // s == "C++ Primer Fifth Ed."
在此调用中，删除了 3 个字符，但在其位置插入了 5 个新字符。

练习 9.43： 编写一个函数，接受三个 string 参数 s、oldVal 和 newVal。使用迭代器及 insert 和 erase 函数将 s 中所有 o1dVal 替换为 newVal。测试你的程序，用它替换通用的简写形式，如，将”tho”替换为”though”，将”thru”替换为”through”。

解：

void func1(std::string &s, const std::string &oldVal, const std::string &newVal)
{
    int sLen = s.size(), oldLen = oldVal.size(), newLen = newVal.size();

    if (oldLen > sLen || 0 == oldLen)
        return;

    for (auto ptr = s.begin(); ptr != s.end();)
    {
        if (s.substr(ptr - s.begin(), oldLen) == oldVal)
        {
            ptr = s.erase(ptr, ptr + oldLen);
            ptr = s.insert(ptr, newVal.begin(), newVal.end()) + newLen;
        }
        else
            ++ptr;
    }
}

练习 9.44： 重写上一题的函数，这次使用一个下标和 replace。

解：

void func2(std::string &s, const std::string &oldVal, const std::string &newVal)
{
    int sLen = s.size(), oldLen = oldVal.size(), newLen = newVal.size();

    if (oldLen > sLen || 0 == oldLen)
        return;

    for (size_t i = 0; i < s.size();)
    {
        if (s.substr(i, oldLen) == oldVal)
        {
            s.replace(i, oldLen, newVal);
            i += newLen;
        }
        else
            ++i;
    }
}

练习 9.45： 编写一个函数，接受一个表示名字的 string 参数和两个分别表示前缀（如
“Mr.”或”Ms.”）和后缀（如”Jr.”或”II”）的字符串。使用迭代器及 insert 和 append 函数将前缀和后缀添加到给定的名字中，将生成的新 string 返回。

解：
1
2
3
4
5
6
7
std::string &func3(std::string &s, const char *prefix, const char *suffix)
{
std::string pref(prefix);
s.insert(s.begin(), pref.begin(), pref.end());
s.append(suffix);
return s;
}

练习 9.46： 重写上一题的函数，这次使用位置和长度来管理 string，并只使用 insert。

解：

std::string &func4(std::string &s, const char *prefix, const char *suffix)
{
    s.insert(0, prefix);
    s.insert(s.size(), suffix);
    return s;
}

9.5.3 string 搜索操作

string 类提供了 6 个不同的搜索函数，每个函数都有 4 个重载版本。每个搜索操作都返回一个 string::size_type 值，表示匹配发生位置的下标。如果搜索失败，则返回一个名为 string::npos 的 static 成员。标准库将 npos 定义为一个 const string::size_type 类型，并初始化为值 -1。由于 npos 是一个 unsigned 类型，此初始值意味着 npos 等于任何 string 最大的可能大小。
WARNING：string 搜索函数返回 string:：size_type 值，该类型是一个 unsigned 类型。因此，用一个 int 或其他带符号类型来保存这些函数的返回值不是一个好主意。

观察下述代码段：

string name("AnnaBelle");
auto pos1 = name.find("Anna"); // pos1 == 0

string lowercase("annabelle");
auto pos2 = lowercase.find("Anna"); // pos2 == npos

string numbers("0123456789"), name("r2d2");
// 返回 1，即，name 中第一个数字的下标
auto pos3 = name.find_first_of(numbers);

string dept("03714p3");
// 返回 5——字符 'p' 的下标
auto pos4 = dept.find_first_not_of(numbers);

搜索操作返回指定字符出现的下标，如果未找到则返回 npos。

string 搜索操作
s.find(args)	查找 s 中 args 第一次出现的位置
s.rfind(args)	查找 s 中 args 最后一次出现的位置
s.find_first_of(args)	在 s 中查找 args 中任何一个字符第一次出现的位置
s.find_last_of(args)	在 s 中查找 args 中任何一个字符最后一次出现的位置
s.find_first_not_of(args)	在 s 中查找第一个不在 args 中的字符
s.find_last_not_of(args)	在 s 中查找最后一个不在 args 中的字符
args 必须是以下形式之一
c, pos	从 s 中位置 pos 开始查找字符 c。pos 默认为 0
s2, pos	从 s 中位置 pos 开始查找字符串 s2。pos 默认为 0
cp, pos	从 s 中位置 pos 开始查找指针 cp 指向的以空字符结尾的 C 风格字符串。pos 默认为 0
cp, pos, n	从 s 中位置 pos 开始查找指针 cp 指向的数组的前 n 个字符。pos 和 n 无默认值

可以传递给 find 操作一个可选的开始位置。这个可选的参数指出从哪个位置开始进行搜索。默认情况下，此位置被置为 0。一种常见的程序设计模式是用这个可选参数在字符串中循环地搜索子字符串出现的所有位置

string::size_type pos = 0;
// 每步循环查找 name 中下一个数
while ((pos = name.find_first_of(numbers, pos)) != string::npos)
{
    cout << "found number at index:" << pos
         << "element is" << name[pos] << endl;
    ++pos; // 移动到下一个字符
}

练习 9.47： 编写程序，首先查找 string “ab2c3d7R4E6” 中的每个数字字符，然后查找其中每个字母字符。编写两个版本的程序，第一个要使用 find_first_of，第二个要使用 find_first_not_of。

解：

void func_947_1(void)
{
    std::string s = "ab2c3d7R4E6";
    std::string numbers = "0123456789";
    std::string letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    std::string::size_type pos = 0;
    while (true)
    {
        pos = s.find_first_of(numbers, pos);

        if (pos != std::string::npos)
        {
            std::cout << "number occurs in s[" << pos << "]: " << s[pos] << std::endl;
            ++pos;
        }
        else
            break;
    }

    pos = 0;
    while (true)
    {
        pos = s.find_first_of(letters, pos);

        if (pos != std::string::npos)
        {
            std::cout << "letter occurs in s[" << pos << "]: " << s[pos] << std::endl;
            ++pos;
        }
        else
            break;
    }
}

void func_947_2(void)
{
    std::string s = "ab2c3d7R4E6";
    std::string numbers = "0123456789";
    std::string letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    std::string::size_type pos = 0;
    while (true)
    {
        pos = s.find_first_not_of(letters, pos);

        if (pos != std::string::npos)
        {
            std::cout << "number occurs in s[" << pos << "]: " << s[pos] << std::endl;
            ++pos;
        }
        else
            break;
    }

    pos = 0;
    while (true)
    {
        pos = s.find_first_not_of(numbers, pos);

        if (pos != std::string::npos)
        {
            std::cout << "letter occurs in s[" << pos << "]: " << s[pos] << std::endl;
            ++pos;
        }
        else
            break;
    }
}

练习 9.49： 如果一个字母延伸到中线之上，如 d 或 f，则称其有上出头部分（ascender）。如果一个字母延伸到中线之下，如 p 或 g，则称其有下出头部分（descender）。编写程序，读入一个单词文件，输出最长的既不包含上出头部分，也不包含下出头部分的单词。

解：

std::string func_949(const std::string &file)
{
    std::ifstream fin(file);
    std::string word, cender_letters = "bdfghjklpqty";
    std::pair<int, std::string> result(0, "");

    while (fin >> word)
    {
        if (word.find_first_of(cender_letters) == std::string::npos)
        {
            if (word.size() > result.first)
            {
                result.first = word.size();
                result.second = word;
            }
        }
    }

    return result.second;
}

9.5.4 compare 函数

标准库 string 类型还提供了一组 compare 函数，根据 s 是等于、大于还是小于参数指定的字符串，s.compare 返回 0、正数或负数。

s.compare 的几种参数形式
s2	比较 s 和 s2
pos1, n1, s2	将 s 中从 pos1 开始的 n1 个字符与 s2 进行比较
pos1, n1, s2, pos2, n2	将 s 中从 pos1 开始的 n1 个字符与 s2 中从 pos2 开始的 n2 个字符进行比较
cp	比较 s 与 cp 指向的以空字符结尾的字符数组
pos1, n1, cp	将 s 中从 pos1 开始的 n1 个字符与 cp 指向的以空字符结尾的字符数组进行比较
pos1, n1, cp, n2	将 s 中从 pos1 开始的 n1 个字符与指针 cp 指向的地址开始的 n2 个字符进行比较

9.5.5 数值转换

要转换为数值的 string 中第一个非空白符必须是数值中可能出现的字符：
1
2
3
string s2 = "pi=3.14";
// 转换 s 中以数字开始的第一个子串，结果 d = 3.14
double d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
我们将 s2 中从此位置开始的子串传递给stod。stod 函数读取此参数，处理其中的字符，直至遇到不可能是数值的一部分的字符。然后它就将找到的这个数值的字符串表示形式转换为对应的双精度浮点值。

string 参数中第一个非空白符必须是符号（+ 或 -）或数字。它可以以 0x 或 0x 开头来表示十六进制数。对那些将字符串转换为浮点值的函数，string 参数也可以以小数点（.）开头，并可以包含 e 或 E 来表示指数部分。对于那些将字符串转换为整型值的函数，根据基数不同，string 参数可以包含字母字符，对应大于数字 9 的数。

Note：如果 string 不能转换为一个数值，这些函数抛出一个 invalid_argument 异常。如果转换得到的数值无法用任何类型来表示，则抛出一个 out_of_range 异常。

string 和数值之间的常见转换操作如下表所示：

string 和数值之间的转换
to_string(val)	一组重载函数，返回数值 val 的 string 表示。val 可以是任何算术类型。对每个浮点类型和 int 或更大的整型，都有相应版本的 to_string。与往常一样，小整型会被提升
stoi(s, p, b)	返回 s 的起始子串（表示整数内容）的数值，返回值类型分别是 int、long、unsigned long、long long、unsigned long long。b 表示转换所用的基数，默认值为 10。p 是 size_t 指针，用来保存 s 中第一个非数值字符的下标，p 默认为 0，即，函数不保存下标
stol(s, p, b)
stoul(s, p, b)
stoll(s, p, b)
stoull(s, p, b)
stof(s, p)	返回 s 的起始子串（表示浮点数内容）的数值，返回值类型分别是 float、double 或 long double。参数 p 的作用与整数转换函数中一样
stod(s, p)
stold(s, p)

练习 9.51： 设计一个类，它有三个 unsigned 成员，分别表示年、月和日。为其编写构造函数，接受一个表示日期的 string 参数。你的构造函数应该能处理不同数据格式，如 January 1，1900、1/1/1990、Jan 1 1900 等。

解：

class MyDate
{
public:
    MyDate(const std::string &date)
    {
        std::string::size_type pos_blank_1st = date.find_first_of(" ");
        std::string::size_type pos_blank_2nd = date.find_last_of(" ");
        std::string::size_type pos_comma = date.find_first_of(",");
        std::string::size_type pos_slash_1st = date.find_first_of("/");
        std::string::size_type pos_slash_2nd = date.find_last_of("/");

        if (pos_blank_1st != std::string::npos)
        {
            month = map_month[date.substr(0, pos_blank_1st)];
            day = pos_comma != std::string::npos
                      ? std::stoi(date.substr(pos_blank_1st + 1, pos_comma - pos_blank_1st - 1))
                      : std::stoi(date.substr(pos_blank_1st + 1, pos_blank_2nd - pos_blank_1st - 1));
            year = std::stoi(date.substr(pos_blank_2nd + 1));
        }
        else
        {
            month = map_month[date.substr(0, pos_slash_1st)];
            day = std::stoi(date.substr(pos_slash_1st + 1, pos_slash_2nd - pos_slash_1st - 1));
            year = std::stoi(date.substr(pos_slash_2nd + 1));
        }
    }

    void GetDate(void)
    {
        std::cout << " Year: " << year << std::endl;
        std::cout << "Month: " << month << std::endl;
        std::cout << "  Day: " << day << std::endl;
        std::cout << std::endl;
    }

private:
    int year;
    int month;
    int day;
    std::map<std::string, int> map_month = {
        {"January", 1},
        {"Jan", 1},
        {"1", 1},
        {"February", 2},
        {"Feb", 2},
        {"2", 2},
        {"March", 3},
        {"Mar", 3},
        {"3", 3},
        {"April", 4},
        {"Apr", 4},
        {"4", 4},
        {"May", 5},
        {"5", 5},
        {"June", 6},
        {"Jun", 6},
        {"6", 6},
        {"July", 7},
        {"7", 7},
        {"August", 8},
        {"Aug", 8},
        {"8", 8},
        {"September", 9},
        {"Sep", 9},
        {"9", 9},
        {"October", 10},
        {"Oct", 10},
        {"10", 10},
        {"November", 11},
        {"Nov", 11},
        {"11", 11},
        {"December", 12},
        {"Dec", 12},
        {"12", 12},
    };
};

9.6 容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue 和 priority_queue。适配器（adaptor）是标准库中的一个通用概念。容器、迭代器和函数都有适配器。每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。
默认情况下，stack 和 queue 是基于 deque 实现的，priority_queue 是在 vector 之上实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。
1
2
3
4
// 在 vector 上实现的空栈
stack<string, vector<string>> str_stk;
// str_stk2 在 vector 上实现，初始化时保存 svec 的拷贝
stack<string, vector<string>> str_stk2(svec);
所有适配器都要求容器县有添加和删除元素的能力。因此，适配器不能构造在 array 之上。类似的，我们也不能用 forward_list 来构造适配器，因为所有适配器都要求容器具有添加、删除以及访问尾元素的能力。stack 只要求 push_back、pop_back 和 back 操作，因此可以使用除 array 和 forward_list 之外的任何容器类型采构造 stack。queue 适配器要求 back、push_back、front 和 push_front，因此它可以构造于 list 或 deque 之上，但不能基于 vector 构造。priority_queue 除了 front、push_back 和 pop_back 操作之外还要求随机访问能力，因此它可以构造于 vector 或 deque 之上，但不能基于 list 构造。

一些典型的 stack 操作：

一些典型的 stack 操作
s.pop()	删除栈顶元素，但不返回该元素值
s.push(item)	创建一个新元素压入栈顶，该元素通过拷贝或移动 item 而来，或者由 args 构造
s.emplace(args)	创建一个新元素压入栈顶，该元素通过拷贝或移动 item 而来，或者由 args 构造
s.top()	返回栈顶元素，但不将元素弹出栈

queue 默认基于 deque 实现，priority_queue 默认基于 vector 实现；queue 也可以用 list 或 vector 实现，priority_queue 也可以用 deque 实现。一些典型的 queue 和 priority_queue 操作：

一些典型的 queue 和 priority_queue 操作
q.pop()	删除 queue 的首元素或 priority_queue 的最高优先级的元素，但不返回此元素
q.front()	返回首元素或尾元素，但不删除此元素，只适用于 queue
q.back()	返回首元素或尾元素，但不删除此元素，只适用于 queue
q.top()	返回最高优先级元素，但不删除该元素，只适用于 priority_queue
q.push(item)	在 queue 末尾或 priority_queue 中恰当的位置创建一个元素，其值为 item，或者由 args 构造
q.emplace(args)

priority_queue 允许我们为队列中的元素建立优先级。新加入的元素会排在所有优先级比它低的已有元素之前。

术语表

forward_list 顺序容器，表示一个单向链表。forward_list 中的元素只能顺序访问。从一个给定元素开始，为了访问另一个元素，我们只能遍历两者之间的所有元素。forward_list 上的迭代器不支持递减运算（--）。forward_list 支持任意位置的快速插入（或删除）操作。与其他容器不同，插入和删除发生在一个给定的迭代器之后的位置。因此，除了通常的尾后迭代器之外，forward_list 还有一个“首前”迭代器。在添加新元素后，原有的指向 forward_list 的迭代器仍有效。在删除元素后，只有原来指向被删元素的迭代器才会失效。
选代器范围（iterator range） 由一对迭代器指定的元素范围。第一个迭代器表示序列中第一个元素，第二个迭代器指向最后一个元素之后的位置。如果范围为空，则两个迭代器是相等的（反之亦然，如果两个迭代器不等，则它们表示一个非空范围）。如果范围非空，则必须保证，通过反复递增第一个迭代器，可以到达第二个迭代器。通过递增迭代器，序列中每个元素都能被访问到。
list 顺序容器，表示一个双向链表。list 中的元素只能顺序访问。从一个给定元素开始，为了访问另一个元素，我们只能遍历两者之间的所有元素。list 上的迭代器既支持递增运算（++），也支持递减运算（--）。list 支持任意位置的快速插入（或删除）操作。当加入新元素后，迭代器仍然有效。当删除元素后，只有原来指向被删除元素的迭代器才会失效。
首前迭代器（off-the-beginning iterator） 表示一个 forward_list 开始位置之前（不存在的）元素的迭代器。是 forward_list 的成员函数 before_begin 的返回值。与 end() 迭代器类似，不能被解引用。
vector 顺序容器。vector 中的元素可以通过位置下标访问。支持快速的随机访问。我们只能在 vector 末尾实现高效的元素添加/删除。向 vector 添加元素可能导致内存空间的重新分配，从而使所有指向 vector 的迭代器失效。在 vector 内部添加（或删除）元素会使所有指向插入（删除）点之后元素的迭代器失效。

输出倒逼思考

C++ Primer - 第 9 章顺序容器