Chapter 56: STL Performance Model

STL 性能分析的主问题是：面对同一个业务操作，如何从接口复杂度继续向下追踪到内存布局、对象迁移、分配次数、迭代器有效性和 CPU 执行成本。读完本章后，读者应能判断一个容器或算法慢在哪里，区分标准承诺、常见实现形状和真实机器成本，并把“换容器”这种直觉改造成可测量的分析顺序。

本章用一个贯穿材料展开：系统持续接收订单记录，按插入顺序保存全部记录，周期性扫描未完成订单，偶尔按订单号查询并更新状态。这个材料足够小，却同时覆盖 std::vector、std::list、std::deque、std::unordered_map 和排序后查找这几类典型 STL 选择。

#include <algorithm>
#include <cstdint>
#include <list>
#include <string>
#include <unordered_map>
#include <vector>

struct Order {
    std::uint64_t id{};
    std::uint64_t user_id{};
    std::string symbol;
    double price{};
    double quantity{};
    bool done{};
};

void scan_open_orders(const std::vector<Order>& orders) {
    for (const Order& order : orders) {
        if (!order.done) {
            // 真实系统中这里会聚合、校验或发送后续请求。
        }
    }
}

从标准接口看，std::vector 在尾部插入具备摊还常数复杂度，中间插入和删除是线性复杂度；C++ 工作草案对 vector 的描述也明确了连续容器、容量管理和重分配失效规则：C++ working draft, vector。这些信息是性能分析的起点。真实工程里还要继续追踪：每次扩容移动多少个 Order，字符串成员是否触发额外分配，扫描是否连续命中缓存，done 的分布是否让分支预测稳定，保存下来的 iterator 在修改后是否仍能使用。

56.1 性能模型超出时间复杂度

时间复杂度回答“输入规模增长时操作次数如何增长”。STL 性能模型还要回答“每个操作在机器上消耗什么资源”。同样是 $O(n)$，顺序扫描 std::vector<Order> 和遍历 std::list<Order> 的成本常常相差很大，因为前者沿连续内存前进，后者每个节点都要读取下一跳指针。复杂度表达了增长阶，内存层级和对象语义决定常数项、等待时间和失效风险。

贯穿材料中的 scan_open_orders 是一个线性扫描。若订单保存在 std::vector<Order> 中，循环体访问的是连续对象。CPU 读取某个 Order 附近的 cache line 时，后续几个对象的部分字节通常已经进入缓存。若订单保存在 std::list<Order> 中，循环每前进一步都要先读节点，再读节点里的对象，再读 next 指针指向的位置。节点地址由 allocator 决定，物理邻近性弱，缓存命中率依赖分配器历史和运行时碎片。

性能模型要把 STL 操作拆成几类可观察成本。接口复杂度说明算法上界；内存布局说明访问是否连续；分配次数说明是否进入堆分配器；对象迁移说明构造、移动、拷贝和析构次数；迭代器失效说明已有位置对象是否需要重新获取；分支行为说明 CPU 是否能稳定预测控制流。把这些成本放到同一个表中，才能解释“线性扫描为什么可能快于对数树查找”“链表插入为什么可能慢于 vector 尾插”“哈希平均常数为什么在某些输入下变差”。

观察维度	典型问题	对贯穿材料的影响
复杂度	操作随订单数量如何增长	扫描所有订单是线性；按 id 哈希查找平均常数
内存布局	对象是否连续，节点是否分散	连续订单数组利于周期性扫描；链表节点增加指针跳转
分配路径	一次操作触发几次 allocate	vector 扩容集中分配；list 插入通常逐节点分配
对象迁移	元素是否被 move、copy 或 destroy	vector 扩容会迁移已有订单对象
位置有效性	iterator、reference、pointer 是否仍指向原对象	扩容会让指向 vector 元素的位置失效
分支形状	条件判断是否稳定	done 分布随机时，扫描中的分支预测成本上升

这个表的作用是把“容器快慢”改成“操作路径快慢”。std::vector 的尾插适合追加型订单流；中间插入大量订单时，需要移动插入点之后的对象。std::list 的节点级插入不移动其他元素；按 iterator 到达插入点之前，仍然要经历节点遍历和分配。std::unordered_map 适合按 id 查找；当负载因子过高、哈希分布差或 rehash 发生时，平均常数查找会暴露桶数组、链表或节点组织的成本。

