[C++]C++Primer Chapter 9

顺序容器

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

9.1 顺序容器概述

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

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

1.string和vector

将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在这两种容器的中间位置添加或删除元素就会非常耗时

2.list和forward_list

何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问。与vector、deque和array相比，这两个容器的额外内存开销也很大。

3.deque

与string和vector类似，deque支持快速的随机访问。与string和vector一样，在deque的中间位置添加或删除元素的代价（可能）很高。但是，在deque的两端添加或删除元素都是很快的，与list或forward_list添加删除元素的速度相当。

4.forward_list和array是新C++标准增加的类型。

与内置数组相比，array是一种更安全、更容易使用的数组类型。与内置数组类似，array对象的大小是固定的。因此，array不支持添加和删除元素以及改变容器大小的操作。

forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。

对其他容器而言，size保证是一个快速的常量时间的操作。

新标准库容器的性能几乎肯定与最精心优化过的同类数据结构一样好（通常会更好）。现代C++程序应该使用标准库容器，而不是更原始的数据结构，如内置数组。

确定使用哪种顺序容器

以下是一些选择容器的基本原则：

除非你有很好的理由选择其他容器，否则应使用vector。
如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list。
如果程序要求随机访问元素，应使用vector或deque。
如果程序要求在容器的中间插入或删除元素，应使用list或forward_list。
如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque。
如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
- 首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向vector追加数据，然后再调用标准库的sort函数（我们将在10.2.3节介绍sort（第343页））来重排容器中的元素，从而避免在中间位置添加元素。
- 如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中。
- 如果程序既需要随机访问元素，又需要在容器中间位置插入元素，那该怎么办？答案取决于在list或forward_list中访问元素与vector或deque中插入/删除元素的相对性能。一般来说，应用中占主导地位的操作（执行的访问操作更多还是插入/删除更多）决定了容器类型的选择。在此情况下，对两种容器分别测试应用的性能可能就是必要的了。

9.2 容器库概览

容器类型上的操作形成了一种层次：

某些操作是所有容器类型都提供的（参见表9.2，第295页）。
另外一些操作仅针对顺序容器（参见表9.3，第299页）、关联容器（参见表11.7，第388页）或无序容器（参见表11.8，第395页）。
还有一些操作只适用于一小部分容器。

本节介绍对所有容器都适用的操作。

对容器可以保存的元素类型的限制

但某些容器操作对元素类型有其自己的特殊要求。我们可以为不支持特定操作需求的类型定义容器，但这种情况下就只能使用那些没有特殊要求的容器操作了。

9.2.1 迭代器

迭代器范围

这种元素范围被称为左闭合区间（left-inclusive interval），其标准数学描述为

使用左闭合范围蕴含的编程假定

如果begin与end相等，则范围为空
如果begin与end不等，则范围至少包含一个元素，且begin指向该范围中的第一个元素
我们可以对begin递增若干次，使得begin==end

9.2.2 容器类型成员

9.2.3 begin和end成员

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

9.2.4 容器定义和初始化

将一个容器初始化为另一个容器的拷贝

为了创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配。不过，当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。而且，新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换（参见4.11节，第141页）为要初始化的容器的元素类型即可。

列表初始化

与顺序容器大小相关的构造函数

顺序容器（array除外）还提供另一个构造函数，它接受一个容器大小和一个（可选的）元素初始值。如果我们不提供元素初始值，则标准库会创建一个值初始化器（参见3.3.1节，第88页)

只有顺序容器的构造函数才接受大小参数，关联容器并不支持。

标准库array具有固定大小

与内置数组一样，标准库array的大小也是类型的一部分。当定义一个array时，除了指定元素类型，还要指定容器大小

与其他容器不同，一个默认构造的array是非空的：它包含了与其大小一样多的元素。这些元素都被默认初始化（参见2.2.1节，第40页），就像一个内置数组（参见3.5.1节，第102页）中的元素那样。如果我们对array进行列表初始化，初始值的数目必须等于或小于array的大小。如果初始值数目小于array的大小，则它们被用来初始化array中靠前的元素，所有剩余元素都会进行值初始化（参见3.3.1节，第88页）。

值得注意的是，虽然我们不能对内置数组类型进行拷贝或对象赋值操作（参见3.5.1节，第102页），但array并无此限制

9.2.5 赋值和swap

使用assign（仅顺序容器）

顺序容器（array除外）还定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。assign操作用参数所指定的元素（的拷贝）替换左边容器中的所有元素。

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

使用swap

swap操作交换两个相同类型容器的内容。调用swap之后，两个容器中的元素将会交换

除array外，交换两个容器内容的操作保证会很快——元素本身并未交换，swap只是交换了两个容器的内部数据结构。

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

元素不会被移动的事实意味着，除string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效。它们仍指向swap操作之前所指向的那些元素。但是，在swap之后，这些元素已经属于不同的容器了。例如，假定iter在swap之前指向svec1[3]的string，那么在swap之后它指向svec2[3]的元素。

与其他容器不同，对一个string调用swap会导致迭代器、引用和指针失效。

与其他容器不同，swap两个array会真正交换它们的元素。因此，交换两个array所需的时间与array中元素的数目成正比。因此，对于array，在swap操作之后，指针、引用和迭代器所绑定的元素保持不变，但元素值已经与另一个array中对应元素的值进行了交换。

在新标准库中，容器既提供成员函数版本的swap，也提供非成员版本的swap。而早期标准库版本只提供成员函数版本的swap。非成员版本的swap在泛型编程中是非常重要的。统一使用非成员版本的swap是一个好习惯。

9.2.6 容器大小操作

成员函数size（参见3.2.2节，第78页）返回容器中元素的数目；

empty当size为0时返回布尔值true，否则返回false；

