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

【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 获取迭代器： (c)begin/(c)end ； (c)rbegin/(c)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 可以在运行期生成无限长或有限长的数值序列

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 可以在运行期生成无限长或有限长的数值序列