复杂度也有版本和标准边界。标准规定接口语义、复杂度类别和失效规则，常见实现决定三指针 vector、分段 deque、节点 list、bucket 加节点的 unordered 容器这类形状，硬件决定 cache miss、分支预测、TLB 和分配器路径的代价。正文中的性能结论默认面向 C++11 到 C++23 中稳定存在的 STL 容器；C++26 新容器如 std::hive 和 std::inplace_vector 作为相邻扩展，不进入本章主线。

56.2 cache locality 与 cache miss

Cache locality 指程序访问的内存地址在时间或空间上有规律。时间局部性表示刚访问过的数据很快再次被访问；空间局部性表示访问某个地址后，很快访问相邻地址。cache miss 指 CPU 需要的数据没有在当前缓存层中命中，执行需要等待更慢的缓存层或主存返回数据。STL 容器的布局直接影响这两个现象。

std::vector<Order> 的核心优势来自连续存储。C++ 工作草案描述 vector 时明确提到它对非 bool 元素满足 contiguous container 要求，并且 data() 返回能表示 [data(), data() + size()) 的指针范围：C++ working draft, vector data。这意味着扫描订单时，循环从一个元素地址移动到下一个元素地址。硬件预取器更容易识别这种模式，cache line 装入后也更容易被后续迭代继续使用。

std::list<Order> 的性能边界来自节点存储。标准对 list 的章节说明给出常数时间任意位置插入和删除，同时说明它缺少快速随机访问能力：C++ working draft, list overview。常见实现形状是每个节点包含前驱指针、后继指针和元素对象。这个形状让节点重连成本稳定，却把遍历转换成指针追踪。每次 ++it 都需要从当前节点读取下一节点地址，再跳到另一片内存。节点分散时，CPU 很难提前知道下一步地址，cache miss 和 TLB miss 的概率随之上升。

贯穿材料中，周期性扫描未完成订单是主访问模式。若订单数量很大，扫描 std::vector<Order> 的每一步都接近顺序内存流。若改用 std::list<Order>，复杂度仍是 $O(n)$，但每个节点的访问可能包含独立缓存等待。此时链表的“任意位置常数插入”没有作用，因为主成本发生在遍历。容器选型要先固定主访问模式：扫描密集时优先评估连续布局；已持有稳定 iterator 且需要频繁局部插入删除时，再评估节点容器。

std::deque<Order> 处在中间位置。常见实现使用控制数组指向多个固定大小 block，整体由多片 block 组成，每个 block 内部连续。它支持随机访问和双端增长，适合从前后两端增删的队列式负载。扫描时，deque 通常比 list 更接近连续访问，但跨 block 时会多一次索引定位或指针间接访问。对贯穿材料中的“追加后扫描”负载，deque 的优势要看是否真的需要高频前端插入或弹出。

有序关联容器也受 cache locality 约束。std::map 和 std::set 常见实现为红黑树，查找复杂度是对数级。一次查找沿根到叶路径跳过多个节点；这些节点分布在堆上，内存位置不连续。若订单数量中等，并且查询键集合可以排序保存到 std::vector 中，std::lower_bound 的对数比较次数加上连续存储，可能在真实时间上超过树查找。这类结论依赖读写比例：频繁插入删除并保持有序时，树容器提供稳定更新路径；批量构建后大量查询时，排序后的连续数组常常值得测量。

Cache locality 的分析顺序可以固定为四步。先看循环是否顺序访问相邻元素；再看元素对象是否过大，是否把热字段和冷字段混在一起；接着看容器是否引入额外指针跳转；最后用测量验证 cache miss、分支和分配是否符合推断。对 Order 来说，done、id、price 这类热字段可能在扫描中被反复访问，而 symbol 的字符串缓冲属于间接内存。若扫描只关心状态和价格，把热字段放入更紧凑的结构或建立索引数组，往往比替换成链表更接近问题本身。

56.3 分配次数、拷贝次数与 move 次数

