《C++ Primer》第9章 顺序容器（二）

参考资料：

• 《C++ Primer》第5版
• 《C++ Primer 习题集》第5版

9.3 顺序容器操作（P305）

9.3.1 向容器中添加元素（P305）

使用push_back

除 array 和 forward_list 外，每个顺序容器都支持 push_back ：

vector<string> sentence;
while(cin >> word){
    sentence.push_back(word);
}
1
2
3
4

对 push_back 的调用相当于在容器尾部创建了一个新元素，将容器的 size 增大 1 ，该元素的值为 word 的拷贝。

使用push_front

list 、forward_list 、deque 还支持 push_front 操作，顾名思义就是把元素添加到容器头部。

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

insert 提供了更一般的添加元素功能，它允许我们在容器中任意位置添加 0 个或多个元素。

每个 insert 函数都接受一个迭代器参数作为第一个参数，表示将元素插入到该迭代器所指位置之前。

插入范围内元素

insert 函数还可以接受更多参数，方式和容器构造函数类似：

vector<string> vs;
list<string> ls = {"hello", "world", "hi"};
vs.insert(vs.begin(), 10, "hi");
vs.insert(vs.begin(), ls.begin(), ls.end());
vs.insert(ls.begin(), ls.begin(), ls.end());    // 错误，拷贝范围和添加位置不能来自同一个容器
1
2
3
4
5

在新标准下，insert 返回第一个新加入元素的迭代器，如果没有新加入元素，则将参数迭代器返回。

使用insert的返回值

vector<int> vi = {0, 1, 2, 3, 4, 5};
auto it = vi.begin();
while(it != vi.end()){
    if(*it % 2){
        vi.insert(it, *it);
    }
    it++;
}
// vi的内容：0 1 1 2 3 3 4 5 5 
1
2
3
4
5
6
7
8
9

使用emplace操作

新标准引入了 emplace_front 、emplace 和emplace_back ，这些操作构造而不是拷贝元素。

调用 emplace 成员时，将参数传递给元素类型的构造函数直接构造元素：

// 使用三个参数的Sales_data构造函数
c.emplace_back("978-0590353403", 25, 15.99);
1
2

在调用 emplace_back 会在容器管理的内存空间中直接创建对象，push_back 则会创建一个局部临时对象，并将其压入容器中。

9.3.2 访问元素（P309）

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

front 、back 、at 和下标返回的都是引用。

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

提供快速随机访问的容器都提供下标运算符。越界的下标是一种严重的程序错误，而且编译器不会检查这种错误。

如果我们希望下标是合法的，可以使用 at 成员函数，如果下标越界，at 会抛出 out_of_range 异常。

9.3.3 删除元素（P311）

pop_front和pop_back成员函数

二者的返回值均为 void 。

从容器内部删除一个元素

erase 从容器指定位置删除元素，可以删除一个由迭代器指定的单个元素，也可以删除由一对迭代器指定范围内的所有元素，返回删除的最后一个元素之后位置的迭代器。

// 删除奇数元素
vector<int> vi = { 0,1,2,3,4,5,6,7,8,9 };
auto cur = vi.begin();
while (cur != vi.end()) {
	if (*cur % 2) {
		cur = vi.erase(cur);
	}
	else {
		cur++;
	}
}
1
2
3
4
5
6
7
8
9
10
11

删除多个元素

vi.erase(vi.begin(), vi.end());
1

9.3.4 特殊的forward_list操作

回忆我们在数据结构中学过的知识，在单向链表中删除元素，往往需要用到待删除元素的上一个元素。

由于删除方式的限制，forward_list 定义了 insert_after 、emplace_after 和 erase_after 操作，也定义了 before_begin 来返回首前（off-the-beginning）迭代器。

在 forward_list 中添加或删除元素时，我们必须同时关注指向待删除元素的迭代器和指向其前驱的迭代器：

// forward_list版删除奇数元素
forward_list<int> fi = { 0,1,2,3,4,5,6,7,8,9 };
auto pre = fi.before_begin();
auto cur = fi.begin();
while (cur != fi.end()) {
    if (*cur % 2) {
        cur = fi.erase_after(pre);
    }
    else {
        pre = cur;
        ++cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

9.3.5 改变容器大小（P314）

我们可以用 resize 函数来增大或缩小容器，如果当前大小大于要求大小，容器后部的元素会被删除；如果当前大小小于要求大小，则会将新的元素添加到容器后面：

forward_list<int> fi = { 0,1,2,3,4,5,6,7,8,9 };
fi.resize(5);    // fi的内容：0,1,2,3,4
fi.resize(10, 5);    // fi的内容：0 1 2 3 4 5 5 5 5 5
1
2
3

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

向容器中添加元素或从容器中删除元素可能令指向容器元素的指针、引用、迭代器失效。

向容器添加元素后：

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

从容器删除元素后：

• 对于 list 和 forward_list ，指向容器其他位置的迭代器（包括尾后、首前）、引用、指针仍然有效。
• 对于 deque ，如果在首尾之外的任何位置删除元素，指向该容器中元素的迭代器、指针、引用都会失效；如果删除 deque 的尾元素，则尾后迭代器会失效，其他迭代器、指针、引用不受影响；如果删除首元素，除尾后迭代器外的其他迭代器、指针、引用不受影响（尾后迭代器是否会失效书里没说清楚）。
• 对于 vector 和 string ，指向被删元素之前元素的迭代器、指针、引用仍然有效，尾后迭代器总是会失效。

不要保存end返回的迭代器

如果在一个循环中插入、删除 deque 、string 、vector 中的元素，不要缓存 end 返回的迭代器。

9.4 vector对象是如何增长的

为了支持快速随机访问，vector 将元素存储在一片连续的空间中。如果添加元素时，vector 已没有足够的空间容纳新的元素，容器必须重新分配新的内存空间，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。

如果我们每添加一个元素就重新分配一次元素，那么性能将非常低。为此，标准库实现者通常会分配比需求更大的新内存空间，此时 vector 的扩张速度通常比 list 和 deque 还快。

管理容量的成员函数

如果需求大小大于当前容量，reserve 至少分配与需求一样大的空间；如果需求大小小于等于当前容量，reserve 什么都不做。也就是说，调用 reserve 后，capacity 将大于传递给 reserve 的参数。

resize 成员只改变容器中的元素数量，而不是容器的容量：

// VS2022
vector<int> vi = {0};    // capacity = 1
vi.reserve(0);    // capacity = 1
vi.reserve(100);    // capacity = 100
vi.resize(0);    // capacity = 100, size = 0
1
2
3
4
5

shrink_to_fit 可以减少容器的容量，但其只是一个请求，具体的实现可以忽略此请求。

capacity 和 size

每个 vector 实现 都可以选择自己的内存分配策略，但必须遵守一条原则：只有当迫不得已时才可以重新分配策略。

通常来说，在一个空的 vector 上调用 n 次 push_back 的时间复杂度不能超过 n 的常数倍。