一个容器就是一些特定类型对象的集合。 顺序容器（sequentialcontainer） 指实现能按顺序访问的数据结构，它为程序员提供了控制元素存储和访问顺序的能力。 这种访问顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。与之相对的，将在第11章介绍的有序和无序关联容器，则根据关键字的值来存储元素。

标准库还提供了三种容器适配器，分别为容器操作定义了不同的接口，来与容器类型适配，将在本章末尾介绍适配器。

所有容器类都共享公共的接口，不同容器按不同方式对其进行扩展。 这个公共接口使容器的学习更加容易——基于某种容器所学习的内容也都适用于其他容器。每种容器都提供了不同的性能和功能的权衡。

概述

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

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

除了固定大小的array外，其他容器都提供高效、灵活的内存管理。 即可以添加和删除元素，扩张和收缩容器的大小。容器保存元素的策略对容器操作的效率有着固定的，有时是重大的影响。在某些情况下，存储策略还会影响特定容器是否支持特定操作。

① string和vector将元素保存在连续的内存空间中，由元素的下标来计算其地址是非常快速的，但是在两种容器的中间位置添加或删除元素非常耗时。而且，添加一个元素有时可能还需要分配额外的存储空间，此时每个元素都必须移动到新的存储空间中。
② list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问：即为了访问一个元素，我们只能遍历整个容器。与vector、deque和array相比，这两个容器的额外内存开销也很大。
③ deque是一个更为复杂的数据结构，元素可以从两端弹出。与string和vector类似，deque支持快速随机访问。 与string和vector一样，在deque的中间位置添加或删除元素的代价（可能）很高 。但是在deque的两端添加或删除元素很快，与list或forward_list添加/删除元素的速度相当。
④ forward_list和array是新C++标准增加的类型。与内置的数组类型相比，array更加安全、更容易使用。forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言，size操作保证是一个快速的常量时间（即与任何变量无关）的操作。

• 如何确定使用哪种容器

  • 除非有很好的理由选择其他容器，否则使用vector是最好的选择；
  • 如果程序有很多小元素且空间的额外开销很重要，不要使用list或forward_list；
  • 要求随机访问元素，应该使用vector或deque；
  • 要求中间插入或删除元素，应该使用list或forward_list；
  • 需要在头尾插入或删除元素，且中间不进行插入或删除，应该使用deque；
  • 如果只在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素。首先可以考虑在读
  • 输入时使用vector，再调用sort函数重排容器中的元素，从而避免在中间位置添加元素。如果必须在中间位置插入元素，考虑在输入阶段使用list，输入完成将list拷贝到vector中

容器库概览

一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。即deque定义在头文件deque中，list定义在头文件list中，以此类推。标准库的容器均定义为模板类（class template）（参见3.3节）。例如对vector，我们必须提供额外信息来生成特定的容器类型。对大多数，但不是所有容器，我们必须额外提供元素类型信息：

1
2

list<Sales_data>// 保存Sales_data对象的list
deque<double>	// 保存double的deque

迭代器

一个 迭代器范围（iteratorrange） 由一对迭代器表示，两个迭代器分别指向同一个容器中的某个元素或者是 尾元素之后的位置（one past the last element） 。这种元素范围被称为左闭合区间（left-inclusive interval）。其标准数学描述为 [begin,end) 。表示范围自begin开始，于end之前结束。迭代器begin和end必须指向相同的容器。end可以与begin指向相同的位置，但不能指向begin之前的位置。

容器类型成员

每个容器都定义了多个类型，如上面所示。之前已经使用过其中三种：size_type （参见3.2.2节）、iterator和const_iterator（参见3.4.1节）。

除了已经使用过的迭代器类型，大多数容器还提供反向迭代器。简单地说，反向迭代器就是一种反向遍历容器的迭代器，与正向迭代器相比，各种操作的含义也都发生了颠倒。例如，对一个反向迭代器执行++操作，会得到上一个元素。