分配次数决定程序进入 allocator 和堆管理器的频率；拷贝次数和 move 次数决定元素对象状态如何迁移。STL 性能分析要把“插入一个元素”拆成分配原始存储、构造新对象、迁移旧对象、销毁旧对象和释放旧存储。std::vector、std::list 和 std::unordered_map 在这些步骤上的分布差异很大。

std::vector 的扩容是集中成本。push_back 在容量足够时，通常在尾部构造一个新元素；容量不足时，容器需要分配更大的连续存储，把已有元素迁移过去，再释放旧存储。标准对 vector::reserve 和插入的描述说明：当重分配发生时，复杂度线性，且所有指向元素的 reference、pointer、iterator 以及 past-the-end iterator 都会失效：C++ working draft, vector capacity。这说明性能成本和正确性成本在同一个扩容点出现。

下面的计数器展示“看上去同样是追加，实际 move 次数可能不同”。示例使用教学简化代码，目标是观察对象迁移次数；具体增长倍率由标准库实现决定。

#include <iostream>
#include <vector>

struct Counted {
    static inline int copies = 0;
    static inline int moves = 0;

    int value{};

    Counted(int v) : value(v) {}

    Counted(const Counted& other) : value(other.value) {
        ++copies;
    }

    Counted(Counted&& other) noexcept : value(other.value) {
        ++moves;
        other.value = 0;
    }

    Counted& operator=(const Counted& other) {
        value = other.value;
        ++copies;
        return *this;
    }

    Counted& operator=(Counted&& other) noexcept {
        value = other.value;
        other.value = 0;
        ++moves;
        return *this;
    }
};

int main() {
    std::vector<Counted> values;
    values.reserve(4);

    for (int i = 0; i != 4; ++i) {
        values.emplace_back(i);
    }

    std::cout << "copies=" << Counted::copies
              << " moves=" << Counted::moves << '\n';
}

这段代码把容量预留为 4，再插入 4 个元素。常见实现中，四次 emplace_back 可以直接在目标位置构造元素，已有元素无需迁移。若删除 reserve(4)，前几次插入可能触发多次扩容，已有元素随扩容迁移。输出数值和实现增长策略有关，但分析结论稳定：当元素类型移动成本高、数量大、追加规模可预估时，reserve 把多次扩容成本合并到一次容量决策中。

移动成本还受元素类型影响。Order 包含 std::string，移动一个字符串通常可以转移内部缓冲所有权，但短字符串优化、小字符串内联、allocator 传播和异常规范都会影响实现选择。std::vector 扩容时为了维持异常安全，常见实现会在元素 move 可能抛出且 copy 可用时选择 copy 路径。这里的性能判断同时依赖语言规则和库实现：noexcept move constructor 能让容器更有条件选择移动；缺少稳定异常承诺时，容器要保护旧状态。

std::list 的插入成本呈现另一种形状。它通常为每个新节点单独分配内存，然后在节点中构造元素，再重连前后指针。已有元素对象保持在原节点中，因此插入不会成批 move 旧元素。这个形状适合“已经持有插入位置 iterator，且需要频繁局部重排”的场景。若每次插入前都要从头查找位置，遍历和分配会成为主成本。list::splice 进一步说明节点容器的强项：标准规定被移动元素的 pointer、reference 和 iterator 继续指向同一元素，所属容器随操作发生变化，并且单元素 splice 是常数复杂度：C++ working draft, list splice。这类优势来自节点所有权转移，元素值迁移不参与主路径。

std::unordered_map<std::uint64_t, Order> 的分配成本来自 bucket 数组和节点。常见实现会为 bucket 数组分配一片指针区域，并为每个元素分配节点。插入时要计算 hash，定位 bucket，比较等价键，必要时构造节点；当负载因子超过策略阈值时，rehash 会重新组织 bucket。标准对 unordered 容器给出平均情况和最坏情况复杂度，插入在平均情况下常数、最坏情况下线性：C++ working draft, unordered set modifiers。对订单 id 查询，这个容器能降低按 id 定位成本；对周期性全量扫描，它仍然要遍历节点结构，连续性弱于 vector。

