第 9 章 顺序容器
sequential container
9.1 顺序容器概述
vector
deque
list
forward_list
array
string
9.2 容器库概览
| 类型别名 | 意义 |
|---|---|
| iterator | 迭代器类型 |
| const_iterator | 不能修改元素的迭代器类型 |
| size_type | 容器类型最大可能的大小 |
| difference_type | 两个迭代器间的距离 |
| value_type | 元素类型 |
| reference | 元素的左值类型与 value_type& 相同 |
| const_reference | 元素的 const 左值类型 |
9.2.1 迭代器
一个迭代器范围 iterator range 由一对迭代器表示。begin 和 end 范围为左闭合区间 left-inclusive interval $[begin, end)$。
9.2.2 容器类型成员
有了类型别名，我们就可以在不了解容器中元素类型的情况下使用它。
使用 assign
赋值要求容器完全一致，assign 是可以转换类型的。
使用 swap
除了 array 其他容器的 swap 是 $O(1)$ 的。
9.2.6 容器大小操作
max_size 返回大于等于该类型所能容纳的最大元素数的值。
forward_list 支持 max_size 和 empty 但不支持 size。
9.2.7 关系运算符
除了无序关联容器外的所有容器都支持关系运算符。
两个容器的大小关系与字符串的字典序类似：
连个容器如果大小相同且元素两两对应相等，则说这两个容器相等。否则两个容器不等。
两个容器大小不同，但元素少的是元素多的前缀，则元素少的容器较小。
如果前缀不同则第一个不同元素的大小关系决定元素大小。
9.3 顺序容器操作
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void show(const vector<int> &vec) {
for(int i : vec) cout << i << " ";
cout<<endl;
}
int main() {
vector<int> vec = {0, 1, 2};
vec.insert(vec.begin(), 3);
show(vec); // 3 0 1 2
vec.insert(vec.end(), 4);
show(vec); // 3 0 1 2 4
vec.insert(vec.begin(), 5, 5);
show(vec); // 5 5 5 5 5 0 1 2 4
set<int> se = {6, 7, 8};
vec.insert(vec.end(), se.begin(), se.end());
show(vec); // 5 5 5 5 5 0 1 2 4 6 7 8
set<char> se_c = {'a', 'b', 'c'};
vec.insert(vec.begin(), se_c.begin(), se_c.end());
show(vec); // 97 98 99 5 5 5 5 5 0 1 2 4 6 7 8
return 0;
}
9.3.2 访问元素
c[n]
c.at(n)
如果 n 是一个范围外的值则，两种取元素的方式是行为是不同的，前者行为是未定义的，后者则会抛出 out_of_range 异常
以上两种访问方式和 back() front() 都是返回元素的引用。
9.3.3 删除元素
c.erase(it) // 删除迭代器位置的元素，返回删除元素之后元素的迭代器。如果 it 是尾后迭代器则行为未定义
c.erase(it_begin, it_end) // 删除迭代器中间的元素 [it_begin, it_end) 中间的元素，
// 返回最后一个被删元素的下一个元素的迭代器
// 如果 it_end 是尾后迭代器，则也会返回尾后迭代器
#include <iostream>
#include <set>
using namespace std;
void show(const set<int> &se) {
for(int i : se) cout << i << " ";
cout<<endl;
}
int main() {
set<int> se = {0, 1, 2, 3, 4, 5};
show(se); // 0 1 2 3 4 5
auto it_b = se.find(1);
auto it_e = se.find(3);
se.erase(it_b, it_e);
show(se); // 0 3 4 5
return 0;
}
9.3.4 特殊的 forward_list
lst.before_begin(); // 首前迭代器 off-the-beginning
lst.insert_after(p, t); // 迭代器 p 之后插入 t
lst.erase_after(p); // 删除 p 之后的元素
9.3.5 改变容器大小
resize 可以调整容器大小，如果 size 变小会删除后部的元素，如果 size 变大可以在 resize 的第二个参数提供初始值。
9.3.6 容器操作可能使迭代器失效
向容器添加元素后：
vector 和 string 如果存储空间被重新分配，则指向容器的迭代器、指针、引用都会失效。否则插入位置前的有效，插入位置后的失效。
对于 deque 插入到除首尾以外的位置，所有迭代器失效、指向元素指针、引用都会失效。插入到首尾迭代器失效，但指向存在的元素的指针和引用不会失效
对于 list、forward_list 指向容器的迭代器、指针和引用仍然有效。
从容器删除元素后：
被删除元素的迭代器、指针和引用会失效
对于 list 和 forward_list 其他位置的迭代器、指针和引用仍旧有效
对 deque 首尾外任何位置删除元素，那么所有迭代器、指针和引用都会失效。删除首尾元素、其他元素迭代器指针引用不会受到影响。删除尾元素，尾后迭代器会受到影响。
对 vector 和 string。指向被删元素之前元素的迭代器、引用和指针有效。尾后迭代器总会失效。
注意在迭代删除元素时，不要使用提前保存的尾后迭代器。
9.4 vector 对象时如何增长的
c.shrink_to_fit(); // 将 capacity 减少为与 size() 相同大小
c.capacity(); // 不重新分配内存空间的话，c 可以保存多少元素
c.reserve(n); // 分配至少能容纳 n 个元素的内存空间
shrink_to_fit() 只是一个请求，并不保证退还内存。
reserve() 的值小于当前容量时不会发生任何操作。
9.5 额外的 string 操作
9.5.1 构造 string 的其他方法
从其他 string 构造 string
string s(cp, n); // s 是 cp 指向的数组中前 n 个字符的拷贝。
// 数组应至少包含 n 个字符。
string s(s2, pos2); // s 是 string s2 从下标 pos2 开始的字符串的拷贝。
// 若 pos2 > s2.size() 则行为未定义
string s(s2, pos2, len2); // s 是 string s2 从下标 pos2 开始
// len2 个字符的拷贝
// 若 pos2 > s2.size() 则行为未定义
// 无论 len2 值是多少，最多只能拷贝
// s2.size() - pos2 个字符
substr 操作
s.substr(pos, len);
9.5.2 改变 string 的其他方法
string 除了能使用接受迭代器版本的 insert 和 erase 也能使用接受下标版本的 insert 和 erase。
string 还提供了 append 和 replace 函数
9.5.3 string 搜索操作
string 的搜索函数会返回一个 string::size_type 的值，成功时返回匹配位置的下标，失败时返回 string::npos。标准库将 string::npos 初始化为 -1，由于它是 unsigned 类型，因此实际上是任何 string 最大的可能大小。
s.find(args);
s.rfind(args);
s.find_first_of(args);
s.find_last_of(args);
s.find_first_not_of(args);
s.find_last_not_of(args);
其中 args 可以是
c, pos // 从 pos 开始查找字符 c。pos 默认为 0
s2, pos // 从 pos 开始查找字符 s2。pos 默认为 0
cp, pos // 从 pos 开始查找 cp 指向的空字符结尾的 C 风格字符串
// pos 默认为 0
cp, pos, n // 从 pos 开始查找指针 cp 指向的数组的前 n 个字符。
// pos 和 n 无默认值
9.5.4 compare 函数
s.compare(s2);
s.compare(pos1, n1, s2);
s.compare(pos1, n1, s2, pos2, n2);
s.compare(cp);
s.compare(pos1, n1, cp);
s.compare(pos1, n1, cp, n2);
9.5.5 数值转换
to_string(val);
stoi(s, p, b); // b 是进制，默认为 10
stol(s, p, b); // 从下标 p 位置开始，默认为 0
stoul(s, p, b);
stoll(s, p, b);
stoull(s, p, b);
stof(s, p);
stod(s, p);
stold(s, p);
9.6 容器适配器
适配器 adaptor 是一种机制，使得某种事物行为看起来像另一种不同的类型。
容器、迭代器和函数都有适配器。
所有容器适配器支持的操作和类型
size_type;
value_type;
container_type;
A a; // 创建空适配器
A a(c); // 创建名为 a 的适配器，带有容器 c 的一个拷贝
==, !=, <, <=, >, >=
a.empty();
a.size();
swap(a, b);
a.swap(b);
Next: 《C++ Primer》 拾遗 第 10 章 泛型算法