剩下的就是类型别名了，通过类型别名，可以在不了解容器中元素类型的情况下使用它。如果需要元素类型，可以使用容器的value_type。如果需要元素类型的一个引用，可以使用reference或const_reference。这些元素相关的类型别名在泛型编程中非常有用。

为了使用这些类型，我们必须显式使用其类名：

1
2

list<string>::iterator iter;       	// iter 是通过list<string>定义的一个迭代器类型
vector<int>::difference_type count;	// count 是通过vector<int>定义的一个difference_type类型

这些声明语句使用了作用域运算符::来访问某个作用域，以便使用list类的iterator成员及vector类定义的difference_type

以 c 开头的版本是C++新标准引入的，用以支持auto（参见2.5.2节），可以与begin和end（包括r或c等版本）成员函数结合使用。以前没有其他选择，只能显式声明希望使用哪种类型的迭代器：

1
2
3
4
5
6

// 显式指定类型
list<string>::iterator it5 = a.begin();
list<string>::const_iterator it6 = a.begin();	// 是iterator还是const_iterator依赖于a的类型
// 新标准C++之后可以使用 auto 
auto it7 = a.begin();	// 仅当a是const时，it7是const_iterator
auto it8 = a.cbegin();	// it8是const_iterator

顺序容器特有操作

添加元素

• 在容器中的特定位置添加元素

  insert成员函数它允许我们在容器中任意位置插入0个或多个元素。而 vector 、 deque 、 list 和 string 都支持 insert 成员函数。至于 forward_list 则是被提供了特殊版本的 insert 成员函数，将在9.3.4节中介绍。

  每个 insert 成员函数都接受一个迭代器作为其第一个参数。这个迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置，包括容器尾部之后的下一个位置。 由于迭代器可能指向容器尾部之后不存在的元素的位置，而且在容器开始位置插入元素是很有用的功能，所以 insert 函数将元素插入到迭代器所指定的位置之前。例如，下面的语句：

  slist.insert(iter, "Hello!"); // 将"Hello!"添加到 iter 指向的元素之前的位置
  虽然某些容器不支持 push_front 操作，但它们对于 insert 操作并无类似的限制（插入开始位置），比如 vector 。因此可以将元素插入到容器的开始位置，而不必担心容器是否支持 push_front ：

  1 2 3 4 5 6 7 8 9

  vector<string> svec; list<string> slist; // 等价于调用slist.push_front("Hello!'*); slist.insert(slist.begin(),"Hello!"); // vector 不支持push_front,但我们可以插入到begin()之前 // 警告：插入到vector末尾之外的任何位置都可能很慢 svec.insert(svec.begin(),"Hello!");

• 使用 emplace 操作

  新标准引入了三个新成员 emplace_front 、 emplace 和 emplace_back ，这些 emplace 操作中的成员函数是直接通过参数构造元素而不是拷贝或移动元素。这些操作分别对应 push_front 、 insert 和 push_back ，允许将元素放置在容器头部、一个指定位置之前和容器尾部。

  当程序员执行一个 emplace 操作时，则是将参数传递给容器的元素类型的普通构造函数。emplace 操作的成员函数使用这些参数在容器管理的内存空间中直接构造元素。之前的（push_front 、 insert 和 push_back）是调用移动构造函数或拷贝构造函数，会浪费内存和时间。

改变容器大小

1
2
3
4

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个元素

额外的string操作

除了顺序容器共同的操作之外， string 类型还提供了一些额外的操作。这些操作中的大部分要么是提供 string 类和C风格字符数组之间的相互转换，要么是增加了允许程序员用下标代替迭代器的版本。

标准库 string 类型定义了大量函数。幸运的是，这些函数使用了重复的模式。当了解 string 支持哪些类型的操作后，就可以在需要使用一个特定操作时回过头来仔细阅读

构造string

substr

1
2
3
4
5

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);	// s4=world
string s5 = s.substr(12);	// 抛出一个out_of_range异常

s.substr(pos,n)

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

搜索操作