分配次数的工程判断可以落到一个问题：一次业务操作是否跨过 allocator 边界。vector::emplace_back 在容量足够时不会为容器存储分配新块；list::emplace 通常每个元素都有节点分配；unordered_map::emplace 可能有节点分配，也可能触发 bucket 重排。元素内部成员也可能继续分配，例如 std::string symbol 保存长字符串时会分配字符缓冲。性能测量若只统计容器元素数量，会漏掉成员对象的二级分配。

56.4 iterator 失效、内存碎片与分支预测

隐性成本指接口调用处看不见，却会改变性能或正确性的成本。贯穿材料里，保存订单位置、删除完成订单、按条件扫描三类操作会同时遇到 iterator 失效、内存碎片和分支预测。它们通常不会出现在复杂度表第一行，却能决定容器选择是否成立。

Iterator 失效是位置对象和容器内部存储关系被修改后产生的后果。std::vector 的 iterator 常见形状接近元素指针；扩容后元素搬到新存储，旧位置指向已经释放或不再属于该容器的地址。vector::insert 在不重分配时仍会让插入点及其后的 iterator 失效，因为这些元素被移动到了新位置；erase 会让删除点及其后的 iterator 失效。cppreference 的 std::vector 页面把这些规则汇总成表，和标准草案中的重分配规则一致：cppreference, std::vector iterator invalidation。

下面的代码体现贯穿材料中常见的错误形状：把指向 vector 元素的指针缓存起来，然后继续追加元素。

#include <vector>

struct Order {
    int id{};
    bool done{};
};

int main() {
    std::vector<Order> orders;
    orders.reserve(1);
    orders.push_back({1, false});

    Order* cached = &orders[0];
    orders.push_back({2, false});

    // cached 可能已经失效；继续解引用会进入未定义行为。
    cached->done = true;
}

这段代码的关键点在于第二次追加可能让容量从 1 扩到更大。扩容后，orders[0] 的新地址和 cached 保存的旧地址分离。稳定做法是保存索引、保存 key，或者在完成所有可能扩容的构建阶段后再获取地址。若确实要长期保存稳定位置，节点容器和句柄式索引结构值得评估；代价是遍历连续性下降、节点分配增多。

内存碎片是节点容器和频繁分配释放共同形成的成本。std::list、std::map、std::unordered_map 常见实现都使用节点，节点从 allocator 获得。长期运行的服务中，订单插入和删除交错发生，释放出来的小块内存可能分散在堆上。碎片会提高分配器查找成本，降低空间局部性，并让工作集占用更多 cache 和 TLB 条目。std::pmr、对象池和批量生命周期管理可以改变这个成本形状，但它们改变的是内存来源和释放节奏，容器接口的复杂度类别保持不变。

分支预测影响扫描和谓词算法。scan_open_orders 中的 if (!order.done) 是一个条件分支。若大部分订单都未完成，CPU 很快形成稳定预测；若完成状态随机分布，预测错误会让流水线丢弃已推测执行的指令，循环吞吐下降。这个成本和容器无关，却和数据分布相关。std::partition、分离活跃订单列表、压缩状态数组等方案的目标都是让热循环更接近稳定路径。做这些改造前，要先确认条件分支确实出现在热点路径中。

隐性成本还会相互叠加。比如为了获得稳定 iterator，把订单从 vector 换成 list，可以减少扩容失效，却增加节点分配、指针追踪和碎片风险。为了按 id 查询，把订单复制进 unordered_map，可以降低查找成本，却引入额外存储、节点分配和同步一致性问题。更稳的结构常常是双结构：vector<Order> 保存扫描主数据，unordered_map<std::uint64_t, std::size_t> 保存 id 到索引的映射。更新时先通过 map 找到索引，再访问 vector；删除时使用延迟清理或 swap-remove，并同步修正索引。这个方案把查询和扫描分开建模，代价是维护两份结构之间的不变量。

隐性成本的检查顺序是：先列出所有会跨调用保存的位置对象；再列出所有会修改容器结构的操作；接着把失效规则和保存位置逐一相交；然后追踪内存块来源、释放时机和循环分支分布。这个顺序能把“偶发崩溃”和“性能抖动”放回同一个容器状态模型中分析。

