第9.9章: deque

概述

::fast_io::deque<T>（读作“deck”）能在两端高效地插入与删除，同时仍支持用 operator[] 进行随机访问。

1. 内部结构

vector 把所有元素存放在一个连续的块里，deque 则不同，它采用块映射设计：

• 元素存放在大小固定的块（chunk）中。
• 一个居中的控制器维护着一张指向这些块的指针数组。
• 每个块容纳 block_size 个元素（由实现定义，通常大到足以填满一个缓存行或一个页）。

// Conceptual layout of a deque:
//
// Controller: [ptr_to_block0] [ptr_to_block1] [ptr_to_block2] ...
//                    |               |               |
//               Block 0:        Block 1:        Block 2:
//             [e0][e1]..[eN]  [e0][e1]..[eN]  [e0][e1]..[eN]

当 deque 需要在前端增长时，它分配一个新块并把指针加到控制器前端，不需要搬移任何已有元素，后端同理。这正是它相对 vector 的关键优势——vector 在前端增长时必须复制所有元素。

2. deque 特有的容量

由于 deque 在两端增长，它的每一端都有独立的容量：

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

int main() {
    using namespace ::fast_io::iomnp;

    ::fast_io::deque<::std::size_t> dq;

    // Reserve at each end independently
    dq.reserve_back(1000zu);
    dq.reserve_front(500zu);

    println("Front capacity: ", dq.front_capacity());
    println("Back capacity: ", dq.back_capacity());

    // Segment introspection
    println("Block size: ", decltype(dq)::block_size);
    println("Segments: ", dq.segments_count());
}

3. 什么时候 deque 优于 vector？

为什么 deque 的分配更高效

vector 的增长方式是把整块缓冲区翻倍：容量耗尽时，它分配一块 2× 当前容量的新缓冲区，并复制每一个已有元素。对 1000 万个元素来说，最后一次重新分配要搬移约 500 万个元素，前一次约 250 万个，依此类推。所有重新分配中元素搬移的总次数大致等于最终的大小。

deque 的增长方式是分配一个新块（通常相当于 4 KB 的元素），并往控制器里加一个指针。永远不会搬移任何已有元素。每个块都是一次独立的小分配。这意味着：

• 没有复制代价 — 每次插入的工作量就是一次构造函数调用，与已有多少元素无关。
• 没有大块分配 — 分配器永远不需要找到一块足以容纳整个数据集的连续区域。许多小分配比一次巨大分配更容易满足。
• 不会超量占用内存 — vector 在刚重新分配之后可能占用多达所需内存的 2×（size = N，capacity = 2N）。deque 只分配它真正会用到的块。

这种效果在基准测试中看得见。压入 1000 万个 ::std::size_t 元素：

普通 deque（0.095 s）已经比不带 reserve 的 vector（0.187 s）快 2×，因为它没有复制代价。而预分配的 deque（0.080 s）甚至比带 reserve 的 vector（0.095 s）更快，因为 deque 避免了 reserve 所要求的那一次大分配。

deque 的缺点

尽管在分配上有优势，deque 有两个显著缺点，使得 vector 在很多场合仍是更好的选择：

1. 不连续

deque 的元素散布在多个堆分配的块上，没有单一连续的缓冲区可以交给 C API、memcpy、SIMD intrinsic，或者任何期望“T* 加元素个数”的库。正因如此，deque 上没有 data() 方法。

如果你需要把元素交给要求连续内存的 API，就必须把它们复制到临时的 vector 里，或者使用 segments API 一块一块地处理。

2. 最小占用很大

每个 deque 至少分配一个完整的块，即使它只有一个元素。块大小通常是 4 KB（4096 字节，选择这个值是为了对齐页或缓存行边界）。所以一个只装有一个 ::std::size_t（8 字节）的 deque，仍然要耗用约 4 KB 内存外加控制器开销。

这使得 deque 成为嵌套容器中内层维度的糟糕选择：

// BAD: 1000 inner deques, each allocating ~4 KB even if nearly empty
::fast_io::vector<::fast_io::deque<::std::size_t>> matrix(1000zu);
// Minimum memory: 1000 * 4 KB = 4 MB, even if each deque has only 1 element

// GOOD: 1000 inner vectors, each allocating only what they need
::fast_io::vector<::fast_io::vector<::std::size_t>> matrix(1000zu);
// Minimum memory: 1000 * ~24 bytes (vector overhead) = ~24 KB