string 类提供了6个不同的搜索函数，每个函数都有4个重载版本。下表中描述了这些搜索成员函数及其参数。每个搜索操作都返回一个 string::size_type 值，表示匹配发生位置的下标。如果搜索失败，则返回一个名为 string::npos 的 static 数据成员。 标准库将 string::npos 定义为一个 const string::size_type 类型，并初始化为值-1。由于 string::npos 是一个 const unsigned 类型，此初始值意味着 string::npos 等于任何 string 最大的可能大小 （比如 unsigned char c = -1; ，假设 char 占8bit，则 c 的值为255）。

• 成员函数 find 完成最简单的搜索。它查找参数指定的字符串，若找到，则返回第一个匹配位置的下标，否则返回 string::npos ：

  1 2	string name("AnnaBelle"); auto posl = name.find("Annan"); // posl==0

• 搜索（以及其他 string 操作）是大小写敏感的。当在 string 中查找子字符串时，要注意大小写：

  1 2	string lowercase("annabelle"); posl = lowercase.find("Anna"); // posl==npos

• 一个更复杂一些的问题是 查找与给定字符串中任何一个字符匹配的位置，可以使用成员函数 find_first_of 。例如，下面代码定位 name 中的第一个数字：

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

• 如果是要 搜索第一个不在参数中的字符，应该调用 find_first_not_of 。例如，为了搜索一个 string 中第一个非数字字符，可以这样做：

  1 2	string dept("03714p3"); auto pos = dept.find_first_not_of(numbers); // 返回5——即第一个非数字字符'p'的下标

• 逆向搜索

  到现在为止，已经用过的 find 操作都是由左至右搜索。标准库还提供了类似的， 但由右至左搜索的操作。 成员函数 rfind 搜索最后一个匹配，即子字符串最靠右的出现位置 ：

  1 2 3

  string river("Mississippi"); auto first_pos = river. find ("is") ; // 返回 1 auto last_pos = river. rfind ("is") ; // 返回 4

  成员函数 find 返回下标值1，表示第一个”is”的位置，而 rfind 返回下标4，表示最后一个”is”的位置。

  类似的， find_last 函数的功能与 find_first 函数相似，只是它们返回最后一个字符而不是第一个字符的匹配：

  find_last_of 搜索与给定 string 中任何一个字符匹配的最后一个字符。
  find_last_not_of 搜索最后一个不出现在给定 string 中的字符。

数值转换

新标准引入了多个函数，可以实现数值数据与标准库 string 之间的转换：

1
2
3

int i = 42;
string s = to_string(i);// 将整数 i 转换为字符表示形式
double d = stod(s);		// 将字符串 s 转换为浮点数

适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器： stack 、 queue 和 priority_queue 。

  适配器（adaptor） 是标准库中的一个通用概念。 容器、迭代器和函数都有适配器。 本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。比如，一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。

定义

每个STL容器适配器都定义了两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。 例如，假定 deq 是一个 deque<int> ，可以用 deq 来初始化一个新的 stack ，如下所示：

stack<int> stk(deq); // 从deq拷贝元素到stk

默认情况下， stack 和 queue 是基于 deque 实现的， priority_queue 是在 vector 之上实现的。 程序员可以在创建一个STL容器适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

1
2
3
4

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

栈适配器

1
2
3
4
5
6
7
8
9

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

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。程序员只可以使用适配器操作，而不能使用底层容器类型的操作。 例如：

intStack.push(ix); // intStack保存0到9，一共十个数

此语句试图在intStack的底层 deque 对象上调用 push_back 。虽然 stack 默认是基于 deque 实现的，但不能直接使用 deque 的操作。不能在一个 stack 调用 push_back ，而必须使用 stack 自己的操作——即成员函数 push

队列适配器

标准库类型 queue 使用一种 先进先出（first-in first-out，FIFO）的存储和访问策略 。进入队列的对象被放置到队尾，而离开队列的对象则从队首删除。即先进入队列的元素比后进入的元素先被删除。

标准库类型 priority_queue 允许 程序员为队列中的元素建立优先级。新加入的元素会排在所有优先级比它低的已有元素之前。默认情况下，标准库在元素类型上使用 < 运算符来确定相对优先级。 将在11.2.2节学习如何重载这个默认设置。