第 23 章 容器选型：从需求到容器的决策路径

本章导读

卷三的收官章不引入新容器，只做一件事：把前十章的知识压缩成可执行的选型流程。选错容器的代价在代码 review 里看不出来——它藏在"为什么这个接口越优化越慢"的季度复盘里。本章给出三条决策主线（归属、顺序、访问模式）、一张决策地图、两个用数据说话的对照实验，以及最常被问到的五个"其实你不想要 X"的反选型问题。读完本章，任何一个数据组织需求你都应该能在三十秒内说出候选容器与验证方法——这个"三十秒"不是修辞，是本章练习一的过关线。

23.1引入

一个真实场景：工单系统里"待处理工单"要支持三种操作——按优先级取出最高的、按工单号查详情、处理完归档。三个操作各自指向一个容器：优先级队列、映射、归档数组。新手答案是"找个全能容器"——不存在；老手答案是"一个问题一个视图"：数组存全部工单（权威数据），映射维护"工单号到下标"（定位视图），优先处理时线性扫描或按需排序（优先视图）。数据只有一份、视图按需搭建——这是选型的第一课：先定权威存储，再搭视图，而不是找全能容器。

第二课更隐蔽：选型要用数据裁决而不是直觉。教科书说"链表插删 O(1) 优于数组 O(n)"——但在百万级遍历、几千次插删的混合负载里，数组的缓存局部性经常让总时间反超链表一个数量级。本章的两个对照实验就是为这个"反直觉"准备的：亲手跑出你自己机器上的数字，选型依据从"听说"升级为"实测"。

23.2概念

三问定型

第一问筛掉一半候选：生命周期整齐→arena（不是容器问题）；等大对象频繁取放→池；对象要自持（多视图、栈上、池中）→侵入式或值容器装句柄；容器全权代管→值容器。第二问再筛一半：下标→数组；插入序→map/set；键序与范围→AVL；LIFO→栈族；FIFO→队列。第三问在剩余候选里按热度定胜负：遍历热选连续存储、定位热选映射、插删热看是否已握节点、跨线程只有队列。

决策地图

反选型五问（评审时的口头禅）

五个高频误区，每个都值得点名；它们也适合当评审口头禅——听到哪句就问对应的三问。"要个万能容器"——不存在，权威存储+视图才是答案（见引入）。"链表插删快"——前提是你已握节点；按下标找节点是 O(n)，局部性还差。"哈希总是最快"——整数键时 xintmap 更快，键序需求时哈希根本不回答。"先上锁保平安"——跨线程传递用队列、定位用分片，锁是卷六的最后手段不是第一反应。"池治百病"——生命周期整齐的短命对象归 arena，池管的是"频繁取放"，语义错位时两者都不对。五问的共同病根：把容器当信仰而不是工具——地图就是把信仰换成流程。

常数之争的裁决方法

复杂度给量级、常数定胜负，裁决工具只有实测——而实测的结论属于你的负载与你的机器，换一个负载配比就要重测。方法：固定数据规模（如百万元素）、固定操作配比（如 90% 遍历 + 10% 插删）、用 xrtNow（返回毫秒 xtime，第 3 章）计时、每个候选跑三遍取中位数——第 10 章 Near 的容差思想同样适用于性能数字的解读。第 6 章统计补充内存侧证据：分配次数、缓存命中率 proxy（每秒吞吐）一起看，单看时间容易误判原因。

23.3示例

对照实验一：数组 vs 链表，遍历主导时谁赢

/* race_list.c —— 百万节点遍历 + 千次插删的对照 */
#define XRT_MODULE_ALL
#define XRT_IMPLEMENTATION
#include <xrt.h>
#include <stdio.h>

typedef struct node { int Value; struct node* Next; } node;

