《C++Primer》第九章 顺序容器

简介

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

后面第十一章会介绍有序和无序关联容器，会根据关键字的值来存储元素。

顺序容器类型

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

需要注意的是：

• string和vector将元素保存在连续的内存空间中，因此根据下表来计算地址是非常快速的。但是在两种容器的中间位置添加或删除元素需要移动该位置后的所有元素来保证连续存储。如果添加一个元素需要分配额外的存储空间，那么所有元素都会被移动到新的存储空间中
• list和forward_list设计的目的是令容器任何位置的添加和删除操作都很快速，作为代价这两个容器不支持元素的随机访问，为了访问某个元素我们只能遍历整个容器。同时这两种容器的额外内存开销比vector、deque和array都要大的多。
• 新标准库的容器比旧版本快的多，线代C++程序应该使用标准库容器，而不是更原始的数据结构，如内置数组。

选择容器的基本原则

• 除非你有很好的理由选择其他容器，否则使用vector是最好的选择
• 如果你的程序有很多很小的元素，且空间的额外开销很重要，那么不要使用list和forward_list
• 如果程序要求随机访问元素，那么使用vector和deque
• 如果程序要求在容器的中间插入或者删除元素，应使用list或forward_list
• 如果程序只需要在头尾位置插入或者删除元素，但不会在中间位置进行插入或删除操作，则使用deque
• 如果程序只有在读取输入时才需要在容器中间插入元素，那么你有两种做法：一是使用vector添加元素，然后调用标准库的sort重排；二是在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中

如果你不确定应该是用哪种容器，那么可以在程序中只使用vector和list公共的操作：使用迭代器，不使用下标操作，这样可以避免随机访问。

容器库概览

1. 容器操作

• 类型别名

• 构造函数

// 默认构造函数, 构造空容器
C c;

// 构造c2的拷贝c1
C c1(c2);

// 构造c, 将迭代器b和e指定范围内的元素拷贝到c
C c(b, e);

// 列表初始化c
C c{a, b, c...};

• 赋值与swap

// 将c1中的元素替换为c2
c1 = c2;

// 将c1中的元素替换为列表中元素
c1 = {a, b, c...};

// 交换a和b的元素
a.swap(b);
swap(a, b);

• 大小

// c中元素的数目, 不支持forward_list
c.size();

// c可保存的最大元素数目
c.max_size();

// 判断c中是否保存元素
c.empty();

• 添加删除元素（不适用于array）

注：在不同的容器中，这些操作的接口都不同

// 将args中的元素拷贝进c
c.insert(args);

// 使用initss构造c中一个元素
c.emplace(inits);

// 删除args指定的元素
c.erase(args);

// 删除c中所有元素, 返回void
c.clear();

• 关系运算符

// 所有容器都支持相等和不等运算符
==, !=

// 关系运算符, 无序关联容器不支持
<, <=, >, >=

• 获取迭代器

// 返回指向c的首元素和尾元素之后的迭代器
c.begin(), c.end()

// 返回const_iterator
c.cbegin(), c.cend()

• 反向容器的额外成员

// 按逆序寻址元素的迭代器
reverse_iterator

// 不能修改元素的逆序迭代器
const_reverse_iterator

// 不能修改元素的逆序迭代器
c.rbegin(), c.rend()

// 返回const_reverse_iterator
c.crbegin(), c.crend()

2. 迭代器

注意迭代器的范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或尾元素之后的位置。通常被称为begin和end。这种表示有三种方便的性质：

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

另外注意begin和end有多种版本：带r的版本返回反向迭代器；以c开头的版本返回const迭代器。不以c开头的函数都是被重载过的，即实际上有两个名为begin的成员，一个是const成员返回容器的const_iterator类型，另一个是非常量成员返回容器的iterator类型。

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

3. 容器定义和初始化

// 默认构造函数, 如果C是一个array, 则c中元素按默认方式初始化, 否则c为空
C c;

// c1初始化为c2的拷贝, c1和c2必须是相同类型, 对于array而言两者还必须具有相同大小
C c1(c2)
C c1=c2

// c初始化为初始化列表中元素的拷贝。列表中的元素类型必须和C的元素类型相容, 对于array类型而言列表中元素数目必须等于或者小于array的大小, 任何遗漏的元素都进行值初始化
C c{a,b,c...}
C c={a,b,c...}

// c初始化为迭代器b和e指定范围内元素的拷贝, 范围中元素的类型必须与C的元素类型相容(array不使用)
C c{b,e}