56.5 工程性能分析方法

工程性能分析要从操作路径开始，而非从容器名开始。对贯穿材料，先把业务拆成四个路径：追加订单、扫描未完成订单、按 id 查询订单、删除或归档完成订单。每条路径分别记录调用频率、元素数量、是否持有位置对象、是否跨线程、是否在延迟敏感路径上执行。容器选型随后服务这些路径。

第一步是写出最小操作模型。下面的模型描述了一个常见双结构方案：vector 保存订单主体，unordered_map 保存 id 到下标。它让扫描保持连续，让按 id 查询走哈希索引。

#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <unordered_map>
#include <vector>

struct OrderBook {
    std::vector<Order> orders;
    std::unordered_map<std::uint64_t, std::size_t> id_to_index;

    void add(Order order) {
        const std::size_t index = orders.size();
        id_to_index.emplace(order.id, index);
        orders.push_back(std::move(order));
    }

    Order& by_id(std::uint64_t id) {
        auto it = id_to_index.find(id);
        if (it == id_to_index.end()) {
            throw std::out_of_range("unknown order id");
        }
        return orders[it->second];
    }
};

这段代码的性能模型包含三个不变量。orders 的下标在 push_back 扩容后仍表示同一个逻辑位置，因为扩容移动对象但不改变元素顺序；id_to_index 保存的是索引，规避了指针随 vector 扩容失效的问题；删除订单时必须同步维护映射，否则 by_id 会返回错误元素。这个模型适合追加和扫描占主导、查询需要加速、删除可以批量处理或延迟处理的负载。

第二步是估算对象数量和迁移次数。对 orders.push_back，若预估每日最多接收 N 条订单，初始化时 orders.reserve(N) 和 id_to_index.reserve(N) 可以减少扩容和 rehash。对包含 std::string 的 Order，移动通常比拷贝更低成本，但仍要考虑字符串缓冲、短字符串优化和 allocator。若订单对象包含大块外部资源，可以改成主体数组保存轻量句柄，资源放到专门池中管理。这个判断的依据是“热循环访问哪些字段”，而非对象在语义上属于同一个业务实体。

第三步是标出失效点。orders.push_back 可能让指向元素的 pointer、reference、iterator 失效；保存下标不受扩容地址变化影响。id_to_index.emplace 可能触发 unordered 容器 rehash，保存的 unordered iterator 会失效；保存 key 重新查找更稳。若删除使用 swap_remove，被交换元素的下标会变化，映射必须更新。若删除使用 tombstone 标记，扫描要处理无效槽位，分支和数据密度会变化。失效点和性能点必须一起记录，因为它们通常来自同一个结构修改。

第四步是设计测量。测量要固定输入规模、数据分布、构建参数和编译选项。一个最小 benchmark 至少区分构建阶段和查询阶段，记录总时间、分配次数、元素 copy 和 move 次数、峰值容量、命中率和删除比例。单次 wall clock 时间容易被噪声影响；多轮运行、预热、关闭调试迭代器、使用 release 编译和固定随机种子能让结果更可解释。工具层面可以使用平台 profiler、allocator 统计、硬件性能计数器或专门 benchmark 框架；工具输出回答“现象在哪里”，正文中的模型负责解释“为什么在那里”。

第五步是形成可复用判断顺序。对任意 STL 性能问题，先问主路径是扫描、查找、插入、删除还是排序；再问元素对象大不大、移动是否便宜、是否会分配；接着问容器内部布局是否适配访问模式；随后问 iterator、reference、pointer 是否跨修改保存；最后用测量确认 cache、分配、分支和迁移的实际占比。这个顺序比直接比较 vector、list、map、unordered_map 更稳定，因为它把结论绑定到负载。

把这个顺序应用回贯穿材料，可以得到一个具体判断。若订单系统主要是追加和周期性扫描，std::vector<Order> 是主体存储的优先候选；若按 id 查询频繁，用 std::unordered_map<id, index> 辅助；若删除频繁且顺序可以改变，使用 swap-remove 并维护索引；若必须保持插入顺序且删除频繁，使用 tombstone 加周期性压缩；若长期保存稳定地址是硬约束，再评估节点容器、对象池或句柄表。每个选择都对应一种成本转移：连续性、稳定性、分配次数、更新不变量和测量证据之间没有免费组合。