max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。

forward_list支持max_size和empty，但不支持size

9.2.7 关系运算符

每个容器类型都支持相等运算符（==和！=）；除了无序关联容器外的所有容器都支持关系运算符（>、>=、<、<=）。关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。

比较两个容器实际上是进行元素的逐对比较。这些运算符的工作方式与string的关系运算（参见3.2.2节，第79页）类似

容器的关系运算符使用元素的关系运算符完成比较

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

9.3 顺序容器操作

9.3.1 向顺序容器添加元素

使用push_back

除array和forward_list之外，每个顺序容器（包括string类型）都支持push_back。

关键概念：容器元素是拷贝

当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。就像我们将一个对象传递给非引用参数（参见3.2.2节，第79页）一样，容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。

使用push_front

list、forward_list和deque容器还支持名为push_front的类似操作。

注意，deque像vector一样提供了随机访问元素的能力，但它提供了vector所不支持的push_front。deque保证在容器首尾进行插入和删除元素的操作都只花费常数时间。

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

insert成员提供了更一般的添加功能，它允许我们在容器中任意位置插入0个或多个元素。vector、deque、list和string都支持insert成员。forward_list提供了特殊版本的insert成员，我们将在9.3.4节（第312页）中介绍。

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

插入范围内元素

接受一个元素数目和一个值，它将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化

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

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

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

使用insert的返回值

通过使用insert的返回值，可以在容器中一个特定位置反复插入元素

使用emplace操作

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

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

9.3.2 访问元素

如果容器中没有元素，访问操作的结果是未定义的。

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

如果我们使用auto变量来保存这些函数的返回值，并且希望使用此变量来改变元素的值，必须记得将变量定义为引用类型。

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

如果我们希望确保下标是合法的，可以使用at成员函数。at成员函数类似下标运算符，但如果下标越界，at会抛出一个out_of_range异常（参见5.6节，第173页）

9.3.3 删除元素

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

pop_front和pop_back成员函数

这些操作返回void。如果你需要弹出的元素的值，就必须在执行弹出操作之前保存它

从容器内部删除一个元素

两种形式的erase都返回指向删除的（最后一个）元素之后位置的迭代器。

删除多个元素

9.3.4 特殊的forward_list操作

forward_list并未定义insert、emplace和erase，而是定义了名为insert_after、emplace_after和erase_after的操作

forward_list也定义了before_begin，它返回一个首前（off-the-beginning）迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素（亦即在链表首元素之前添加删除元素）。

9.3.5 改变容器大小

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

resize操作接受一个可选的元素值参数，用来初始化添加到容器中的元素。如果调用者未提供此参数，新元素进行值初始化（参见3.3.1节，第88页）。

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

在向容器添加元素后：

如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。

当我们删除一个元素后：

对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。

建议：管理迭代器

当你使用迭代器（或指向容器元素的引用或指针）时，最小化要求迭代器必须保持有效的程序片段是一个好的方法。

由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。这个建议对vector、string和deque尤为重要。

编写改变容器的循环程序

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

不要保存end返回的迭代器

当我们添加/删除vector或string的元素后，或在deque中首元素之外任何位置添加/删除元素后，原来end返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用。通常C++标准库的实现中end（）操作都很快，部分就是因为这个原因。

9.4 vector对象是如何增长的

当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用，可用来保存更多的新元素。

管理容量的成员函数

只有当需要的内存空间超过当前容量时，reserve调用才会改变vector的容量。

如果需求大小大于当前容量，reserve至少分配与需求一样大的内存空间（可能更大）。

如果需求大小小于或等于当前容量，reserve什么也不做。特别是，当需求大小小于当前容量时，容器不会退回内存空间。

因此，在调用reserve之后，capacity将会大于或等于传递给reserve的参数。这样，调用reserve永远也不会减少容器占用的内存空间。

类似的，resize成员函数（参见9.3.5节，第314页）只改变容器中元素的数目，而不是容器的容量。我们同样不能使用resize来减少容器预留的内存空间。

在新标准库中，我们可以调用shrink_to_fit来要求deque、vector或string退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是，具体的实现可以选择忽略此请求。也就是说，调用shrink_to_fit也并不保证一定退回内存空间。

capacity和size

虽然不同的实现可以采用不同的分配策略，但所有实现都应遵循一个原则：确保用push_back向vector添加元素的操作有高效率。从技术角度说，就是通过在一个初始为空的vector上调用n次push_back来创建一个n个元素的vector，所花费的时间不能超过n的常数倍。

9.5 额外的string操作

后面用到的时候再来查

9.5.1 构造string的其他方法

substr操作

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

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

9.5.2 改变string的其他方法

除了接受迭代器的insert和erase版本外，string还提供了接受下标的版本。下标指出了开始删除的位置，或是insert到给定值之前的位置

append和replace函数

改变string的多种重载函数

9.5.3 string搜索操作

string类提供了6个不同的搜索函数，每个函数都有4个重载版本。表9.14描述了这些搜索成员函数及其参数。每个搜索操作都返回一个string：：size_type值，表示匹配发生位置的下标。如果搜索失败，则返回一个名为string：：npos的static成员（参见7.6节，第268页）。标准库将npos定义为一个const string：：size_type类型，并初始化为值-1。由于npos是一个unsigned类型，此初始值意味着npos等于任何string最大的可能大小（参见2.1.2节，第32页）。

9.5.4 compare函数

9.5.5 数值转换

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

要转换为数值的string中第一个非空白符必须是数值中可能出现的字符

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

如果string不能转换为一个数值，这些函数抛出一个invalid_argument异常（参见5.6节，第173页）。如果转换得到的数值无法用任何类型来表示，则抛出一个out_of_range异常。