# Chapter 9 Sequential Containers

# Overview of the Sequential Containers

# 顺序容器概述

顺序容器（sequential container）：为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

# 顺序容器类型

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

除了固定大小的 array 外，其他容器都提供高效、灵活的内存管理。
forward_list 和 array 是新 C++ 标准增加的类型。
通常使用 vector 是最好的选择，除非你有很好的理由选择其他容器。
新标准库的容器比旧版的快得多。

# Exercise 9.1

对于下面的程序任务， vector 、 deque 和 list 哪种容器最为适合？解释你的选择的理由。如果没有哪一种容器优于其他容器，也请解释理由。

(a) 读取固定数量的单词，将它们按字典序插入到容器中。我们将在下一章中看到，关联容器更适合这个问题。
(b) 读取未知数量的单词，总是将单词插入到末尾。删除操作在头部进行。
(c) 从一个文件读取未知数量的整数。将这些数排序，然后将它们打印到标准输出。

解：

(a) list ，因为需要频繁的插入操作。
(b) deque ，总是在头尾进行插入、删除操作。
(c) vector ，不需要进行插入删除操作。

# Container Library Overview

# 容器操作

# 类型

操作	解释
`iterator`	此容器类型的迭代器类型
`const_iterator`	可以读取元素但不能修改元素的迭代器类型
`size_type`	无符号整数类型，足够保存此种容器类型最大可能的大小
`difference_type`	带符号整数类型，足够保存两个迭代器之间的距离
`value_type`	元素类型
`reference`	元素的左值类型；和 `value_type &` 含义相同
`const_reference`	元素的 `const` 左值类型，即 `const value_type &`

# 构造函数

操作	解释
`C c;`	默认构造函数，构造空容器
`C c1(c2);` 或 `C c1 = c2;`	构造 `c2` 的拷贝 `c1`
`C c(b, e)`	构造 `c` ，将迭代器 `b` 和 `e` 指定范围内的所有元素拷贝到 `c`
`C c(a, b, c...)`	列表初始化 `c`
`C c(n)`	只支持顺序容器，且不包括 `array` ，包含 `n` 个元素，这些元素进行了值初始化
`C c(n, t)`	包含 `n` 个初始值为 `t` 的元素

只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
array 具有固定大小。
和其他容器不同，默认构造的 array 是非空的。
直接复制：将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。
使用迭代器复制：不要求容器类型相同，容器内的元素类型也可以不同。

# 赋值和 `swap`

操作	解释
`c1 = c2;`	将 `c1` 中的元素替换成 `c2` 中的元素
`c1 = {a, b, c...}`	将 `c1` 中的元素替换成列表中的元素（不适用于 `array` ）
`c1.swap(c2)`	交换 `c1` 和 `c2` 的元素
`swap(c1, c2)`	等价于 `c1.swap(c2)`
`c.assign(b, e)`	将 `c` 中的元素替换成迭代器 `b` 和 `e` 表示范围中的元素， `b` 和 `e` 不能指向 `c` 中的元素
`c.assign(il)`	将 `c` 中的元素替换成初始化列表 `il` 中的元素
`c.assign(n, r)`	将 `c` 中的元素替换为 `n` 个值是 `t` 的元素

使用非成员版本的 swap 是一个好习惯。
assign 操作不适用于关联容器和 array

# 大小

操作	解释
`c.size()`	`c` 中元素的数目（不支持 `forward_list` ）
`c.max_size()`	`c` 中可保存的最大元素数目
`c.empty()`	若 `c` 中存储了元素，返回 `false` ，否则返回 `true`

# Exercise 9.2

定义一个 list 对象，其元素类型是 int 的 deque 。

解：

std::list<std::deque<int>> l;

# Exercise 9.3

构成迭代器范围的迭代器有何限制？

解：

两个迭代器 begin 和 end 需满足以下条件：

它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置。
我们可以通过反复递增 begin 来到达 end 。换句话说， end 不在 begin 之前。

# Exercise 9.4

编写函数，接受一对指向 vector<int> 的迭代器和一个 int 值。在两个迭代器指定的范围中查找给定的值，返回一个布尔值来指出是否找到。

解：

	bool find(vector<int>::const_iterator begin, vector<int>::const_iterator end, int i)
	{
	while (begin++ != end)
	{
	if (*begin == i)
	return true;
	}
	return false;
	}

# Exercise 9.5

重写上一题的函数，返回一个迭代器指向找到的元素。注意，程序必须处理未找到给定值的情况。

解：

	vector<int>::const_iterator find(vector<int>::const_iterator begin, vector<int>::const_iterator end, int i)
	{
	while (begin != end)
	{
	if (*begin == i)
	return begin;
	++begin;
	}
	return end;
	}

# Exercise 9.6

下面的程序有何错误？你应该如何修改它？

	list<int> lst1;
	list<int>::iterator iter1 = lst1.begin(),
	iter2 = lst1.end();
	while (iter1 < iter2) /* ... */

解:

修改成如下：

while (iter1 != iter2)

# Exercise 9.7

为了索引 int 的 vector 中的元素，应该使用什么类型？

解:

vector<int>::size_type

# Exercise 9.8

为了读取 string 的 list 中的元素，应该使用什么类型？如果写入 list ，又应该使用什么类型？