性能模型最终服务源码阅读。看到 reserve、shrink_to_fit、splice、rehash、load_factor、erase、lower_bound 这些接口时，要同时追踪标准语义、常见实现形状和负载证据。复杂度给出边界，源码形状给出路径，测量给出权重。三者对齐时，性能结论才可以迁移到另一个项目。

最小自检任务

阅读下面的场景，并判断主体容器和辅助索引如何选择。

场景：一个服务维护 500 万条订单。每秒追加新订单，后台每 100 毫秒扫描全部未完成订单，前台按订单 id 查询单条订单。完成订单先标记为 done，每分钟批量清理一次。业务代码会把订单 id 保存到任务队列中，队列消费者稍后再查询订单；代码不会跨容器修改保存 vector iterator 或元素指针。

问题：在 std::vector<Order>、std::list<Order>、std::unordered_map<std::uint64_t, Order>、std::vector<Order> + std::unordered_map<std::uint64_t, std::size_t> 四种方案中，哪个更适合作为初始设计？说明你的判断顺序，并指出一个需要测量验证的风险。

答案要点

更适合作为初始设计的是 std::vector<Order> + std::unordered_map<std::uint64_t, std::size_t>。判断顺序先看主路径：后台高频全量扫描要求主体存储具备连续访问优势，因此 vector 适合作为订单主体；前台按 id 查询要求快速定位，因此用 unordered 索引保存 id 到下标的映射。接着看位置有效性：业务队列保存订单 id，不保存 vector iterator 或元素指针，vector 扩容不会让保存的 id 失效；映射保存下标，扩容后元素顺序保持，下标仍可定位同一逻辑元素。然后看删除策略：完成订单先打标，每分钟批量清理，适合在清理阶段统一压缩 vector 并重建或修正索引。最后看成本转移：该方案增加了一份哈希索引和维护不变量的成本，但保留了扫描路径的连续性。

需要测量验证的风险包括：500 万个 Order 的对象大小是否让扫描工作集过大，done 分布是否造成明显分支预测成本，std::string symbol 是否让热循环反复触达冷数据，批量清理时压缩和重建索引是否造成周期性延迟尖峰。若测量显示扫描主要受冷字段影响，可以拆分热字段数组或建立活跃订单数组；若清理尖峰超出延迟预算，可以分批压缩或使用 tombstone 加后台重整。

本章知识点总结

• 主路径优先：性能分析先固定扫描、查找、插入、删除或排序这类主路径，再评价容器接口。
• 复杂度边界：时间复杂度说明增长阶，真实耗时还依赖缓存、分配、移动、失效和分支。
• 连续存储：std::vector 的连续布局适合顺序扫描、批量处理和排序后查找。
• 节点成本：节点容器提供稳定节点和局部重连能力，同时引入指针跳转、逐节点分配和碎片风险。
• 扩容成本：vector 扩容会分配新存储、迁移已有元素，并让指向元素的位置对象失效。
• 预留容量：reserve 在规模可预估时能减少扩容次数，并把迁移成本前置到容量决策。
• 移动语义：元素 move 是否廉价取决于成员对象、allocator 和异常承诺，判断时要查看对象状态转移和异常边界。
• 哈希索引：unordered_map 适合按 key 定位，但节点布局、负载因子和 rehash 会改变扫描和迭代成本。
• 失效规则：iterator、reference、pointer 的有效性必须和所有结构修改操作逐一相交检查。
• 碎片来源：频繁节点分配和释放会降低局部性，并可能增加 allocator 和 TLB 成本。
• 分支成本：热循环中的条件分布会影响分支预测，数据分布是性能模型的一部分。
• 双结构设计：主体连续存储加辅助索引可以同时服务扫描和查询，但必须维护结构间不变量。
• 测量证据：benchmark 应区分构建、查询、扫描和清理阶段，并记录分配、迁移、容量和命中率。
• 源码阅读：看到 reserve、splice、rehash、erase 等接口时，应同时追踪标准语义、实现形状和负载证据。