C++ 09顺序容器

2021-08-13

顺序容器概述

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

顺序容器类型

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

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

容器操作

类型

操作	解释
`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`

添加元素

操作	解释
`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返回的迭代器
- 建议：每次改变容器的操作之后都正确地重新定位迭代器

std::vector<int> arr = {1, 2, 3 ,4 ,5};
auto iter = arr.begin();

while (iter != arr.end()) { //每次都重新计算end
    if (*iter == 1) {
        iter = arr.insert(iter, 0); //iter指向0
        iter += 2; //跳过0，1, iter指向3
    } else if (*iter == 5) {
        iter = arr.erase(iter); //iter == end
    } else {
        iter++;
    }
}

容器内元素的类型约束

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

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

额外的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`

容器适配器（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()`	返回具有最高优先级的元素值，不删除。只适用于`priority_queue`
`q.push(item)`	在队尾压入一个新元素
`q.emplace(args)`	同上,但元素由`args`来构造

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

顺序容器概述

顺序容器类型

容器操作

类型

构造函数

赋值和swap

大小

添加元素

访问元素

删除元素

特殊的forwad_list操作

改变容器大小

获取迭代器

反向容器的额外成员

迭代器

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

容器内元素的类型约束

vector对象是如何增长的

管理容量的成员函数

额外的string操作

构造string的其他方法

substr操作

改变string的其他方法

string搜索操作

s.compare的几种参数形式

string和数值转换

容器适配器（adapter）

适配器的通用操作和类型

stack

queue和priority_queue

赋值和`swap`