解:

	list<string>::const_iterator // 读
	list<string>::iterator // 写

# Exercise 9.9

begin 和 cbegin 两个函数有什么不同？

解:

begin 返回的是普通迭代器， cbegin 返回的是常量迭代器。

# Exercise 9.10

下面 4 个对象分别是什么类型？

	vector<int> v1;
	const vector<int> v2;
	auto it1 = v1.begin(), it2 = v2.begin();
	auto it3 = v1.cbegin(), it4 = v2.cbegin();

解:

it1 是 vector<int>::iterator

it2 ， it3 和 it4 是 vector<int>::const_iterator

# Exercise 9.11

对 6 种创建和初始化 vector 对象的方法，每一种都给出一个实例。解释每个 vector 包含什么值。

解：

	vector<int> vec; // 0
	vector<int> vec(10); // 10 个 0
	vector<int> vec(10, 1); // 10 个 1
	vector<int> vec{ 1, 2, 3, 4, 5 }; // 1, 2, 3, 4, 5
	vector<int> vec(other_vec); // 拷贝 other_vec 的元素
	vector<int> vec(other_vec.begin(), other_vec.end()); // 拷贝 other_vec 的元素

# Exercise 9.12

对于接受一个容器创建其拷贝的构造函数，和接受两个迭代器创建拷贝的构造函数，解释它们的不同。

解：

接受一个容器创建其拷贝的构造函数，必须容器类型和元素类型都相同。
接受两个迭代器创建拷贝的构造函数，只需要元素的类型能够相互转换，容器类型和元素类型可以不同。

# Exercise 9.13

如何从一个 list<int> 初始化一个 vector<double> ？从一个 vector<int> 又该如何创建？编写代码验证你的答案。

解：

	list<int> ilst(5, 4);
	vector<int> ivc(5, 5);

	vector<double> dvc(ilst.begin(), ilst.end());
	vector<double> dvc2(ivc.begin(), ivc.end());

# Exercise 9.14

编写程序，将一个 list 中的 char * 指针元素赋值给一个 vector 中的 string 。

解：

	std::list<const char*> l{ "hello", "world" };
	std::vector<std::string> v;
	v.assign(l.cbegin(), l.cend());

# Exercise 9.15

编写程序，判定两个 vector<int> 是否相等。

解：

	std::vector<int> vec1{ 1, 2, 3, 4, 5 };
	std::vector<int> vec2{ 1, 2, 3, 4, 5 };
	std::vector<int> vec3{ 1, 2, 3, 4 };

	std::cout << (vec1 == vec2 ? "true" : "false") << std::endl;
	std::cout << (vec1 == vec3 ? "true" : "false") << std::endl;

# Exercise 9.16

重写上一题的程序，比较一个 list<int> 中的元素和一个 vector<int > 中的元素。

解：

	std::list<int> li{ 1, 2, 3, 4, 5 };
	std::vector<int> vec2{ 1, 2, 3, 4, 5 };
	std::vector<int> vec3{ 1, 2, 3, 4 };

	std::cout << (std::vector<int>(li.begin(), li.end()) == vec2 ? "true" : "false") << std::endl;
	std::cout << (std::vector<int>(li.begin(), li.end()) == vec3 ? "true" : "false") << std::endl;

# Exercise 9.17

假定 c1 和 c2 是两个容器，下面的比较操作有何限制？

解：

if (c1 < c2)

c1 和 c2 必须是相同类型的容器并且保存相同类型的元素
元素类型要支持关系运算符

# Sequential Container Operations

# 添加元素

操作	解释
`c.push_back(t)`	在 `c` 尾部创建一个值为 `t` 的元素，返回 `void`
`c.emplace_back(args)`	同上
`c.push_front(t)`	在 `c` 头部创建一个值为 `t` 的元素，返回 `void`
`c.emplace_front(args)`	同上
`c.insert(p, t)`	在迭代器 `p` 指向的元素之前创建一个值是 `t` 的元素，返回指向新元素的迭代器
`c.emplace(p, args)`	同上
`c.insert(p, n, t)`	在迭代器 `p` 指向的元素之前插入 `n` 个值为 `t` 的元素，返回指向第一个新元素的迭代器；如果 `n` 是 0，则返回 `p`
`c.insert(p, b, e)`	将迭代器 `b` 和 `e` 范围内的元素，插入到 `p` 指向的元素之前；如果范围为空，则返回 `p`
`c.insert(p, il)`	`il` 是一个花括号包围中的元素值列表，将其插入到 `p` 指向的元素之前；如果 `il` 是空，则返回 `p`

因为这些操作会改变大小，因此不适用于 array 。
forward_list 有自己专有版本的 insert 和 emplace 。
forward_list 不支持 push_back 和 emplace_back 。
当我们用一个对象去初始化容器或者将对象插入到容器时，实际上放入的是对象的拷贝。
emplace 开头的函数是新标准引入的，这些操作是构造而不是拷贝元素。
传递给 emplace 的参数必须和元素类型的构造函数相匹配。

# 访问元素

操作	解释
`c.back()`	返回 `c` 中尾元素的引用。若 `c` 为空，函数行为未定义
`c.front()`	返回 `c` 中头元素的引用。若 `c` 为空，函数行为未定义
`c[n]`	返回 `c` 中下标是 `n` 的元素的引用， `n` 时候一个无符号证书。若 `n>=c.size()` ，则函数行为未定义
`c.at(n)`	返回下标为 `n` 的元素引用。如果下标越界，则抛出 `out_of_range` 异常