int main(void)
{
	xarray tArray;
	node* pChain = NULL;
	xtime t0, t1;
	long long iSum = 0;

	xrtArrayInit(&tArray, sizeof(int));
	for ( int i = 0; i < 1000000; ++i ) {
		int v = i;
		xrtArrayPush(&tArray, &v);
	}
	for ( int i = 0; i < 1000000; ++i ) {
		node* p = (node*)xrtMalloc(sizeof(node));
		p->Value = i; p->Next = pChain; pChain = p;
	}

	t0 = xrtNow();
	for ( size_t i = 0; i < tArray.Count; ++i ) {
		iSum += *(int*)xrtArrayGet(&tArray, i);
	}
	t1 = xrtNow();
	printf("array scan: %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);

	iSum = 0;
	t0 = xrtNow();
	for ( node* p = pChain; p != NULL; p = p->Next ) {
		iSum += p->Value;
	}
	t1 = xrtNow();
	printf("list  scan: %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);

	while ( pChain != NULL ) {
		node* p = pChain->Next;
		xrtFree(pChain);
		pChain = p;
	}
	xrtArrayUnit(&tArray);
	return 0;
}

刚才发生了什么。 两种结构装同样的百万个整数、求和结果一致。数组是一块连续内存，硬件预取器把遍历变成流水线；链表每跳一次都是一次潜在的缓存未命中——百万跳就是百万次"等内存"。教科书里链表的"插删 O(1)"没有骗你，但你的负载里插删只占千分之一：热操作的常数才是决策变量。把插删配比调到 50% 重跑一次，你会看到差距收窄——决策地图的每个格子背后，都应该有这样一张你自己机器上的实测表。

对照实验二：数组线性查找 vs 映射定位

/* race_lookup.c —— 十万条记录，十万次按键查找 */
#define XRT_MODULE_ALL
#define XRT_IMPLEMENTATION
#include <xrt.h>
#include <stdio.h>

typedef struct item { int Key; int Value; } item;

static item Items[100000];

int main(void)
{
	xmap tMap;
	xtime t0, t1;
	long long iSum = 0;

	for ( int i = 0; i < 100000; ++i ) {
		Items[i].Key = i * 7;
		Items[i].Value = i;
	}
	xrtMapInit(&tMap, sizeof(int));
	for ( int i = 0; i < 100000; ++i ) {
		int Key = Items[i].Key;
		xrtMapGetOrAdd(&tMap, (xbytesview){ &Key, sizeof(Key) }, NULL);
	}

	t0 = xrtNow();
	for ( int i = 0; i < 100000; ++i ) {
		int Key = i * 7;
		for ( size_t j = 0; j < 100000; ++j ) {
			if ( Items[j].Key == Key ) {
				iSum += Items[j].Value;
				break;
			}
		}
	}
	t1 = xrtNow();
	printf("array linear: %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);

	iSum = 0;
	t0 = xrtNow();
	for ( int i = 0; i < 100000; ++i ) {
		int Key = i * 7;
		int* pValue = (int*)xrtMapGet(
			&tMap, (xbytesview){ &Key, sizeof(Key) });
		if ( pValue != NULL ) {
			iSum += *pValue;
		}
	}
	t1 = xrtNow();
	printf("map lookup  : %lld us (sum=%lld)\n",
		(long long)(t1 - t0), iSum);
	xrtMapUnit(&tMap);
	return 0;
}

刚才发生了什么。 同样的十万次按键取值，数组线性扫描是 O(n) 每次——总操作数百亿级；映射每次摊还 O(1)。三个数量级的差距已经不属于"常数之争"，是量级问题——决策地图里"定位热→映射"这条规则背后就是这张表。注意对照的公平性：数组若先排序再二分，差距会缩小到约一个数量级——对照实验要给每个候选它最强的形态，否则你测的是"稻草人"。

卷三收官：从格子到直觉

选型地图的终点不是背格子，是把格子内化成直觉——判断标志是：看到一段需求描述，脑子里自动浮现"权威存储放哪、视图搭哪、热操作谁扛"，三十秒内说出候选与验证方法，并且知道哪个反选型问题最可能坑到你。到这一步，卷三的十一个容器就不再是十一个工具，而是一张随取随用的心智地图——卷四开始的解析、卷六开始的并发、卷七开始的网络，都在这张地图上继续加盖楼层。

23.4契约

• 三问定型：归属→顺序→访问模式，按序筛候选。
• 权威存储+视图：数据一份、视图按需，拒绝万能容器。
• 实测裁决：固定规模与配比、三取中位、内存侧证据并行（第 6 章统计）；给每个候选最强形态，不打稻草人。
• 反选型五问：万能容器/链表插删/哈希最快/先上锁/池治百病——每条都在地图上标了替代答案。
• 并发边界：除队列外本卷容器均非线程安全，跨线程方案在卷六——设计期就带着这个边界，别等并发化改造时返工。

组合拳：三个高频架构速写

决策地图的格子之外，三个"多容器组合"的架构在实际项目里反复出现，值得整段记住。资源管理器：固定池放对象（权威存储）+ xmap 做键定位 + 侵入式链表维护时序（LRU/清理序）+ slot_map 出借代际句柄——四个容器各一格，合成一套完整的"取放、定位、时序、引用"体系，第 67 章网络连接表是它的并发放大版。解析器工作区：固定栈做帧栈（深度受资源边界约束）+ arena 放临时片段（随作用域回收）+ xmap 做符号表（插入序导出报错信息）——卷四第 31 章会原样用到。事件流水线：SPSC 队列两级串联（采集→聚合→处理）+ 聚合侧固定池复用事件对象——卷六的日志与监控线程是这个骨架的成品。三个速写的共同点：没有一处是"聪明"的容器选择，全部是三问答完后的自然结果——这也是本章希望你带走的最终状态：选型不再是灵感，是流程。

什么时候重构容器选择

容器选型不是一次性的。三个信号出现时就该回到决策地图：量级跨档（数据从千级涨到百万级，数组的线性查找从无感变成瓶颈——本章实验二的数字提前打预防针）；访问模式漂移（原本遍历为主的页面加入了高频定位——加视图比重写权威存储便宜）；并发化改造（单线程模块要跨线程共享——除队列外的答案全在卷六，别在容器层硬扛）。把这三信号写进技术债清单的检查项，容器层的技术债就不会"沉默增长到爆仓"。

常见错误

/* 需求：按键定位 + 键序导出。惯性：我都会链表 */
xlist Pending;   /* 定位 O(n)、无序——两个需求都没满足 */

/* 三问：归属=对象自持；顺序=键序；模式=定位+范围 */
/* 答案：侵入式 AVL（对象已存在，加节点字段挂树） */
xavl ByKey;

if ( Complexity == "O(1)" ) {
	Choose(It);          /* 链表插删 O(1) → 选链表，遍历热负载直接翻车 */
}

/* 固定规模与配比，两候选各跑三遍取中位，用数字选 */
Benchmark(候选A, 负载);
Benchmark(候选B, 负载);
Choose(winner_by_measurement);

编程练习

小结