第9章 顺序容器
9.1 顺序容器概述
1. 顺序容器类型
| 顺序容器 | 描述 |
|---|---|
| vector | 可变大小数组 |
| string | 与vector类型，但专门用于保存字符 |
| deque | 双端队列 |
| list | 双向链表 |
| forward_list | 单向链表 |
| array | 固定大小数组 |
2. 选择容器的基本原则
- 除非有很好的理由选择其它容器，否则应使用vector。
- 若程序要求随机访问元素，应使用vector或deque。
- 若程序要求在头尾位置插入或删除元素，不会在中间位置进行插入和删除，应使用deque。
- 除非程序中有很多的小元素，且对空间额外开销要求高，否则不要使用list或forward_list。
- 若程序要求在容器中间插入或删除元素，应使用list或forward_list。
- 若程序只有在读取输入时才需要在容器中间位置添加元素，之后只需随机访问元素。针对这种情况，需明确是否一定要在容器中间位置添加元素：通过其它途径实现居中添加元素，如对vector使用sort重排元素顺序可避免在中间位置添加元素；若一定，则在读取输入时用list，输入完成后将list拷贝到vector。
提示：若不确定选择哪个容器，建议在程序中只使用vector和list的公共操作：使用迭代器，不使用下标操作，避免随机访问。
9.2 容器库概览
1. 标准迭代器支持的运算
| 运算 | 描述 |
|---|---|
| *iter | 返回iter所指元素的引用 |
| iter->mem | 解引用iter，并访问该元素的成员mem，等价于(*iter).mem |
| --iter1，++iter | 迭代器向前（向后）移动一个位置 forward_list不支持-- |
| ==、!= | 判断两个迭代器是否相等（不相等） |
2. 部分容器支持的迭代器运算（string、vector、deque、array）
| 运算 | 描述 |
|---|---|
| iter + n iter - n |
迭代器+整型=迭代器，迭代器-整型=迭代器 迭代器向前或向后移动n个位置 |
| iter += n iter -= n |
等价于iter = iter + n; iter = iter - n |
| iter1 - iter2 | 迭代器-迭代器=距离 距离的类型：different_type |
| >、>=、<、<= | 比较两个迭代器之间的距离 无序关联容器不支持 |
3. 容器类型成员
| 类型别名 | 描述 |
|---|---|
| iterator | 此容器类型的迭代器类型 |
| const_iterator | 常量迭代器类型，可访问不可修改元素 |
| size_type | 无符号整数类型，足够容纳该容器类型所有可能的容量 |
| different_type | 带符号整数类型，足够容纳两个迭代器之间的距离 |
| value_type | 元素的类型 |
| reference | 元素的左值类型，等价于value_type & |
| const_refernence | 元素的const左值类型，等价于const value_type & |
4. 获取迭代器
| 获取迭代器 | 描述 |
|---|---|
| c.begin()、c.end() | 指向c中首元素和尾后元素的迭代器 若c是const，则返回const_iterator 若c不是const，则返回iterator |
| c.cbegin()、c.cend() | 指向c中首元素和尾后元素的迭代器 返回const_iterator |
5. 反向容器（forward_list不支持）
| 额外成员 | 描述 |
|---|---|
| reverse_iterator | 指按逆序寻址元素的迭代器 |
| const_reverse_iterator | 只能读取不能修改元素的逆序迭代器 |
| c.rbegin()、c.rend() | 返回指向c的尾元素和首前位置的迭代器 若c是const，则返回const_reverse_iterator 若c不是const，则返回reverse_iterator |
| c.rcbegin()、c.rcend() | 返回指向c的尾元素和首前位置的迭代器 返回const_reverse_iterator |
6. 容器定义和初始化
| 定义与初始化 | 描述 |
|---|---|
| C c | 默认构造函数，元素个数为空 若是array，则固定个数的元素默认初始化 若array元素类型是类类型，则该类必须含有默认构造函数 |
| C c1(c2) C c1=c2 |
利用c2初始化c1 c1和c2容器类型和元素类型相同 若是array，还要求元素个数相同 |
| C c{a,b,...} C c={a,b,...} |
利用初始化列表来初始化c 列表元素类型与C中元素类型相容 若是array，还要求元素个数<=array大小，遗漏的元素进行值初始化 |
| C c(b,e) | 利用[b,e)内的元素初始化c 范围内元素类型与C的元素类型可转换 array不支持 |
| C seq(n) | 创建seq，并添加n个值初始化的元素 元素类型是内置类型或者具有默认构造函数的类类型 此构造函数是explicit的 string、array不支持 |
| C seq(n,t) | 创建seq，并添加n个值为t的元素 array不支持 |
7. 赋值和swap
| 赋值 | 描述 |
|---|---|
| c1=c2 | 将c2元素拷贝到c1 c1和c2容器类型和元素类型相同 若是array，还要求元素个数相同 |
| c={a,b,...} | 将初始化列表中的元素拷贝到c 列表元素类型与C中元素类型相容 若是array，还要求元素个数<=array大小，遗漏的元素进行值初始化 |
| seq.assign(il) | 将初始化列表il拷贝到seq 关联容器、array不支持 |
| seq.assign(b,e) | 将[b,e)内的元素拷贝到seq 范围内元素类型与seq的元素类型可转换 关联容器、array不支持 |
| seq.assign(n,t) | 将n个值为t的元素拷贝到seq 关联容器、array不支持 |
| swap | 描述 |
|---|---|
| swap(c1,c2) c1.swap(c2) |
交换c1和c2中的元素 只交换两个容器的内部数据结构（即元素地址） 指向容器元素的原迭代器、引用和指针仍有效 若是array，真正交换元素值 若是string，指向容器元素的原迭代器、引用和指针失效 |
8. 容器大小操作
| 容器大小 | 描述 |
|---|---|
| c.size() | c中的元素数目 forward_list不支持 |
| c.max_size() | c可保存的最大元素数目 |
| c.empty() | 若c为空返回ture，否则返回false |
9.3 顺序容器操作
1. 顺序容器访问元素
| 顺序容器访问元素 | 描述 |
|---|---|
| c.front() | 返回c中首元素的引用 forward_list不支持 |
| c.beak() | 返回c中尾元素的引用 |
| c[n] | 返回c中下标为n的元素的引用，0 <= n < c.size() 只支持vector、string、deque、array |
| c.at(n) | 返回c中下标为n的元素的引用，0 <= n < c.size() 若下标越界，则抛出异常out_of_range 只支持vector、string、deque、array |
2. 顺序容器添加元素（array不支持）
| 顺序容器添加元素 | 描述 |
|---|---|
| c.push_front(t) | 在c的首部创建一个值为t的元素 返回void vector、string不支持 |
| c.emplace_front(args) | 在c的首部创建一个由args创建的元素 返回void vector、string不支持 |
| c.push_back(t) | 在c的尾部创建一个值为t的元素 返回void forward_list不支持 |
| c.emplace_back(args) | 在c的尾部创建一个由args创建的元素 返回void forward_list不支持 |
| c.insert(p,t) | 在迭代器p之前创建一个值为t的元素 返回指向新添加的元素的迭代器 forward_list不支持 |
| c.emplace(p,args) | 在迭代器p之前创建一个由args创建的元素 返回指向新添加的元素的迭代器 forward_list不支持 |
| c.insert(p,n,t) | 在迭代器p之前创建n个值为t的元素 返回指向新添加的第一个元素的迭代器 forward_list不支持 |
| c.insert(p,b,e) | 在迭代器p之前插入[b,e)内的元素 返回指向新添加的第一个元素的迭代器 forward_list不支持 |
| c.insert(p,il) | 在迭代器p之前插入初始值列表il中的元素 返回指向新添加的第一个元素的迭代器 forward_list不支持 |
3. 顺序容器删除元素（array不支持）
| 顺序容器删除元素 | 描述 |
|---|---|
| c.pop_front() | 删除c中的首元素 返回void vector、string不支持 |
| c.pop_back() | 删除c中的尾元素 返回void forward_list不支持 |
| c.erase(p) | 删除迭代器p指向的元素 返回一个指向删除位置之后元素的迭代器 forward_list不支持 |
| c.erase(b,e) | 删除[b,e)内的元素 返回一个指向删除位置之后元素的迭代器 forward_list不支持 |
| c.clear() | 删除c中的所有元素 返回void |
4. forward_list特有操作
| forward_list特有操作 | 描述 |
|---|---|
| lst.before_begin() | 返回指向首前元素的迭代器iterator |
| lst.cbefore_begin() | 返回指向首前元素的迭代器const_iterator |
| lst.emplace_after(p,args) | 在迭代器p之后插入1个由args构造的元素 返回指向插入元素的迭代器 |
| lst.insert_after(p,t) | 在迭代器p之后插入1个值为t的元素 返回指向插入元素的迭代器 |
| lst.insert_after(p,n,t) | 在迭代器p之后插入n个值为t的元素 返回指向最后一个插入元素的迭代器 |
| lst.insert_after(p,b,e) | 在迭代器p之后插入[b,e)内的元素 返回指向最后一个插入元素的迭代器 |
| lst.insert_after(p,il) | 在迭代器p之后插入初始值列表中的元素 返回指向最后一个插入元素的迭代器 |
| lst.erase_after(p) | 删除迭代器p之后的一个元素 返回一个指向删除位置之后元素的迭代器 |
| lst.erase_after(b,e) | 删除(b,e]的元素 返回一个指向删除位置之后元素的迭代器 |
5. 改变顺序容器大小（array不支持）
| 改变顺序容器大小 | 描述 |
|---|---|
| c.resize(n) | 调整c的大小为n个元素 |
| c.resize(n,t) | 调整c的大小为n个元素，若n>c.size()，将多出的元素初始化为t |
6. 容器操作可能使迭代器失效
| 容器操作 | 失效情况 |
|---|---|
| vector string |
添加元素： 1. 若重新分配内存，所有迭代器、指针和引用都失效 2. 若未重新分配内存，插入位置之后迭代器、指针和引用都失效 删除元素： 1. 指向被删元素及其后元素的迭代器、引用和指针失效 |
| deque | 添加元素： 1. 若插在首尾位置，所有迭代器失效，但引用和指针有效 2. 若插在首尾位置之外，所有迭代器、指针和引用都失效 删除元素： 1. 若删除首尾元素，尾后迭代器失效，但其余迭代器、引用和指针仍有效 2. 若删除首尾之外的元素，所有迭代器、指针和引用都失效 |
| list forward_list |
添加元素： 1. 所有迭代器、引用和指针仍有效 删除元素： 1. 指向被删元素的迭代器、指针和引用都失效 |
| array | 添加元素： 1. 不能插入 删除元素： 1. 不能删除 |
建议：
- 在vector、string和deque中添加或删除元素，必须考虑指向容器元素的迭代器、引用和指针失效的问题。在循环中，尽量使用insert或erase更新迭代器。
- 在vector、string中添加或删除元素，或者在deque首元素之外添加或删除元素总会使尾后迭代器end()失效。故此时不要保存end()返回的迭代器。
9.4 vector对象是如何增长的
1. 容器大小管理
| 容器大小管理 | 描述 |
|---|---|
| c.reverse(n) | 分配至少能容纳n个元素的内存空间 只支持vector、string |
| c.capacity() | 若不重新分配内存，c可以保存的最多元素个数 只支持vector、string |
| c.shrink_to_fit() | 将capacity()减少到size() 只支持vector、string、deque |
提示：
- c.size()输出元素个数，c.max_size()输出可保存的最大元素个数，c.resize()改变元素个数，c.reverse()输出不重新分配内存情况下可保存的元素个数。
- 只有当n>c.capacity()时，c.resize(n)和c.reserve(n)才会改变c的容量；只有当n==c.capacity()时，再添加元素才会改变c的容量。
9.5 额外的string操作
1. string的构造函数
| string的构造函数 | 描述 |
|---|---|
| string s | 默认构造函数，元素个数为空 |
| string s(n,'a') | s是由n个'a'组成的字符串 |
| string s{'a','b',...} | 将初始化列表拷贝到s |
| string s(cp) string s(cp,n) |
将cp指向的数组拷贝到s，数组必须以空字符结尾 将从cp开始的n个字符拷贝到s |
| string s1(s2) string s1(s2,pos) string s1(s2,pos,len) string s(b,e) |
将s2拷贝到s1 将s2中下标从pos开始的字符拷贝到s1 将s2中下标从pos开始的len个字符拷贝到s1 将迭代器[b,e)内的元素拷贝到s |
2. string的子串操作
| string的子串操作 | 描述 |
|---|---|
| s.substr(pos,n) | 返回一个string，包含s中从pos开始的n个字符的拷贝 |
3. string的修改操作
1. string的修改操作
| args形式 | 描述 |
|---|---|
| n,c | n个字符c |
| il | 初始值列表 |
| cp | 字符数组cp，必须以空字符结尾 |
| cp,len | 从cp开始的len个字符 |
| s | 字符串s |
| s,pos,len | 从s[pos]开始的len个字符 |
| b,e | 迭代器[b,e)内的字符 |
| string的修改操作 | 描述 |
|---|---|
| s.insert(pos,args) | 在s[pos]之前插入args指定的字符，返回一个指向s的引用 s.insert(pos,n,c) s.insert(pos,cp,len) s1.insert(pos,s2) s1.insert(pos,s2,pos,len) |
| s.insert(p,args) | 在迭代器p之前插入args指定的字符，返回指向第一插入字符的迭代器 s.insert(p,n,c) s.insert(p,il) s.insert(p,b,e) |
| s.erase(pos) s.erase(pos,n) |
删除从s[pos]开始到末尾的字符，返回一个指向s的引用 删除从s[pos]开始的n个字符，返回一个指向s的引用 |
| s.assign(args) | 用args指定的字符替换s中的字符，返回一个指向s的引用 s.assign(n,c) s.assign(il) s.assign(cp) s.assign(cp,len) s1.assign(s2) s1.assign(s2,pos,len) s.assign(b,e) |
| s.append(args) | 将args追加到s，返回一个指向s的引用 s.append(n,c) s.append(il) s.append(cp) s.append(cp,len) s1.append(s2) s1.append(s2,pos,len) s.append(b,e) |
| s.replace(pos,n,args) | 将从s[pos]开始的n个字符替换为args指定的字符，返回一个指向s的引用 s.replace(pos,n1,n2,c) s.replace(pos,n,il)——错误 s.replace(pos,n,cp) s.replace(pos,n,cp,len) s1.replace(pos,n,s2) s1.replace(pos,n,s2,pos,len) s.replace(pos,n,b,e)——错误 |
| s.replace(b,e,args) | 将[b,e)内的字符替换为args指定的字符，返回一个指向s的引用 s.replace(b,e,n,c) s.replace(b,e,il) s.replace(b,e,cp) s.replace(b,e,cp,len) s1.replace(b,e,s2) s1.replace(b,e,s2,pos,len)——错误 s.replace(b1,e1,b2,e2) |
提示：如上函数可能因不同的C++标准而不同
4. string的搜索操作
| args形式 | 描述 |
|---|---|
| c,pos | 从s[pos]开始查找c |
| cp,pos | 从s[pos]开始查找cp |
| cp,pos,n | 从s[pos]开始查找从cp开始的n个字符 |
| s,pos | 从s[pos]开始查找s |
| string的搜索操作 | 描述 |
|---|---|
| s.find(args) | 查找s中args第一次出现的位置 s.find(c,pos) s.find(cp,pos) s.find(cp,pos,n) s1.find(s2,pos) |
| s.rfind(args) | 查找s中args最后一次出现的位置 s.rfind(c,pos) s.rfind(cp,pos) s.rfind(cp,pos,n) s1.rfind(s2,pos) |
| s.find_first_of(args) | 在s中查找args中任何一个字符第一次出现的位置 s.find_first_of(c,pos) s.find_first_of(cp,pos) s.find_first_of(cp,pos,n) s1.find_first_of(s2,pos) |
| s.find_first_not_of(args) | 在s中查找第一个不在args中的字符 s.find_first_not_of(c,pos) s.find_first_not_of(cp,pos) s.find_first_not_of(cp,pos,n) s1.find_first_not_of(s2,pos) |
| s.find_last_of(args) | 在s中查找args中任何一个字符最后一次出现的位置 s.find_last_of(c,pos) s.find_last_of(cp,pos) s.find_last_of(cp,pos,n) s1.find_last_of(s2,pos) |
| s.find_last_not_of(args) | 在s中查找最后一个不在args中的字符 s.find_last_not_of(c,pos) s.find_last_not_of(cp,pos) s.find_last_not_of(cp,pos,n) s1.find_last_not_of(s2,pos) |
5. string的compare
| string的compare | 描述 |
|---|---|
| s1.compare(s2) | 比较s1和s2 |
| s1.compare(pos1,n1,s2) | 将从s1[pos1]开始的n1个字符和s2比较 |
| s1.compare(pos1,n1,s2,pos2,n2) | 将从s1[pos1]开始的n1个字符和从s2[pos2]开始的n2个字符比较 |
| s.compare(cp) | 比较s和cp |
| s.compare(pos,n,cp) | 将从s[pos]开始的n个字符和cp比较 |
| s.compare(pos1,n1,cp,n2) | 将从s[pos1]开始的n1个字符和从cp开始的n2个字符比较 |
6. string的数值转换
| string的数值转换 | 描述 |
|---|---|
| to_string(val) | val -> string val：任何算术类型 |
| stoi(s,p,b) stol(s,p,b) stoul(s,p,b) stoll(s,p,b) stoull(s,p,b) |
string -> int string -> long string -> unsigned long string -> long long string -> unsigned long long p：s的下标 b：基数（8，10，16） |
| stof(s,p) stod(s,p) stold(s,p) |
string -> float string -> double string -> long double p：s的下标 |
9.6 容器适配器
适配器：一种机制，能使某种事物的行为看起来像另一种事物一样。
容器适配器：一个容器适配器接受一种已有的容器类型，其行为看起来像另一种类型。
| 适配器支持的操作 | 描述 |
|---|---|
| size_type | 一种类型，足以保存当前类型最大对象的大小 |
| value_type | 元素类型 |
| container_type | 实现适配器的底层容器类型 |
| A a; | 创建一个名为a的空适配器 |
| A a(c); | 创建一个名为a的适配器，拷贝容器c的元素 |
| ==, !=, <, <=, >, >= | 返回底层容器的比较结果 |
| a.empty() | 若适配器为空，返回true，否则返回false |
| a.size() | 返回a的元素个数 |
| swap(a,b) a.swap(b) |
交换a和b的内容 要求：a和b是同一类型，底层容器也是同一类型 |
| 顺序容器适配器 | 要求 | 底层容器 |
|---|---|---|
| stack | push_back, pop_back, back | 默认deque 支持vector、list 不支持forward_list、array |
| queue | push_back, back, push_front, front | 默认deque 支持list 不支持forward_list、array、vector |
| priority_queue | push_back, pop_back, front,随机访问 | 默认vector 支持deque 不支持forward_list、array、list |
| stack操作（先进后出） | 描述 |
|---|---|
| s.top() | 返回栈顶元素 |
| s.push(item) | 将iterm压栈 |
| s.emplace(args) | 将args构造的元素压栈 |
| s.pop() | 删除栈顶元素 |
| queue操作（先进先出） | 描述 |
|---|---|
| q.front() | 返回queue首元素 |
| q.back() | 返回queue尾元素 |
| q.push(item) | 在queue末尾添加iterm |
| q.emplace(args) | 在queue末尾添加由args构造的元素 |
| q.pop() | 删除queue首元素 |
| priority_queue操作（优先级） | 描述 |
|---|---|
| q.top() | 返回priority_queue最高优先级的元素 |
| q.push(item) | 在priority_queue合适位置添加iterm |
| q.emplace(args) | 在priority_queue合适位置添加由args构造的元素 |
| q.pop() | 删除priority_queue最高优先级的元素 |
提示：容器适配器只能使用自己的操作，而不能使用底层容器的操作。