访问成员函数返回的是引用。
at 和下标操作只适用于 string 、 vector 、 deque 、 array 。
back 不适用于 forward_list 。
如果希望下标是合法的，可以使用 at 函数。

# 删除元素

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

会改变容器大小，不适用于 array 。
forward_list 有特殊版本的 erase
forward_list 不支持 pop_back
vector 和 string 不支持 pop_front

# 特殊的 forwad_list 操作

链表在删除元素时需要修改前置节点的内容，双向链表会前驱的指针，但是单向链表没有保存，因此需要增加获取前置节点的方法。
forward_list 定义了 before_begin ，即首前（off-the-begining）迭代器，允许我们再在首元素之前添加或删除元素。

操作	解释
`lst.before_begin()`	返回指向链表首元素之前不存在的元素的迭代器，此迭代器不能解引用。
`lst.cbefore_begin()`	同上，但是返回的是常量迭代器。
`lst.insert_after(p, t)`	在迭代器 `p` 之后插入元素。 `t` 是一个对象
`lst.insert_after(p, n, t)`	在迭代器 `p` 之后插入元素。 `t` 是一个对象， `n` 是数量。若 `n` 是 0 则函数行为未定义
`lst.insert_after(p, b, e)`	在迭代器 `p` 之后插入元素。由迭代器 `b` 和 `e` 指定范围。
`lst.insert_after(p, il)`	在迭代器 `p` 之后插入元素。由 `il` 指定初始化列表。
`emplace_after(p, args)`	使用 `args` 在 `p` 之后的位置，创建一个元素，返回一个指向这个新元素的迭代器。若 `p` 为尾后迭代器，则函数行为未定义。
`lst.erase_after(p)`	删除 `p` 指向位置之后的元素，返回一个指向被删元素之后的元素的迭代器，若 `p` 指向 `lst` 的尾元素或者是一个尾后迭代器，则函数行为未定义。
`lst.erase_after(b, e)`	类似上面，删除对象换成从 `b` 到 `e` 指定的范围。

# 改变容器大小

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

# 获取迭代器

操作	解释
`c.begin()` , `c.end()`	返回指向 `c` 的首元素和尾元素之后位置的迭代器
`c.cbegin()` , `c.cend()`	返回 `const_iterator`

以 c 开头的版本是 C++11 新标准引入的
当不需要写访问时，应该使用 cbegin 和 cend 。

# 反向容器的额外成员

操作	解释
`reverse_iterator`	按逆序寻址元素的迭代器
`const_reverse_iterator`	不能修改元素的逆序迭代器
`c.rbegin()` , `c.rend()`	返回指向 `c` 的尾元素和首元素之前位置的迭代器
`c.crbegin()` , `c.crend()`	返回 `const_reverse_iterator`

不支持 forward_list

# 迭代器

迭代器范围： begin 到 end ，即第一个元素到最后一个元素的后面一个位置。
左闭合区间： [begin, end)
左闭合范围蕴含的编程设定：
- 如果 begin 和 end 相等，则范围为空。
- 如果二者不等，则范围至少包含一个元素，且 begin 指向该范围中的第一个元素。
- 可以对 begin 递增若干次，使得 begin == end 。

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

在向容器添加元素后：
- 如果容器是 vector 或 string ，且存储空间被重新分配，则指向容器的迭代器、指针、引用都会失效。
- 对于 deque ，插入到除首尾位置之外的任何位置都会导致指向容器的迭代器、指针、引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在元素的引用和指针不会失效。
- 对于 list 和 forward_list ，指向容器的迭代器、指针和引用依然有效。
在从一个容器中删除元素后：
- 对于 list 和 forward_list ，指向容器其他位置的迭代器、引用和指针仍然有效。
- 对于 deque ，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、指针、引用都会失效；如果是删除 deque 的尾元素，则尾后迭代器会失效，但其他不受影响；如果删除的是 deque 的头元素，这些也不会受影响。
- 对于 vector 和 string ，指向被删元素之前的迭代器、引用、指针仍然有效。
- 注意：当我们删除元素时，尾后迭代器总是会失效。
- 注意：使用失效的迭代器、指针、引用是严重的运行时错误！
- 建议：将要求迭代器必须保持有效的程序片段最小化。
- 建议：不要保存 end 返回的迭代器。

# 容器内元素的类型约束

元素类型必须支持赋值运算；
元素类型的对象必须可以复制。
除了输入输出标准库类型外，其他所有标准库类型都是有效的容器元素类型。

# Exercise 9.18

编写程序，从标准输入读取 string 序列，存入一个 deque 中。编写一个循环，用迭代器打印 deque 中的元素。

解：

	#include <iostream>
	#include <string>
	#include <deque>

	using std::string; using std::deque; using std::cout; using std::cin; using std::endl;

	int main()
	{
	deque<string> input;
	for (string str; cin >> str; input.push_back(str));
	for (auto iter = input.cbegin(); iter != input.cend(); ++iter)
	cout << *iter << endl;

	return 0;
	}

# Exercise 9.19

