【C++基础】第9章：序列与关联容器

1 容器概述

1.1 容器：一种特殊的类型，其对象可以放置其它类型的对象（元素）

1.1.1 需要支持的操作：对象的添加、删除、索引、遍历

1.1.2 有多种算法可以实现容器，每种方法各有利弊

1.2 容器分类

1.2.1 序列容器：其中的对象有序排列，使用整数值进行索引

1.2.2 关联容器：其中的对象顺序并不重要，使用键进行索引

1.2.3 适配器：调整原有容器的行为，使得其对外展现出新的类型、接口或返回新的元素

1.2.4 生成器：构造元素序列

1.3 迭代器：用于指定容器中的一段区间，以执行遍历、删除等操作

1.3.1 获取迭代器： ©begin/©end ； ©rbegin/©rend

1.3.2 迭代器分类：分成 5 类（ category ），不同的类别支持的操作集合不同

2 序列容器

2.1 C++ 标准库中提供了多种序列容器模板

2.1.1 array ：元素个数固定的序列容器

2.1.2 vector ：元素连续存储的序列容器

2.1.3 forward_list / list ：基于链表 / 双向链表的容器

2.1.4 deque ： vector 与 list 的折衷

2.1.5 basic_string ：提供了对字符串专门的支持

2.2 需要使用元素类型来实例化容器模板，从而构造可以保存具体类型的容器

2.3 不同的容器所提供的接口大致相同，但根据容器性质的差异，其内部实现与复杂度不同

2.4 对于复杂度过高的操作，提供相对较难使用的接口或者不提供相应的接口

2.5 array 容器模板：具有固定长度的容器，其内部维护了一个内建数组，与内建数组相比提供了复制操作

2.6 提供的接口

2.6.1 构造

2.6.2 成员类型： value_type 等

2.6.3 元素访问： [] ， at ， front ， back ， data

2.6.4 容量相关（平凡实现）： empty ， size ， max_size

2.6.5 填充与交换： fill ， swap

2.6.6 比较操作： <=>

2.6.7 迭代器

2.7 vector 容器模板：元素可变

2.8 提供的接口

2.8.1 与 array 很类似，但有其特殊性

2.8.2 容量相关接口： capacity / reserve / shrink_to_fit

2.8.3 附加元素接口： push_back / emplace_back

2.8.4 元素插入接口： insert / emplace

2.8.5 元素删除接口： pop_back / erase / clear

2.9 注意

2.9.1 vector 不提供 push_front / pop_front ，可以使用 insert / erase 模拟，但效率不高

2.9.2 swap 效率较高

2.9.3 写操作可能会导致迭代器失效

2.10 list 容器模板：双向链表

2.11 与 vector 相比， list

2.11.1 插入、删除成本较低，但随机访问成本较高

2.11.2 提供了 pop_front / splice 等接口

2.11.3 写操作通常不会改变迭代器的有效性

2.12 forward_list 容器模板：单向链表

2.12.1 目标：一个成本较低的线性表实现

2.12.2 其迭代器只支持递增操作，因此无 rbegin/rend

2.12.3 不支持 size

2.12.4 不支持 pop_back / push_back

2.12.5 XXX_after 操作

2.13 deque容器模板： vector 与 list 的折衷

2.13.1 push_back / push_front 速度较快

2.13.2 在序列中间插入、删除速度较慢

2.14 basic_string 容器模板：实现了字符串相关的接口

2.14.1 使用 char 实例化出 std::string

2.14.2 提供了如 find ， substr 等字符串特有的接口

2.14.3 提供了数值与字符串转换的接口

2.14.4 针对短字符串的优化（short string optimization: SSO ）

3 关联容器

3.1 使用键进行索引

3.1.1 set / map / multiset / multimap

3.1.2 unordered_set / unordered_map / unordered_multiset / unordered_multimap

3.2 set / map / multiset / multimap 底层使用红黑树实现

3.3 unordered_xxx 底层使用 hash 表实现

3.4 set

3.4.1 通常来说，元素需要支持使用 < 比较大小

3.4.2 或者采用自定义的比较函数来引入大小关系

3.4.3 插入元素： insert / emplace / emplace_hint

3.4.4 删除元素： erase

3.4.5 访问元素： find / contains

3.4.6 修改元素： extract

3.5 注意： set 迭代器所指向的对象是 const 的，不能通过其修改元素

3.6 map

3.6.1 树中的每个结点是一个 std::pair

3.6.2 键 (pair.first) 需要支持使用 < 比较大小

3.6.3 或者采用自定义的比较函数来引入大小关系

3.6.4 访问元素： find / contains / [] / at

3.6.5 注意

3.6.5.1 map 迭代器所指向的对象是 std::pair ，其键是 const 类型

3.6.5.2 [] 操作不能用于常量对象

3.7 multiset / multimap

3.7.1 与 set / map 类似，但允许重复键

3.7.2 元素访问

3.7.2.1 find 返回首个查找到的元素

3.7.2.2 count 返回元素个数

3.7.2.3 lower_bound / upper_bound / equal_range 返回查找到的区间

3.8 unordered_set / unordered_map / unordered_multiset / unordered_multimap

3.8.1 与 set / map 相比查找性能更好

3.8.2 但插入操作一些情况下会慢

3.8.3 其键需要支持两个操作

3.8.3.1 转换为 hash 值

3.8.3.2 判等

3.8.4 除 == ， != 外，不支持容器级的关系运算

3.8.4.1 但 ==, != 速度较慢

3.8.5 自定义 hash 与判等函数

4 适配器与生成器

4.1 类型适配器

4.1.1 basic_string_view （ C++17 ）

4.1.1.1 可以基于 std::string ， C 字符串，迭代器构造

4.1.1.2 提供成本较低的操作接口

4.1.1.3 不可进行写操作

4.1.2 span （ C++20 ）

4.1.2.1 可基于 C 数组、 array 等构造

4.1.2.2 可读写

4.2 接口适配器

4.2.1 stack / queue / priority_queue

4.2.2 对底层序列容器进行封装，对外展现栈、队列与优先级队列的接口

4.2.3 priority_queue 在使用时其内部包含的元素需要支持比较操作

4.3 数值适配器 (c++20) ： std::ranges::XXX_view, std::ranges::views::XXX, std::views::XXX

4.3.1 可以将一个输入区间中的值变换后输出

4.3.2 数值适配器可以组合，引入复杂的数值适配逻辑

4.4 生成器 (c++20)

4.4.1 std::ranges::itoa_view, std::ranges::views::itoa, std::views::itoa

4.4.2 可以在运行期生成无限长或有限长的数值序列