C++ Primer 第九章 顺序容器

一个容器就是一些特定类型对象的集合。顺序容器（sequential container）为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

9.1 顺序容器概述

string和vector保存在连续的内存空间中，因此由下标计算地址非常快速。

forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能，因此不提供size操作，因为保存和计算大小会增加开销。

通常，vector是最好的选择。

每个容器都定义在同名的头文件中，容器均是模板类。

9.2 容器库概览

9.2.1 类型别名

9.2.2 构造函数

只有顺序容器（不包括array的构造函数才能接受大小参数）。如果元素类型没有默认构造函数，除了大小参数外，还需要显式指定元素初始值。array支持拷贝和赋值（内置数组不行）。

9.2.3 赋值与 swap

由于右边运算对象的大小可能与左边不同，因此array不支持assign，也不运行用花括号包围的值列表赋值。assign不适用于关联容器。assign仅要求类型相容。

赋值相关操作会导致指向左边容器内部的迭代器、引用和指针失效，而swap操作不会导致失效（array和string除外），它们仍指向交换之前的那些元素。

除array外，swap不对任何元素进行拷贝、删除和插入操作，因此可以保证在常数时间完成，它只是交换了两个容器的内部数据结构。

swap两个array会真正交换它们的元素。在操作之后，指针、引用和迭代器所绑定的元素保持不变，但元素值已经和另一个array中对应元素的值进行了交换。

统一使用非成员版本的swap是一个好习惯。

9.2.4 容器大小操作

9.2.5 添加元素

这些操作会改变容器大小，array不支持。

forward_list有自己版本的 insert 和 emplace。forward_list不支持 push_back 和 emplace_back。

vector和string不支持push_front 和 emplace_front。

emplace函数会在容器管理的内存空间中直接创建对象，而push函数会创建一个局部临时变量，并将其压入容器中。传递给emplace的参数必须与元素类型的构造函数相匹配。

9.2.6 访问元素

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

9.2.7 删除元素

这些操作会改变容器大小，array不支持。

forward_list有自己版本的 erase。forward_list不支持 pop_back。

vector和string不支持pop_front。

删除元素的成员函数并不检查其参数。在删除元素前，程序员必须确保它们是存在的。

9.2.8 迭代器

注：forward_list不支持

9.2.9 特殊的 forward_list 操作

为了理解forward_list为什么有特殊版本的添加和删除操作，考虑当我们从一个单向链表中删除一个元素时会发生什么。当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生变化。为了添加或删除一个元素，我们需要访问其前驱，以便改变前驱改变前驱的链接。但是，forward_list是单向链表。在一个单向链表中，没有简单的方法来获取一个元素的前驱，出于这个原因，在一个forward_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。这样，我们总是可以访问到被添加或删除元素所影响的元素。

由于这些操作与其他容器上的操作有实现方式不同，forward_list并未定义insert、emplace和erase，而是定义了名为insert_after、emplace_after和erase_after的操作。为了支持这些操作，forward_list也定义了before_begin,它返回一个首前迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素（亦即在链表首元素之前添加删除元素）。

9.2.10 改变容器大小

shrink_to_fit()只适用于vector、string和deque。

capacity()和reserve(n)只适用于vector和string。

9.3 迭代器失效

9.3.1 添加元素

vector或string：

• 存储空间重新分配：迭代器、指针、引用均失效
• 未重新分配：插入位置之前的有效，之后的失效

deque：

• 插入首尾之外：均失效
• 插入首尾：迭代器失效，指针、引用不失效

list或forward_list：都有效（包括尾后和首前）

9.3.2 删除元素

list或forward_list：都有效（包括尾后和首前）

deque：

• 删除首尾之外：均失效
• 删除首：首前失效，其他有效
• 删除尾：尾后失效，其他有效

vector或string：被删除元素之前的都有效

当我们删除元素时，尾后迭代器总是会失效（除了删除deque首元素外），所以不要保存end返回的迭代器。

9.4 额外的 string 操作

9.4.1 构造 string 的其他方法

这些构造函数接受一个string或const char*参数。从const char*拷贝时，指针指向的数组必须以空字符结尾，如果还传递了一个计数值，数组就不必以空字符结尾。

9.4.2 substr 操作

s.substr(pos, n)返回一个string，包含 s 中从 pos 开始的 n 个字符的拷贝。pos 的默认值是0，n 的默认值是 s.size()-pos，即拷贝从 pos 开始的所有字符。如果开始位置超出string的大小，抛出 out_of_range 异常，不管 n 值为多少，最多拷贝到string的末尾。

9.4.3 其他修改 string 的操作

9.4.4 string 搜索操作

string类提供了6个不同的搜索函数，每个函数有4个重载版本。每个搜索操作都返回string::size_type值，表示匹配发生的下标。如果搜索失败，则返回string::npos的static成员。标准库将string::npos定义成一个const string::size_type，并初始化为-1。由于 npos 是一个无符号数，此初始值意味着 npos 等于任何string最大的可能大小。

9.4.5 compare 函数

9.4.6 数值转换

string s2 = "pi = 3.14";
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));

9.5 容器适配器

适配器（adaptors）是标准库中的一个通用概念，容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器（Container adaptors）接受一种已有的容器类型，使其行为看起来像一种不同的类型。标准库定义了三个序列容器适配器：stack、queue和priority_queue。

9.5.1 所以适配器都支持的的操作和类型

9.5.2 定义适配器

• stack默认基于deque实现，要求push_back、pop_back和back操作，可使用除array和forward_list之外的任何容器构造

• queue默认基于deque实现，要求back、push_back、front、push_front操作，可使用list和deque构造

• priority_queue默认基于vector实现，要求front、push_back和pop_back操作，还需要随机访问能力，可使用vector和deque构造

两种构造方法：默认构造函数创建一个空对象；接受一个容器的构造函数拷贝该容器来初始化适配器。

//假设 deq 是一个 deque<int>
stack<int> stk(deq);    //从 deq 拷贝元素到 stk

我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型：

//在 vector 上实现的空栈
stack<string, vector<string>> str_stk;
//在 vector 上实现的空栈，初始化时保存 svec 的拷贝
stack<string, vector<string>> str_stk2（svec);

9.5.3 栈适配器

stack类型定义在同名头文件中。下面展示了如何使用：

stack<int> intStack;  //空栈
//填满栈
for (size_t ix = 0; ix != 10; ++ix)
    intStack.push(ix);  //栈保存0-9十个数
while (!intStack.empty()) { //栈中有值就继续循环
    int value = intStack.top();
    //使用栈顶值的代码
    intStack.pop(); //弹出栈顶元素，继续循环
}

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作，我们只能使用适配器操作，而不能使用底层容器类型的操作。

9.5.4 队列适配器

queue和priority_queue定义在头文件 queue 中。操作方法如下：