第9.8章: vector

English

概述

要写出高效的代码，理解 ::fast_io::vector 如何管理容量是必不可少的。vector 维护两个量：

1. 增长是如何发生的

在内部，vector 就是指向单块连续堆分配的三个指针： 


// Conceptual layout of a vector with size=3, capacity=8:
//
//   begin_ptr     curr_ptr                end_ptr
//       |            |                      |
//       v            v                      v
//   +----+----+----+----+----+----+----+----+
//   | e0 | e1 | e2 |    |    |    |    |    |
//   +----+----+----+----+----+----+----+----+
//   ^                       ^
//   |_______ size=3 ________|
//   |___________ capacity=8 _________________|

热路径：还有空闲容量时

当你调用 push_back() 或 emplace_back() 时，vector 先检查 curr_ptr != end_ptr。若还有空间，就在 curr_ptr 处就地构造元素并推进指针。这就是热路径 — 一次构造函数调用加一次指针自增，没有任何分配。

冷路径：容量耗尽时

当 curr_ptr == end_ptr 时，vector 必须重新分配。步骤如下：

  1. 计算新容量：容量翻倍（2×）。若当前容量为 0，则增长到 1 个元素。若翻倍会使 size_t 溢出，则取到可能的最大容量。
  2. 按新容量分配一块新缓冲区。
  3. 把元素从旧缓冲区搬移到新缓冲区。对可平凡复制的类型（如整数、浮点数、POD 结构体），这就是一次 memcpy；对非平凡类型，则逐个在新缓冲区中移动构造，再在旧缓冲区中析构。
  4. 释放旧缓冲区。
  5. 把三个指针更新为指向新缓冲区。 

// Growth sequence for a vector<size_t>:
//
// capacity: 0 → 1 → 2 → 4 → 8 → 16 → 32 → ...
// size:     0   1   2   3   4    5    6    ...
//
// Each arrow that crosses a power-of-2 boundary triggers reallocation.

为什么翻倍能带来摊还 Θ(1)

考虑从空 vector 开始进行 n 次插入的总工作量。重新分配发生在大小为 1、2、4、8、…，一直到小于 n 的最大 2 的幂。元素搬移的总次数是：

1 + 2 + 4 + 8 + … + n/2 < n

所以所有重新分配的总代价与 n 成正比，于是每次插入是摊还 Θ(1)。绝大多数插入走热路径，只有少数会触发昂贵的重新分配。

可平凡复制与不可平凡的类型

类型类别 重新分配时元素的搬移方式 例子
可平凡复制或可平凡搬移 批量 memcpy — 一次调用复制整个缓冲区 ::std::size_t、double、POD 结构体
非平凡（有自定义移动构造函数或析构函数） 逐元素移动构造 + 析构 ::fast_io::string、::fast_io::vector

这个区别对性能有影响：100 万个元素的 vector<::std::size_t> 重新分配时只做一次 8 MB 的 memcpy，硬件对它有很深的优化。而 100 万个元素的 vector<::fast_io::string> 必须逐个移动构造并析构每个字符串。

2. reserve()

reserve(n) 保证 vector 至少有容纳 n 个元素的容量，但不改变大小。若当前容量已经 ≥ n，它什么都不做。

当你事先知道需要多少元素时，用 reserve() 来避免反复重新分配： 


#include <fast_io_dsal/vector.h>
#include <fast_io.h>

int main() {
    ::fast_io::vector<::std::size_t> v;

    // Without reserve: push_back triggers reallocations at 1, 2, 4, 8, 16, ...
    // With reserve: zero reallocations during the loop
    v.reserve(1000zu);
    for (::std::size_t i{}; i < 1000zu; ++i) {
        v.push_back(i);
    }
    // size() == 1000, capacity() >= 1000
}

3. push_back_unchecked()

当你已用 reserve() 预分配好容量时，可以使用 push_back_unchecked() 跳过每次插入的容量检查。这样就省掉了热路径上的一个分支： 


::fast_io::vector<::std::size_t> v;
v.reserve(100zu);

// Normal push_back checks: "is curr_ptr == end_ptr?" every iteration.
// push_back_unchecked skips that check — UB if you exceed capacity.
for (::std::size_t i{}; i < 100zu; ++i) {
    v.push_back_unchecked(i);
}
// size() == 100, capacity() >= 100

当元素个数事先已知时，reserve() + push_back_unchecked() 是填充 vector 最快的方式。

4. shrink_to_fit()

shrink_to_fit() 请求 vector 把容量缩减到与大小相符。若当前容量大于大小，这会触发一次重新分配：把元素复制到更紧凑的缓冲区，并释放旧的缓冲区。 


::fast_io::vector<::std::size_t> v;
v.reserve(10000zu);
for (::std::size_t i{}; i < 5zu; ++i) v.push_back(i);
// size() == 5, capacity() >= 10000

v.shrink_to_fit();
// size() == 5, capacity() == 5

5. clear() 与 clear_destroy() 的区别

这两个操作的区别在于已分配的内存会被如何处理：

操作 元素 内存 适用场景
clear() 被析构 保留（容量不变） 你打算很快复用这个 vector
clear_destroy() 被析构 被释放（容量变为 0） 你想把内存还给分配器 

::fast_io::vector<::std::size_t> v{1zu, 2zu, 3zu};
v.reserve(1000zu);

v.clear();
// size() == 0, capacity() >= 1000 (memory still held)

v.clear_destroy();
// size() == 0, capacity() == 0 (memory freed)

要点

← 第9.7章: list ↑ 主页 第9.9章: deque →