// 只有顺序容器(不包括array)的构造函数才能接受大小实参
C seq(n)    // seq包含n个元素, 这些元素进行了值初始化; 此构造函数是explicit的(string不适用)
C seq(n,t)  // seq包含n个初始化为t值得元素

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

当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。不过当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了，新容器内的元素类型只要能转换成初始化容器的元素类型即可

list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

// 拷贝方式一：直接拷贝整个容器, 要求容器类型和元素类型都必须相同
list<string> list2(authors);    // 正确: 类型匹配
vector<string> words(articles); // 错误: 容器类型不匹配

// 拷贝方式二：传递迭代器参数来拷贝一个范围
// 正确: 可以将const char* 元素转换为string
forward_list<string> words(articles.begin(), articles.end());

• 列表初始化

我们可以对容器进行列表初始化，这样会显式指定容器内每个元素的值。除了array外，初始化列表还隐含地指定了容器的大小：容器将包含与初始值一样多的元素。

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

除了与关联容器相同的构造函数外，顺序容器（array除外）还提供另一个构造函数，它接受一个容器大小和一个（可选的）元素初始值。如果不提供初始值，则标准库会创建一个值初始化器。

vector<int> ivec(10, -1);     // 10个int元素, 每个都初始化为-1
list<string> svec(10, "hi!"); // 10个string； 每个都初始化为"hi!"
forward_list<int> ivec(10);   // 10个元素, 每个都初始化为0
deque<string> svec(10);       // 10个元素, 每个都是空string

• 标准库array具有固定大小

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