重写上一题的程序，用 list 替代 deque 。列出程序要做出哪些改变。

解：

只需要在声明上做出改变即可，其他都不变。

	deque<string> input;
	// 改为
	list<string> input;

# Exercise 9.20

编写程序，从一个 list<int> 拷贝元素到两个 deque 中。值为偶数的所有元素都拷贝到一个 deque 中，而奇数值元素都拷贝到另一个 deque 中。

解：

	#include <iostream>
	#include <deque>
	#include <list>
	using std::deque; using std::list; using std::cout; using std::cin; using std::endl;

	int main()
	{
	list<int> l{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	deque<int> odd, even;
	for (auto i : l)
	(i & 0x1 ? odd : even).push_back(i);

	for (auto i : odd) cout << i << " ";
	cout << endl;
	for (auto i : even)cout << i << " ";
	cout << endl;

	return 0;
	}

# Exercise 9.21

如果我们将第 308 页中使用 insert 返回值将元素添加到 list 中的循环程序改写为将元素插入到 vector 中，分析循环将如何工作。

解：

一样的。如书上所说：

第一次调用 insert 会将我们刚刚读入的 string 插入到 iter 所指向的元素之前的位置。 insert 返回的迭代器恰好指向这个新元素。我们将此迭代器赋予 iter 并重复循环，读取下一个单词。只要继续有单词读入，每步 while 循环就会将一个新元素插入到 iter 之前，并将 iter 改变为新加入元素的尾置。此元素为（新的）首元素。因此，每步循环将一个元素插入到 list 首元素之前的位置。

# Exercise 9.22

假定 iv 是一个 int 的 vector ，下面的程序存在什么错误？你将如何修改？

解：

	vector<int>::iterator iter = iv.begin(),
	mid = iv.begin() + iv.size() / 2;
	while (iter != mid)
	if (*iter == some_val)
	iv.insert(iter, 2 * some_val);

解：

循环不会结束
迭代器可能会失效

要改为下面这样：

	while (iter != mid)
	{
	if (*iter == some_val)
	{
	iter = v.insert(iter, 2 * some_val);
	++iter;
	}
	++iter;
	}

# Exercise 9.23

在本节第一个程序中，若 c.size() 为 1，则 val 、 val2 、 val3 和 val4 的值会是什么？

解：

都会是同一个值（容器中仅有的那个）。

# Exercise 9.24

编写程序，分别使用 at 、下标运算符、 front 和 begin 提取一个 vector 中的第一个元素。在一个空 vector 上测试你的程序。

解：

	#include <iostream>
	#include <vector>

	int main()
	{
	std::vector<int> v;
	std::cout << v.at(0); // terminating with uncaught exception of type std::out_of_range
	std::cout << v[0]; // Segmentation fault: 11
	std::cout << v.front(); // Segmentation fault: 11
	std::cout << *v.begin(); // Segmentation fault: 11
	return 0;
	}

# Exercise 9.25

对于第 312 页中删除一个范围内的元素的程序，如果 elem1 与 elem2 相等会发生什么？如果 elem2 是尾后迭代器，或者 elem1 和 elem2 皆为尾后迭代器，又会发生什么？

解：

如果 elem1 和 elem2 相等，那么不会发生任何操作。
如果elem2 是尾后迭代器，那么删除从 elem1 到最后的元素。
如果两者皆为尾后迭代器，也什么都不会发生。

# Exercise 9.26

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

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

解：

	vector<int> vec(ia, end(ia));
	list<int> lst(vec.begin(), vec.end());

	for (auto it = lst.begin(); it != lst.end(); )
	if (*it & 0x1)
	it = lst.erase(it);
	else
	++it;

	for (auto it = vec.begin(); it != vec.end(); )
	if (!(*it & 0x1))
	it = vec.erase(it);
	else
	++it;

# Exercise 9.27

编写程序，查找并删除 forward_list<int> 中的奇数元素。

解：

	#include <iostream>
	#include <forward_list>

	using std::forward_list;
	using std::cout;

	auto remove_odds(forward_list<int>& flist)
	{
	auto is_odd = [] (int i) { return i & 0x1; };
	flist.remove_if(is_odd);
	}

	int main()
	{
	forward_list<int> data = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	remove_odds(data);
	for (auto i : data)
	cout << i << " ";

	return 0;
	}

# Exercise 9.28

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

	void find_and_insert(forward_list<string>& flst, const string& s1, const string& s2)
	{
	auto prev = flst.before_begin();
	auto curr = flst.begin();
	while (curr != flst.end())
	{
	if (*curr == s1)
	{
	flst.insert_after(curr, s2);
	return;
	}
	prev = curr;
	++curr;
	}
	flst.insert_after(prev, s2);
	}

# Exercise 9.29

假定 vec 包含 25 个元素，那么 vec.resize(100) 会做什么？如果接下来调用 vec.resize(10) 会做什么？

解：

将 75 个值为 0 的元素添加到 vec 的末尾
从 vec 的末尾删除 90 个元素

# Exercise 9.30

接受单个参数的 resize 版本对元素类型有什么限制（如果有的话）？

解：

元素类型必须提供一个默认构造函数。

# Exercise 9.31

第 316 页中删除偶数值元素并复制奇数值元素的程序不能用于 list 或 forward_list 。为什么？修改程序，使之也能用于这些类型。

解：

iter += 2;

因为复合赋值语句只能用于 string 、 vector 、 deque 、 array ，所以要改为：

	++iter;
	++iter;

如果是 forward_list 的话，要增加一个首先迭代器 prev ：

	auto prev = flst.before_begin();
	//...
	curr == flst.insert_after(prev, *curr);
	++curr; ++curr;
	++prev; ++prev;

# Exercise 9.32

在第 316 页的程序中，向下面语句这样调用 insert 是否合法？如果不合法，为什么？

iter = vi.insert(iter, *iter++);

解：

不合法。因为参数的求值顺序是未指定的。

# Exercise 9.33

在本节最后一个例子中，如果不将 insert 的结果赋予 begin ，将会发生什么？编写程序，去掉此赋值语句，验证你的答案。

解：

begin 将会失效。

	#include <iostream>
	#include <vector>

	using std::cout;
	using std::endl;
	using std::vector;

	int main()
	{
	vector<int> data { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	for(auto cur = data.begin(); cur != data.end(); ++cur)
	if(*cur & 0x1)
	cur = data.insert(cur, *cur), ++cur;

	for (auto i : data)
	cout << i << " ";

	return 0;
	}

# Exercise 9.34

假定 vi 是一个保存 int 的容器，其中有偶数值也有奇数值，分析下面循环的行为，然后编写程序验证你的分析是否正确。

	iter = vi.begin();
	while (iter != vi.end())
	if (*iter % 2)
	iter = vi.insert(iter, *iter);
	++iter;

解：

循环永远不会结束。

# How a vector Grows

# vector 对象是如何增长的

vector 和 string 在内存中是连续保存的，如果原先分配的内存位置已经使用完，则需要重新分配新空间，将已有元素从就位置移动到新空间中，然后添加新元素。

# 管理容量的成员函数

操作	解释
`c.shrink_to_fit()`	将 `capacity()` 减少到和 `size()` 相同大小
`c.capacity()`	不重新分配内存空间的话， `c` 可以保存多少个元素
`c.reverse(n)`	分配至少能容纳 `n` 个元素的内存空间

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

# Exercise 9.35

解释一个 vector 的 capacity 和 size 有何区别。

解：

capacity 的值表明，在不重新分配内存空间的情况下，容器可以保存多少元素
而 size 的值是指容器已经保存的元素的数量

# Exercise 9.36

一个容器的 capacity 可能小于它的 size 吗？

解：

不可能。

# Exercise 9.37

为什么 list 或 array 没有 capacity 成员函数？

解：

因为 list 是链表，而 array 不允许改变容器大小。

# Exercise 9.38

编写程序，探究在你的标准实现中， vector 是如何增长的。

解：

	#include <iostream>
	#include <string>
	#include <vector>

	using namespace std;

	int main()
	{
	vector<int> v;

	for (int i = 0; i < 100; i++)
	{
	cout << "capacity: " << v.capacity() << " size: " << v.size() << endl;
	v.push_back(i);
	}
	return 0;
	}

输出：

capacity: 0  size: 0
capacity: 1  size: 1
capacity: 2  size: 2
capacity: 3  size: 3
capacity: 4  size: 4
capacity: 6  size: 5
capacity: 6  size: 6
capacity: 9  size: 7
capacity: 9  size: 8
capacity: 9  size: 9
capacity: 13  size: 10
capacity: 13  size: 11
capacity: 13  size: 12
capacity: 13  size: 13
capacity: 19  size: 14
capacity: 19  size: 15
capacity: 19  size: 16
capacity: 19  size: 17
capacity: 19  size: 18
capacity: 19  size: 19
capacity: 28  size: 20
capacity: 28  size: 21
capacity: 28  size: 22
capacity: 28  size: 23
capacity: 28  size: 24
capacity: 28  size: 25
capacity: 28  size: 26
capacity: 28  size: 27
capacity: 28  size: 28
capacity: 42  size: 29
capacity: 42  size: 30
capacity: 42  size: 31
capacity: 42  size: 32
capacity: 42  size: 33
capacity: 42  size: 34
capacity: 42  size: 35
capacity: 42  size: 36
capacity: 42  size: 37
capacity: 42  size: 38
capacity: 42  size: 39
capacity: 42  size: 40
capacity: 42  size: 41
capacity: 42  size: 42
capacity: 63  size: 43
capacity: 63  size: 44
capacity: 63  size: 45
capacity: 63  size: 46
capacity: 63  size: 47
capacity: 63  size: 48
capacity: 63  size: 49
capacity: 63  size: 50
capacity: 63  size: 51
capacity: 63  size: 52
capacity: 63  size: 53
capacity: 63  size: 54
capacity: 63  size: 55
capacity: 63  size: 56
capacity: 63  size: 57
capacity: 63  size: 58
capacity: 63  size: 59
capacity: 63  size: 60
capacity: 63  size: 61
capacity: 63  size: 62
capacity: 63  size: 63
capacity: 94  size: 64
capacity: 94  size: 65
capacity: 94  size: 66
capacity: 94  size: 67
capacity: 94  size: 68
capacity: 94  size: 69
capacity: 94  size: 70
capacity: 94  size: 71
capacity: 94  size: 72
capacity: 94  size: 73
capacity: 94  size: 74
capacity: 94  size: 75
capacity: 94  size: 76
capacity: 94  size: 77
capacity: 94  size: 78
capacity: 94  size: 79
capacity: 94  size: 80
capacity: 94  size: 81
capacity: 94  size: 82
capacity: 94  size: 83
capacity: 94  size: 84
capacity: 94  size: 85
capacity: 94  size: 86
capacity: 94  size: 87
capacity: 94  size: 88
capacity: 94  size: 89
capacity: 94  size: 90
capacity: 94  size: 91
capacity: 94  size: 92
capacity: 94  size: 93
capacity: 94  size: 94
capacity: 141  size: 95
capacity: 141  size: 96
capacity: 141  size: 97
capacity: 141  size: 98
capacity: 141  size: 99

# Exercise 9.39

解释下面程序片段做了什么：

	vector<string> svec;
	svec.reserve(1024);
	string word;
	while (cin >> word)
	svec.push_back(word);
	svec.resize(svec.size() + svec.size() / 2);

解：

定义一个 vector ，为它分配 1024 个元素的空间。然后通过一个循环从标准输入中读取字符串并添加到 vector 当中。循环结束后，改变 vector 的容器大小（元素数量）为原来的 1.5 倍，使用元素的默认初始化值填充。如果容器的大小超过 1024， vector 也会重新分配空间以容纳新增的元素。

# Exercise 9.40

如果上一题的程序读入了 256 个词，在 resize 之后容器的 capacity 可能是多少？如果读入了 512 个、1000 个、或 1048 个呢？

解：

如果读入了 256 个词， capacity 仍然是 1024
如果读入了 512 个词， capacity 仍然是 1024
如果读入了 1000 或 1048 个词， capacity 取决于具体实现。

# Additional string Operations

# 额外的 string 操作

# 构造 string 的其他方法

操作	解释
`string s(cp, n)`	`s` 是 `cp` 指向的数组中前 `n` 个字符的拷贝，此数组
`string s(s2, pos2)`	`s` 是 `string s2` 从下标 `pos2` 开始的字符的拷贝。若 `pos2 > s2.size()` ，则构造函数的行为未定义。
`string s(s2, pos2, len2)`	`s` 是 `string s2` 从下标 `pos2` 开始的 `len2` 个字符的拷贝。

n , len2 , pos2 都是无符号值。

# substr 操作

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

# 改变 string 的其他方法

操作	解释
`s.insert(pos, args)`	在 `pos` 之前插入 `args` 指定的字符。 `pos` 可以使是下标或者迭代器。接受下标的版本返回指向 `s` 的引用；接受迭代器的版本返回指向第一个插入字符的迭代器。
`s.erase(pos, len)`	删除从 `pos` 开始的 `len` 个字符，如果 `len` 被省略，则删除后面所有字符，返回指向 `s` 的引用。
`s.assign(args)`	将 `s` 中的字符替换成 `args` 指定的字符。返回一个指向 `s` 的引用。
`s.append(args)`	将 `args` 指定的字符追加到 `s` ，返回一个指向 `s` 的引用。
`s.replace(range, args)`	删除 `s` 中范围 `range` 中的字符，替换成 `args` 指定的字符。返回一个指向 `s` 的引用。

# string 搜索操作

string 类提供了 6 个不同的搜索函数，每个函数都有 4 个重载版本。
每个搜索操作都返回一个 string::size_type 值，表示匹配发生位置的下标。如果搜索失败则返回一个名为 string::npos 的 static 成员（类型是 string::size_type ，初始化值是 - 1，也就是 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_first_not_of(args)`	在 `s` 中查找最后一个不在 `args` 中的字符

args 必须是一下的形式之一：

`args` 形式	解释
`c, pos`	从 `s` 中位置 `pos` 开始查找字符 `c` 。 `pos` 默认是 0
`s2, pos`	从 `s` 中位置 `pos` 开始查找字符串 `s` 。 `pos` 默认是 0
`cp, pos`	从 `s` 中位置 `pos` 开始查找指针 `cp` 指向的以空字符结尾的 C 风格字符串。 `pos` 默认是 0
`cp, pos, n`	从 `s` 中位置 `pos` 开始查找指针 `cp` 指向的前 `n` 个字符。 `pos` 和 `n` 无默认值。

# s.compare 的几种参数形式

逻辑类似于 C 标准库的 strcmp 函数，根据 s 是等于、大于还是小于参数指定的字符串， s.compare 返回 0、正数或负数。

参数形式	解释
`s2`	比较 `s` 和 `s2`
`pos1, n1, s2`	比较 `s` 从 `pos1` 开始的 `n1` 个字符和 `s2`
`pos1, n1, s2, pos2, n2`	比较 `s` 从 `pos1` 开始的 `n1` 个字符和 `s2`
`cp`	比较 `s` 和 `cp` 指向的以空字符结尾的字符数组
`pos1, n1, cp`	比较 `s` 从 `pos1` 开始的 `n1` 个字符和 `cp` 指向的以空字符结尾的字符数组
`pos1, n1, cp, n2`	比较 `s` 从 `pos1` 开始的 `n1` 个字符和 `cp` 指向的地址开始 `n2` 个字符

# string 和数值转换

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

# Exercise 9.41

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

解：

	vector<char> v{ 'h', 'e', 'l', 'l', 'o' };
	string str(v.cbegin(), v.cend());

# Exercise 9.42

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

解：

使用 reserve(100) 函数预先分配 100 个元素的空间。

# Exercise 9.43

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

解：

	#include <iterator>
	#include <iostream>
	#include <string>
	#include <cstddef>

	using std::cout;
	using std::endl;
	using std::string;

	auto replace_with(string &s, string const& oldVal, string const& newVal)
	{
	for (auto cur = s.begin(); cur <= s.end() - oldVal.size(); )
	if (oldVal == string{ cur, cur + oldVal.size() })
	cur = s.erase(cur, cur + oldVal.size()),
	cur = s.insert(cur, newVal.begin(), newVal.end()),
	cur += newVal.size();
	else
	++cur;
	}

	int main()
	{
	string s{ "To drive straight thru is a foolish, tho courageous act." };
	replace_with(s, "tho", "though");
	replace_with(s, "thru", "through");
	cout << s << endl;

	return 0;
	}

# Exercise 9.44

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

解：

	#include <iostream>
	#include <string>

	using std::cout;
	using std::endl;
	using std::string;

	auto replace_with(string &s, string const& oldVal, string const& newVal)
	{
	for (size_t pos = 0; pos <= s.size() - oldVal.size();)
	if (s[pos] == oldVal[0] && s.substr(pos, oldVal.size()) == oldVal)
	s.replace(pos, oldVal.size(), newVal),
	pos += newVal.size();
	else
	++pos;
	}

	int main()
	{
	string str{ "To drive straight thru is a foolish, tho courageous act." };
	replace_with(str, "tho", "though");
	replace_with(str, "thru", "through");
	cout << str << endl;
	return 0;
	}

# Exercise 9.45

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

解：

	#include <iostream>
	#include <string>

	using std::string;
	using std::cin;
	using std::cout;
	using std::endl;

	// Exercise 9.45
	auto add_pre_and_suffix(string name, string const& pre, string const& su)
	{
	name.insert(name.begin(), pre.cbegin(), pre.cend());
	return name.append(su);
	}

	int main()
	{
	string name("Wang");
	cout << add_pre_and_suffix(name, "Mr.", ", Jr.") << endl;
	return 0;
	}

# Exercise 9.46

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

解：

	#include <iostream>
	#include <string>

	auto add_pre_and_suffix(std::string name, std::string const& pre, std::string const& su)
	{
	name.insert(0, pre);
	name.insert(name.size(), su);
	return name;
	}

	int main()
	{
	std::string name("alan");
	std::cout << add_pre_and_suffix(name, "Mr.", ",Jr.");
	return 0;
	}

# Exercise 9.47

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

解：

	#include <iostream>
	#include <string>

	using namespace std;

	int main()
	{
	string numbers("0123456789");
	string s("ab2c3d7R4E6");

	cout << "numeric characters: ";
	for (int pos = 0; (pos = s.find_first_of(numbers, pos)) != string::npos; ++pos)
	{
	cout << s[pos] << " ";
	}

	cout << "\nalphabetic characters: ";
	for (int pos = 0; (pos = s.find_first_not_of(numbers, pos)) != string::npos; ++pos)
	{
	cout << s[pos] << " ";
	}

	return 0;
	}

# Exercise 9.48

假定 name 和 numbers 的定义如 325 页所示， numbers.find(name) 返回什么？

解：

返回 string::npos

# Exercise 9.49

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

解：

	#include <string>
	#include <fstream>
	#include <iostream>

	using std::string; using std::cout; using std::endl; using std::ifstream;

	int main()
	{
	ifstream ifs("../data/letter.txt");
	if (!ifs) return -1;

	string longest;
	auto update_with = [&longest](string const& curr)
	{
	if (string::npos == curr.find_first_not_of("aceimnorsuvwxz"))
	longest = longest.size() < curr.size() ? curr : longest;
	};
	for (string curr; ifs >> curr; update_with(curr));
	cout << longest << endl;

	return 0;
	}

# Exercise 9.50

编写程序处理一个 vector<string> ，其元素都表示整型值。计算 vector 中所有元素之和。修改程序，使之计算表示浮点值的 string 之和。

解：

	#include <iostream>
	#include <string>
	#include <vector>

	auto sum_for_int(std::vector<std::string> const& v)
	{
	int sum = 0;
	for (auto const& s : v)
	sum += std::stoi(s);
	return sum;
	}

	auto sum_for_float(std::vector<std::string> const& v)
	{
	float sum = 0.0;
	for (auto const& s : v)
	sum += std::stof(s);
	return sum;
	}

	int main()
	{
	std::vector<std::string> v = { "1", "2", "3", "4.5" };
	std::cout << sum_for_int(v) << std::endl;
	std::cout << sum_for_float(v) << std::endl;

	return 0;
	}

# Exercise 9.51

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

解：

	#include <iostream>
	#include <string>
	#include <vector>

	using namespace std;
	class My_date{
	private:
	unsigned year, month, day;
	public:
	My_date(const string &s){

	unsigned tag;
	unsigned format;
	format = tag = 0;

	// 1/1/1900
	if(s.find_first_of("/")!= string :: npos)
	{
	format = 0x01;
	}

	// January 1, 1900 or Jan 1, 1900
	if((s.find_first_of(',') >= 4) && s.find_first_of(',')!= string :: npos){
	format = 0x10;
	}
	else{ // Jan 1 1900
	if(s.find_first_of(' ') >= 3
	&& s.find_first_of(' ')!= string :: npos){
	format = 0x10;
	tag = 1;
	}
	}

	switch(format){

	case 0x01:
	day = stoi(s.substr(0, s.find_first_of("/")));
	month = stoi(s.substr(s.find_first_of("/") + 1, s.find_last_of("/")- s.find_first_of("/")));
	year = stoi(s.substr(s.find_last_of("/") + 1, 4));

	break;

	case 0x10:
	if( s.find("Jan") < s.size() ) month = 1;
	if( s.find("Feb") < s.size() ) month = 2;
	if( s.find("Mar") < s.size() ) month = 3;
	if( s.find("Apr") < s.size() ) month = 4;
	if( s.find("May") < s.size() ) month = 5;
	if( s.find("Jun") < s.size() ) month = 6;
	if( s.find("Jul") < s.size() ) month = 7;
	if( s.find("Aug") < s.size() ) month = 8;
	if( s.find("Sep") < s.size() ) month = 9;
	if( s.find("Oct") < s.size() ) month =10;
	if( s.find("Nov") < s.size() ) month =11;
	if( s.find("Dec") < s.size() ) month =12;

	char chr = ',';
	if(tag == 1){
	chr = ' ';
	}
	day = stoi(s.substr(s.find_first_of("123456789"), s.find_first_of(chr) - s.find_first_of("123456789")));

	year = stoi(s.substr(s.find_last_of(' ') + 1, 4));
	break;
	}
	}

	void print(){
	cout << "day:" << day << " " << "month: " << month << " " << "year: " << year;
	}
	};
	int main()
	{
	My_date d("Jan 1 1900");
	d.print();
	return 0;
	}

# Container Adaptors

# 容器适配器（adapter）

适配器是使一事物的行为类似于另一事物的行为的一种机制，例如 stack 可以使任何一种顺序容器以栈的方式工作。
初始化 deque<int> deq; stack<int> stk(deq); 从 deq 拷贝元素到 stk 。
创建适配器时，指定一个顺序容器，可以覆盖默认的基础容器： stack<string, vector<string> > str_stk; 。

# 适配器的通用操作和类型

操作	解释
`size_type`	一种类型，须以保存当前类型的最大对象的大小
`value_type`	元素类型
`container_type`	实现适配器的底层容器类型
`A a;`	创建一个名为 `a` 的空适配器
`A a(c)`	创建一个名为 `a` 的适配器，带有容器 `c` 的一个拷贝
关系运算符	每个适配器都支持所有关系运算符： `==` 、 `!=` 、 `<` 、 `<=` 、 `>` 、 `>=` 这些运算符返回底层容器的比较结果
`a.empty()`	若 `a` 包含任何元素，返回 `false` ; 否则返回 `true`
`a.size()`	返回 `a` 中的元素数目
`swap(a, b)`	交换 `a` 和 `b` 的内容， `a` 和 `b` 必须有相同类型，包括底层容器类型也必须相同
`a.swap(b)`	同上

# stack

操作	解释
`s.pop()`	删除栈顶元素，不返回。
`s.push(item)`	创建一个新元素，压入栈顶，该元素通过拷贝或移动 `item` 而来
`s.emplace(args)`	同上，但元素由 `args` 来构造。
`s.top()`	返回栈顶元素，不删除。

定义在 stack 头文件中。
stack 默认基于 deque 实现，也可以在 list 或 vector 之上实现。

# queue 和 priority_queue

操作	解释
`q.pop()`	删除队首元素，但不返回。
`q.front()`	返回队首元素的值，不删除。
`q.back()`	返回队尾元素的值，不删除。只适用于 `queue`
`q.top()`	返回具有最高优先级的元素值，不删除。
`q.push(item)`	在队尾压入一个新元素。
`q.emplace(args)`

定义在 queue 头文件中。
queue 默认基于 deque 实现， priority_queue 默认基于 vector 实现。
queue 可以在 list 或 vector 之上实现， priority_queue 也可以用 deque 实现。

# Exercise 9.52

使用 stack 处理括号化的表达式。当你看到一个左括号，将其记录下来。当你在一个左括号之后看到一个右括号，从 stack 中 pop 对象，直至遇到左括号，将左括号也一起弹出栈。然后将一个值（括号内的运算结果） push 到栈中，表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。

解：

这道题可以延伸为逆波兰求值，以及中缀转后缀表达式。

	#include <stack>
	#include <string>
	#include <iostream>

	using std::string; using std::cout; using std::endl; using std::stack;

	int main()
	{
	string expression{ "This is (pezy)." };
	bool bSeen = false;
	stack<char> stk;
	for (const auto &s : expression)
	{
	if (s == '(') { bSeen = true; continue; }
	else if (s == ')') bSeen = false;

	if (bSeen) stk.push(s);
	}

	string repstr;
	while (!stk.empty())
	{
	repstr += stk.top();
	stk.pop();
	}

	expression.replace(expression.find("(")+1, repstr.size(), repstr);

	cout << expression << endl;

	return 0;
	}

# Chapter Summary

🍓：）