第9.1章: 序列容器概览

English

概述

本节介绍 fast_io_dsal 中提供的所有序列容器。序列容器按顺序存放元素——第一个加入的元素位于位置 0，第二个位于位置 1，依此类推。我们会逐一介绍每种容器，解释数据局部性，并给出选择合适容器的经验法则。

1. 容器目录

下面的表格列出了全部容器。IPA 一列给出每个名字的国际音标读音。

拥有所有权的容器

容器 IPA 内存布局 说明
::fast_io::array<T, N> /əˈreɪ/ 连续（栈上或静态存储区） 大小固定，元素个数在编译期已知。
::fast_io::vector<T> /ˈvɛktər/ 连续（堆上） 默认容器。大小动态，存储连续。
::fast_io::string /strɪŋ/ 连续（堆上） 动态字符序列。是 basic_string<char> 的别名。
::fast_io::deque<T> /dɛk/ 分块（堆上） 双端队列。两端插入/删除都很快，并支持随机访问。
::fast_io::list<T> /lɪst/ 双向链表结点（堆上） 双向链表。一旦定位到位置，任意处的插入/删除都是 Θ(1)。
::fast_io::forward_list<T> /ˈfɔɹwəɹd lɪst/ 单向链表结点（堆上） 单向链表。每元素额外开销最小，但只能向前遍历。
::fast_io::bitvec /bɪt vɛk/ 紧凑位存储（堆上） 动态位向量。它存放的是单个位，而不是 bool 值。

视图类型（不拥有所有权）

视图类型 IPA 说明
::fast_io::span<T> /spæn/ 对连续内存的非拥有视图，大小动态。
::fast_io::index_span<T, N> /ˈɪndɛks spæn/ 非拥有视图，大小在编译期固定为 N。
::fast_io::string_view /strɪŋ vjuː/ 对字符序列的非拥有视图。
::fast_io::cstring_view /ˈsiː strɪŋ vjuː/ 带空字符结尾保证的非拥有视图。

2. 数据局部性与性能

容器在内存中存放元素的方式对性能有深远影响。现代 CPU 严重依赖缓存（L1、L2、L3）。当元素连续存放时，访问一个元素通常会把它的邻居一起带进缓存，后续访问几乎不花代价。

布局 容器 缓存行为 遍历速度
连续 array、vector、string 极佳 — 硬件预取器可以完美工作 最快
分块 deque 块内良好，块边界处偶有缓存未命中 对大型容器而言接近连续
链表结点 list、forward_list 差 — 每个结点都是一次独立的堆分配 最慢 — 指针追逐
紧凑位 bitvec 极佳 — 比 vector<bool> 紧凑 64× 快，但访问单个位需要掩码

对大多数工作负载来说，连续存储胜出。CPU 缓存行通常是 64 字节。一个 vector<::std::size_t> 每缓存行能带来 16 个元素，而 list<::std::size_t> 每缓存行只带来 1 个元素（还要在指针上浪费内存）。因此，尽管链表提供 Θ(1) 插入，遍历的常数因子却可能差 10–50×。

3. 如何选择容器

以下是选择容器时的经验法则：

能不用容器就不用。如果可以用 I/O 操作完成任务（例如打印 “Hello, World!”），那就这么做。I/O 提供了一种无需动态分配就能处理无界数据的抽象。I/O 缓冲区往往比栈分配和堆分配都更高效。
  1. 除非有理由使用别的容器，就用 ::fast_io::vector。它的缓存局部性最好，几乎在所有操作上都是最快的。
  2. 如果程序包含大量小元素，而空间开销很重要，就不要用 list 或 forward_list。链表中的每个结点至少要带一个指针（64 位系统上是 8 字节）的额外开销。
  3. 如果程序需要随机访问元素，就用 vector 或 deque。两者都提供 Θ(1) 的 operator[]，链表则没有。
  4. 如果程序需要在容器中间插入或删除元素，就用 list 或 forward_list。一旦迭代器定位好，插入与删除都是 Θ(1)。
  5. 如果程序需要在前端和后端插入或删除元素，但不需要在中间操作，就用 deque。vector 只能在尾部高效增长。
  6. 如果程序只需要在读取输入时向中间插入元素，之后又需要随机访问：
    • 首先想一想，你是否真的需要中间插入。通常更简单的做法是先往 vector 里追加，之后再调用 ::std::ranges::sort。
    • 如果确实必须往中间插入，可以考虑在输入阶段使用 list，输入完成后再把链表复制到 vector 中。
最佳实践：如果你不确定该用哪个容器，就把代码写成只使用 vector 和 list 共有的操作：使用迭代器（或 _index 系列操作），并且不要假定存在随机访问。这样在需要时就能轻松切换到 vector 或 list。

如果程序既需要随机访问又需要在中间插入或删除元素呢？答案取决于链表访问元素的相对代价与 vector 或 deque 中插入/删除的代价之间的对比。一般说来，应用的主要操作（是访问更多还是插入/删除更多）会决定选择。在这种情况下，通常需要针对两种容器都做性能测试。

要点

← 第9章: 序列容器 ↑ 主页 第9.2章: 通用操作 →