第 13 章 卷三 容器与数据结构：导言

本章导读

卷三装的是"怎么放数据"。十一个容器分成五组：序列（数组、缓冲、栈族、链表）管元素的排布与进出；映射与集合（map、intmap、set）管"按键定位"与"归属判定"；有序结构（AVL 两形态）管"键序与范围"；队列（SPSC/MPSC/MMPC）管"跨线程传递"；池（固定池、变长池）管"对象的批量取放"。第 14 章到第 22 章逐个精讲，第 23 章收官把它们组成一张选型地图。

四条家族约定（先记约定，再学容器）

卷三的全部容器共享四条约定，第 14 章首次立约、后续各章直接引用。句柄在栈、内存在堆：Init 拿栈上句柄开张、容器自管缓冲、Unit 精确归还；要容器对象本身上堆用 Create/Destroy。读走字段、写走函数：Count、Size、Data 等只读状态是公开字段，热路径零开销；会失败的操作走函数返回值并配合第 4 章错误槽。失败无副作用：编辑失败容器保持原状，清理代码永远安全。迭代三段式：Begin/Next/End 的顺序快照迭代，迭代期指针不出迭代期、迭代中禁增删——map、set、AVL、池的遍历全部同构。四条约定让"学一个容器"的成本随容器数量递减：第 14 章最贵，之后每一章都在复用。

一条主线：归属与顺序

比四条约定更深的一条主线是归属与顺序。归属问"这块数据归谁管"——值语义（数组/映射的槽）让容器全权代管，侵入式（链表/AVL 的节点）让你保留对象、容器只管链接，拥有式（容器式 AVL）把生死交给树，池管取放、arena 管同回收——第 5 章的所有权语言在卷三落地为具体的容器选择。顺序问"我按什么次序访问"——下标、插入序、键序、LIFO/FIFO、优先序，每种容器承诺一种（且只有一种）顺序：数组的下标、映射的插入序、AVL 的键序、栈的后进先出、队列的先进先出。选容器时把这两个问题回答了，答案基本就出来了——第 23 章的选型地图正是把这两问展开成决策路径。

阅读建议

三类读者三种走法。按序通读：从第 14 章到第 23 章，约定在前面立、地图在最后收，适合第一次系统学习。按需查阅：直接跳你项目要用的那个容器，读完本章的四条约定与主线两问再进具体章——约定是各章的前置。复习串联：直接读第 23 章选型地图，从地图回跳各章的契约区——适合面试准备或技术评审前的快速回顾。无论哪种走法，每章的两个完整示例都值得亲手跑一遍：容器是"手感"知识，跑过的才真正属于你。

一个提醒：本卷不解决并发

除队列外，本卷容器全部不是线程安全的——这不是缺陷，是分层（各章契约区都有这条）。需要跨线程共享容器时，答案在卷六：读多写少上读写锁、跨线程传递用队列、高并发用分片。现在就立下这个预期，可以避免"到卷六才发现选型要返工"的弯路——带着单线程假设设计的容器层，是并发重构时最贵的部分。

本卷知识地图

学习检验（离开本卷前自测）

合上书回答六个问题，每个都对应一组容器：一组同型记录要按下标频繁访问并整体排序，用哪个？字节流要"分段攒、整块取"，用哪个？对象生命周期整齐、想一起回收，第 7 章的答案和本卷的答案分别是什么、为什么不冲突？按键定位时"插入序导出"与"键序导出"分别选哪个映射？需要"键序 + 范围查询"时哈希为什么无能为力、AVL 的两个形态按什么选？十万条连接对象的取放为什么交给池而不交给堆？六问全部顺畅作答，卷三才算真正读完——答不顺的，回对应章节的契约区重读一遍——六个问题分别指向：数组、缓冲、arena 与池的分工、两套映射、AVL 两形态、池化对象。

性能观：常数之争

容器性能之争大半是常数之争，本卷反复出现的三个常数因子值得现在建立直觉。局部性：连续存储（数组、缓冲、映射的槽）对预取器友好，链式结构（链表、树）每次跳转都是一次缓存未命中的机会——百万级遍历里这常常比算法复杂度更响。分配次数：值内联（数组、映射）与池化把分配从"每对象"降到"每容器/每页"；侵入式干脆归零——第 6 章统计的 backing 曲线是三种策略的可观测分界。同步成本：无锁队列按拓扑计价，SPSC 最便宜——"拓扑确定就选专用"是本卷唯一涉及并发时就教掉的纪律。三个因子在选型时互相牵制：链表的 O(1) 插删在缓存局部性面前经常赢不了数组的搬移——第 23 章的地图会把这类"反直觉"用决策规则固定下来，而你现在要带走的直觉是：先量级、再常数、最后才是聪明。

与前后卷的衔接

向前衔接：卷一的内存体系（第 5 章拥有式、第 7 章 arena）是容器归属语言的底座，第 6 章统计是容器性能验证的工具。向后衔接：卷四的解析器用栈（帧栈）与映射（词频）组装；卷六的并发体系以队列与池为物理载体；卷七网络引擎的连接表是"数组 + 映射 + slot_map + 池"的完全体。可以说卷三的每一个容器都会在后面某一卷担任主角——现在把它们认清，后面遇到时只需要关注"业务"那一个新变量。