第10章：优化数据结构

从“容器就是一组性能契约”开始

standard library containers 提供 value/lifetime、iterator、complexity 与 invalidation contract；它们不承诺每个 workload 上同样快。第 10 章的核心是 experimenting：保持 semantics/input/operation mix 一致，逐个比较 candidate，而不是只读复杂度表。

sequence containers 按 sequence 组织 elements；associative containers 按 key/order/hash contract 组织。选择前写出 random index、front/back/middle mutation、exact/range lookup、duplicates、stable references、ordered iteration 与 peak memory。

struct WorkloadResult {
    std::chrono::nanoseconds build;
    std::chrono::nanoseconds mutate;
    std::chrono::nanoseconds iterate;
    std::uint64_t checksum;
};
 
template <class Container, class Build, class Mutate, class Visit>
WorkloadResult runContainerScenario(Build build, Mutate mutate, Visit visit) {
    Container values;
    const auto buildTime = measure([&] { build(values); });
    const auto mutateTime = measure([&] { mutate(values); });
    std::uint64_t checksum = 0;
    const auto iterateTime = measure([&] { checksum = visit(values); });
    return {buildTime, mutateTime, iterateTime, checksum};
}

harness 还应记录 allocations/bytes/RSS、key comparisons/hash、cache misses，并验证 checksum/order/reference contract。不要让不同 candidate 执行不同业务 work。

std::vector 与 std::string

std::vector contiguous、random access、适合 iteration/sorting；std::string 也是 contiguous character sequence（另有 terminator/value contract）。append 在 capacity 足够时便宜，超出则 reallocation：取得新 storage、move/copy elements、释放旧 storage并使 references/iterators 失效。

inserting and deleting 在 middle 会移动 suffix；erase many one-by-one 可能 quadratic，应使用 erase-remove、partition/compaction 或 batch rebuild。append/read-heavy 常先 reserve；不能为极端 max 无界预留。

void removeExpired(std::vector<Job>& jobs, Clock::time_point now) {
    std::erase_if(jobs, [now](const Job& job) {
        return job.expiresAt <= now;
    });
}

一次 compaction 保留 survivors，通常比循环 find+erase 少搬移。若 order 不重要，可 swap-with-back 降移动；这改变 order，必须显式 contract。

iterating contiguous values 通常 locality 好；sorting 可用 random-access standard algorithm；lookup 若 unsorted 用 linear，sorted 用 binary/range，read-mostly 可 amortize sort。vector 并不因 middle insert O(n) 就不适合插入偶尔、遍历频繁的 workload。

std::deque

std::deque 是 segmented random-access sequence；front/back growth 通常无需搬移全部 elements。deque insertion 在 middle 仍可能移动一侧 elements，并影响 iterators/references（按标准规则核对）；不是“任意插入 O(1)”。

deque iteration 跨 blocks，通常比 vector 有更多 indirection；deque sorting 支持 random-access iterator，可用 std::sort，但 segmented layout 与 element move 影响 constants。适合 queue-like 双端增长且需要 random access 的场景；简单 FIFO 还应比较 deque adaptor 使用与 ring buffer。

std::list 与 std::forward_list

std::list doubly linked，std::forward_list singly linked。list insertion 只有在 insertion position iterator 已知时才 constant relink；search position 仍需 traversal。每 node allocation/metadata 和 pointer chasing 可能让它在 iteration-heavy workload 输给 vector。

list iteration/forward-list iteration 都是 pointer traversal；list sorting 必须用 member list::sort/forward_list::sort，它通过 relink nodes，不满足 random-access std::sort 要求。large nonmovable elements、frequent splice with known iterators 可能是 list 的真实优势。

Ordered Associative: map/multimap/set/multiset

std::map unique key/value，std::set unique key；std::multimap 与 std::multiset 允许 equivalent keys。它们提供 ordered iteration、lower/equal range 与 logarithmic search/update（典型 tree representation，但标准不强制具体节点布局）。

multi container 适合一 key 多记录且需 ordered group；若只需要 exact key→vector values，map<Key, vector<Value>> 可能更 compact，但改变 insertion/reference/erase semantics。transparent comparator 可避免临时 key。测 comparator/key copy、node allocations、range length 与 iteration。

Unordered map/multimap 与 Lookup

std::unordered_map unique key/value，std::unordered_multimap equivalent duplicate keys；unordered lookup 依 hash、bucket/probe 和 exact equality，average constant 不保证 ordered range 或 worst-case。rehash 会重建 buckets 并使 iterators 失效（reference rules另核对）。

std::unordered_multimap<Tag, ItemId> buildTagIndex(
    std::span<const Item> items) {
    std::size_t associations = 0;
    for (const Item& item : items) associations += item.tags.size();
 
    std::unordered_multimap<Tag, ItemId> index;
    index.reserve(associations);
    for (const Item& item : items) {
        for (Tag tag : item.tags) index.emplace(tag, item.id);
    }
    return index;
}

reserve 预估 associations，减少 rehash；仍要比较 alternative unordered_map<Tag, vector<ItemId>> 的 group locality/build/erase。duplicate semantics 与 order不可静默改变。

Other Data Structures（其他数据结构）

other data structures 包括 flat/sorted map、heap/priority queue、bitset、trie、ring buffer、pool/intrusive list、spatial index。它们不是“标准容器更快版”，而是表达不同 contract：bounded FIFO、prefix lookup、dense boolean set、priority top、spatial neighborhood 等。

选择 custom/domain structure 要写 invariant、capacity/growth、ownership、iterator/reference、error/worst-case，并与组合标准 primitives baseline 同语义比较。若只有小常数收益却承担大量维护，保留标准方案更优。

小结

• 标准容器优化依靠同语义 experimenting，完整比较 access/mutation/stability/representation
• vector/string 连续且易 iterate/sort，reallocation 与 middle movement 要用 reserve/batch 管理
• deque 支持两端增长和 random access，但 segmented iteration/sort 有额外 constants
• list/forward_list 的 O(1) insertion 需要已知位置，node allocation 与 pointer traversal 必须计价
• map/set 提供 ordered unique，multi 允许 duplicates；unordered 家族提供 average exact lookup但无顺序
• unordered lookup 要审计 hash/equality/load/rehash/worst-case，而非只引用 O(1)
• other structures 只有在领域 contract 明确且同语义收益覆盖维护成本时才采用