array<int, 10> ia1;   // 10个默认初始化的int
array<int, 10> ia2 = {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; // 正确

4.赋值和swap

如果俩容器的大小不同，那么赋值运算后两者的大小都与右边容器的原大小相同：

c1 = c2;      // 将c1的内容替换为c2中元素的拷贝
c1 = {a,b,c}; // 赋值后, c1大小为3

与内置数组不同，array类型允许赋值，但是赋值号左右两边的运算对象必须具有相同的类型：

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 19> a2 = {0}; // 所有元素均为0
a1 = a2;  // 替换a1中的元素
a2 = {0}; // 错误：不能将一个花括号列表赋予数组

容器赋值运算除了=操作符外，还包括swap()和assign()：

// 将c1中的元素替换为c2中元素的拷贝, c1和c2必须具有相同的类型
c1=c2

// 将c1中元素替换为初始化列表中元素的拷贝（array不适用）
c={a,b,c...}

// 交换c1和c2中的元素, c1和c2必须具有相同的类型, swap操作通常比从c2向c1拷贝元素快得多
swap(c1, c2)
c1.swap(c2)

// assign不适用于关联容器和array
// 将seq中的元素替换为迭代器b和e所表示范围的元素
seq.assign(b,e) 
// 将seq中的元素替换为初始化列表il中的元素
seq.assign(il)
// 将seq中的元素替换为n个值为t的元素
seq.assign(n,t)
seq.assign(il)

• 赋值运算符要求左右两边的运算对象具有相同的类型，顺序容器（除array）外提供了assign成员允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。比如我们可以使用assign实现从一个vector中的一段char*值赋予一个list中的string。
• swap操作交换两个相同类型容器的内容，注意除array外，swap不对任何元素进行拷贝、删除或插入操作，因此可以保证在常数时间内完成。
• 与其他容器不同，swap两个array会真正交换它们的元素，因此交换两个array所需的时间与array中元素的数目成正比。

5. 容器大小操作

除了forward_list外，所有容器类型都有三个与大小相关的操作：

• size：返回容器中元素的数目
• empty：当size为0返回真
• max_size：返回一个大于或等于该类型容器所能容纳的最大元素数的值

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

6. 关系运算符

每个容器都支持相等运算符（==和!=），除了无序关联容器外的所有容器都支持关系运算符（>, >=, <, <=）。关系运算符两边必须是保存相同类型元素的容器。本质上是对容器内每个元素逐个比较：

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

顺序容器操作

1. 向顺序容器添加元素

除array外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或者删除元素来改变容器大小。

需要注意如下几点：

• 这些添加元素的操作会改变容器大小，array不支持这些操作。
• forward_list有自己专有版本的insert和emplace
• forward_list不支持push_back和emplace_back
• vector和string不支持push_front和emplace_front
• 我们可以使用insert将元素插入到vector、string和deque的任何位置，但是这样可能很耗时

具体的添加元素操作包括：

• c.push_back(t), c.emplace_back(args)：在c的尾部创建一个值为t或者由args创建的元素
• c.push_front(t), c.emplace_front(args)：在c的头部创建一个值为t或者由args创建的元素
• c.insert(p,t), c.emplace(p, args)：在迭代器p指向的元素之前创建一个值为t或由args创建的元素。返回指向新添加的元素的迭代器。
• c.insert(p,n,t)：在迭代器p指向的元素之前插入n个值为t的元素，返回指向新添加的第一个元素的迭代器。
• c.insert(p,b,e)：将迭代器b和e指定范围内的元素插入到迭代器p指向的元素之前，返回指向新添加的第一个元素的迭代器。
• c.insert(p,il)：将花括号包起来的元素值列表插入到迭代器p指向的元素之前，返回新添加的第一个元素的迭代器。

注意：向一个vector、string或者deque插入元素会使得所有指向容器的迭代器、引用和指针失效。在一个vector或者string的尾部之外任何位置，或是一个deque的首尾之外的任何位置添加元素都需要移动元素。向vector或者string添加元素可能引起整个对象存储空间的重新分配（重新分配一个存储一个对象的内存，并激昂元素从旧的空间移动到新的空间）。

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

2. 访问元素

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

具体的访问元素操作包括：

• at和下标操作只适用于string、vector、deque和array
• c.back()：返回c中尾元素的引用, 如果c为空则函数行为未定义
• c.front()：返回c中首元素的引用, 如果c为空则函数行为未定义
• c[n]：返回第n个元素的引用, 如果n>=c.size()则函数行为未定义
• c.at(n)：返回第n个元素的引用, 如果下标越界则抛出out_of_range异常

使用front或者back成员函数前需要判断c.empty()是否为真

// 在容器中访问元素的成员函数（front、back、at和下标）返回的都是引用
if (!c.empty()) {
    auto &v = c.back();  // 获得最后一个元素的引用
    v = 1024;            // 改变c中最后一个元素
    auto v2 = c.back();  // v2不是一个引用, 只是c.back()的一个拷贝
    v2 = 0;              // 并不会改变c中最后一个元素
}

3. 删除元素

注意：

• 删除元素会改变容器的大小，所以不适用于array。
• forward_list有特殊版本的erase
• forward_list不支持pop_back
• vector和string不支持pop_front
• 删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。

相关的操作包括：

• c.pop_back()：删除c中尾元素, 若c为空则函数行为未定义
• c.pop_front()：删除c中首元素, 若c为空则函数行为未定义
• c.erase(p)：删除迭代器p指向的元素, 返回一个指向被删元素之后元素的迭代器
• c.erase(b,e)：删除迭代器b和e所指定范围内的元素, 返回一个指向最后一个被删除元素之后元素的迭代器
• c.clear()：删除c中所有元素

4. 特殊的forward_list操作

假设一个forward_list表示为如下：

// 删除elem3之前
elem1 -> elem2 -> elem3 -> elem4

// 删除elem3会改变elem2的值
elem1 -> elem2 -> elem4

由于forward_list是一个单向链表，因此我们没有简单的方法来获取一个元素的前驱。forward_list定义了名为insert_after、emplace_after和erase_after。为了支持这些操作，forward_list也定义了before_begin，它返回一个首前元素。这个迭代器允许我们在链表首元素之前添加/删除元素。

具体的操作包括：

• lst.before_begin(), lst.cbefore_begin()：返回指向链表首元素之前不存在的元素的迭代器，此迭代器不能解引用
• lst.insert_after(p,t),lst.insert_after(p,n,t),lst.insert_after(p,b,e),lst.insert_after(p,il)：在迭代器p之后的位置插入元素，返回一个指向最后一个插入元素的迭代器
• emplace_after(p,args)：使用args在p指定的位置之后创建一个元素，返回一个指向这个新元素的迭代器
• lst.erase_after(p), lst.erase_after(b,e)：删除元素，返回一个指向被删元素之后元素的迭代器

5. 改变容器大小

除了array外我们可以使用resize()来增加或者缩小容器，如果当前大小小于所要求的大小，容器后面的元素会被删除；如果当前大小小于新大小，会将新元素添加到容器后部。

6. 容器操作可能使得迭代器失效

向容器添加元素：

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

删除元素后：

• 对于list和forward_list指向容器其他位置的迭代器、引用和指针仍然有效
• 对于vector和string，指向被删除元素之前元素的迭代器、引用和指针仍有效。

管理容器大小的操作

• c.shrink_to_fit()：只适用于vector、string和deque，将capacity()减少为与size()相同大小
• c.capacity()：不重新分配内存空间的话，c可以保存多少元素
• c.reserve(n)：分配至少能容纳n个元素的内存空间

额外的string操作

1. 构造string的其他方法

• string s(cp,n)：s是cp指向的数组前n个字符的拷贝，此数组至少应该包含n个字符
• string s(s2,pos2)：s是string s2从下标pos2开始的字符的拷贝
• string s(s2,pos2,len)：s是sting s2从下标pos2开始len2个字符的拷贝
• s.substr(pos,n)：返回一个string，包含s中从pos开始的n个字符的拷贝

2. 改变string的其他方法

string类型支持顺序容器的赋值运算以及assign、insert和erase操作，同时还定义了额外的insert和erase版本。

• s.insert(pos,args)：在pos之前插入args指定的字符，pos可以是一个下标或一个迭代器，接受下标的版本返回一个指向s的引用，接受迭代器的版本返回指向第一个插入字符的迭代器
• s.erase(pos,len)：删除从pos位置开始的len个字符，返回指向s的引用
• s.append(args)：将s中的字符替换为args的字符，返回一个指向s的引用
• s.replace(range,args)： 删除s中范围range内的字符，替换为args指定的字符。range或者是一个下标和一个长度，或者是一对指向s的迭代器。返回s的引用

上面提到的args可以是一下形式之一：

• str：字符串str
• str,pos,len：str从pos开始最多len个字
• cp,len：从cp指向的字符数组的前（最多）len个字符
• cp：cp指向的以空字符结尾的字符数组
• n,c：n个字符c
• b,e：迭代器b和e指定的范围内的字符
• 初始化列表：花括号包围的，以逗号分割的字符列表

注意：

• assign总是替换string中的所有内容
• append总是将新字符追加到string的末尾
• replace函数提供了两种指定删除元素范围的方式：即可以通过一个位置和一个长度来指定范围，也可以通过一个迭代器范围来指定
• insert函数允许我们使用两种方式来指定插入点：用一个下标或者一个迭代器，两种方式下新元素都会插入到给定下标之前的位置

3. string搜索操作

string类提供了6个不同的搜索函数，每个搜索操作返回一个string::size_type值，表示匹配发生位置的下标。如果搜索失败则返回一个名为string::npos的static成员。搜索操作包括：

• 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无默认值

4. compare函数

类似于strcmp函数，根据s是等于、大于还是小于参数指定的字符串，s.compare返回0、正数或者负数。根据我们是要比较两个string还是一个string与一个字符数组，我们可以将compare划分为6个版本：

• 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个字符进行比较

5. 数值转换

要转换为数值的string中第一个非空白符必须是数值中可能出现的字符，如果string不能转换为一个数值则这些函数会抛出一个invalid_argument的异常。

• to_string(val)：一组重载函数，返回数值val的string表示。
• stoi(s,p,b), stol(s,p,b), stoul(s,p,b), stoll(s,p,n),stoull(s,p,b)：返回s的起始子串（表示整数内容）的数值，返回值分别是int、long、unsigned long、long long、unsigned long long。b表示转换所用的基数，默认值为10。p是size_t指针，用来保存s中第一个非数值字符的下标，默认为0，即不保存下标
• stof(s,p),stod(s,p),stold(s,p)：返回s的起始子串（表示浮点数）的数值，返回值类型分别是float、double或者long double。参数p的作用同上

容器适配器

标准库定义了三个顺序容器适配器：stack、queue和priority_queue，一个容器适配器接收一种已有的容器类型，使其行为看起来像一种不同的类型。例如stack适配器接收一个顺序容器（除array或forward_list外），并使其操作起来像一个stack一样。

1. 容器适配器都支持的操作和类型

• size_type：一种类型，足以保存当前类型的最大对象的大小
• value_type：元素类型
• container_type：实现适配器的底层容器类型
• A a：创建一个名为a的空适配器
• A a(c)：创建一个名为a的适配器，带有容器c的一个拷贝
• 关系运算符：每个适配器都支持所有关系运算符==, !=, <, <=, >, >=
• a.empty()：判断a是否包含元素
• a.size()：返回a的元素数目
• swap(a,b), a.swap(b)：交换a和b的内容，a和b必须有相同类型，包括底层容器类型也必须相同

2. 定义一个适配器

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。默认情况下，stack和queue是基于deque实现的，priority_queue是基于vector实现的。但我们也可以通过在创建一个适配器时将一个命名的顺序容器作为第二个类型参数来重载默认容器类型。

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

3. 栈适配器

栈默认基于deque实现，也可以再list或者vecotr上实现

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

4. 队列适配器

queue默认基于deque实现，也可以用list和vecotr实现。priority_queue默认基于vector实现，也可以用deque实现。

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