作为经验法则：

• 当你需要两端快速增长时，把 deque 用作顶层容器。
• 在嵌套容器中把 vector 用作内层维度（vector<vector<T>>、vector<array<T, N>> 等），以避免每个实例的块开销。

4. 用 segments API 快速遍历

常规的 deque 迭代器在每次元素自增时都要检查块边界：

// What deque_iterator::operator++ does internally:
if (++curr_ptr == block_end) [[unlikely]]
    wrap_to_next_block(); // branch on every element

这个分支通常能被正确预测（对 8 字节类型，每块约 500 个元素），但它妨碍编译器自动向量化循环，并带来延迟。segments API 让你按块遍历，从而彻底消除逐元素检查。

segment 方法

返回的 span 带有 .data() 和 .size()，因此内层循环会编译成一次普通的指针遍历 — 可自动向量化、可用 memcpy、热路径上无分支。只有第一个和最后一个 segment 可能是不满的，中间的 segment 总是恰好包含 block_size 个元素。

只读遍历

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

int main() {
    ::fast_io::deque<::std::size_t> dq;
    for (::std::size_t i{}; i < 10000zu; ++i)
        dq.push_back(i);

    ::std::size_t sum{};

    // Segment iteration: no per-element bounds check
    for (::std::size_t i{}, segs{dq.segments_count()}; i != segs; ++i)
    {
        for (auto const e : dq.const_nth_segment(i))
        {
            sum += e;
        }
    }

    ::fast_io::io::println("sum = ", sum);
}

可变遍历

// Write through segments
for (::std::size_t i{}, segs{dq.segments_count()}; i != segs; ++i)
{
    for (auto& e : dq.nth_segment(i))
    {
        e *= 2zu;
    }
}

为 memcpy / SIMD 直接取指针

// Get raw pointer + count from each segment
for (::std::size_t i{}, segs{dq.segments_count()}; i != segs; ++i)
{
    auto seg = dq.const_nth_segment(i);
    ::std::size_t const* data = seg.data();
    ::std::size_t count = seg.size();
    // pass (data, count) to memcpy, SIMD intrinsics, etc.
}

什么时候用 segments 而不是常规迭代

5. 迭代器失效与指针/引用稳定性的区别

deque 的块映射设计带来了一个与 vector 不同的独特失效性质：

为什么迭代器总会失效：deque 迭代器内部持有指向控制器（块指针数组）的指针。当控制器增长时 — 任何前端或后端插入都可能引发 — 旧的控制器被释放、新的被分配。所有指向旧控制器的迭代器因此悬空，尽管元素本身并没有移动。

为什么指针与引用在尾部插入后仍然有效：当 deque 在某一端增长时，它要么填满现有端块中的剩余容量，要么分配一个全新的块。不会复制或搬移任何已有元素。因此插入之前取得的指针或引用仍然指向同一处内存。

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

int main() {
    ::fast_io::deque<::std::size_t> dq{10zu, 20zu, 30zu};

    ::std::size_t& ref = dq[1zu]; // reference to element 20

    // Iterator is invalidated, but the reference survives:
    dq.push_back(40zu);
    // ref is still valid and refers to 20

    dq.push_front(5zu);
    // ref is STILL valid — elements are never moved on end insertions

    ::fast_io::io::println("ref = ", ref); // 20
}

与 vector 的对比：vector 把所有元素存放在一个连续数组里。当它增长超过容量时，会分配一个新数组并搬移每一个元素，这会使所有迭代器、指针和引用失效 — 不存在部分稳定。

要点

• deque 使用由大小固定的块组成的映射，而不是一个连续数组。
• 它在前端和后端的插入都是摊还 Θ(1)，且不复制元素。
• deque 不连续 — 没有 data()，也不能直接用于 C API 或 SIMD。
• 每个 deque 至少分配一个约 4 KB 的块，即使只有一个元素。在嵌套容器中不要把它用作内层维度。
• reserve_front() 与 reserve_back() 分别控制两端的容量。
• deque 支持随机访问，但缓存局部性比 vector 略差。
• 默认优先用 vector；需要前端插入时用 deque。
• 对 deque 做无分支、可自动向量化的遍历时，使用 segments API（segments_count()、nth_segment()、const_nth_segment()）。
• deque 的迭代器在插入时总会失效，但指向已有元素的指针和引用在 push_front() / push_back() 之后仍然有效 — 这与 vector 不同，vector 在重新分配时会使一切失效。