第 14 章 动态数组 xarray

本章导读

卷三从最常用的容器讲起。xarray 把元素字节直接连续存放——缓存友好、零逐元素分配，配合公开的 Count 字段与 qsort 兼容的排序接口，覆盖"装一批记录、排序、遍历"这条最高频路径。本章同时讲它的孪生兄弟 xptrarray（存指针、装多态对象），把"值语义 vs 指针语义"这个贯穿卷三的选型问题在第一章就钉死。容器家族的共同约定（Init/Unit 生命周期、失败无副作用、借用与拥有的边界）也从本章开始建立。

14.1引入

一个后台服务要维护"当前在线会话"列表：高峰几千条、每秒几十次增删，还要定期按优先级排序输出。这组需求翻译成容器语言就是三句话：追加要摊还 O(1)、排序要原地零分配、遍历要缓存友好。用裸数组要自己管扩容与拷贝；用链表丢了连续性、排序退化；自己造轮子则要面对第 6 章那些失败路径的考验。xarray 的答案很朴素：连续存储 + 倍增扩容 + 批量操作——追加三个元素是一次 memcpy，排序是原地 qsort 语义，遍历是缓存最友好的顺序访问。朴素的方案赢在常数因子，而容器的性能之争大半是常数因子之争。

什么时候朴素方案不够？元素很大且频繁中段插入删除时，连续存储的搬移成本线性增长——那是第 20 章 AVL 树与第 18 章 map 的领地；元素需要多态（不同类型混装）时，值语义放不下——那是 xptrarray 与指针容器的领地。还有一个不那么明显的边界：当"按下标"本身不够、外部需要稳定的对象标识时，数组的下标会因删除而漂移——那是第 17 章 slot_map 代际句柄的领地。容器的世界里没有万能药，只有一张越来越精确的选型地图，本章是地图的第一块拼图。

14.2概念

值语义：元素就是字节

xrtArrayInit(&arr, sizeof(元素类型)) 只需要元素大小——数组对元素类型完全泛型。元素直接内嵌在数组自己的内存里：没有逐元素的分配（追加 100 个元素可能一次分配都不做），没有指针跳转（遍历时预取器满血工作），元素的地址在扩容前稳定、扩容后整体搬迁。值语义的直接推论：持有数组期间拿到的元素指针，在扩容后会失效——这是本章坑 1 的主角。

生命周期与公开字段

tRecords.Count 是公开字段——遍历与容量判断不需要函数调用。XRT 容器的普遍约定：只读状态走公开字段，会失败的操作走函数（返回 bool 并配合第 4 章错误槽）。这让热路径的读访问零开销，同时失败路径保有完整诊断。

扩容策略与 Reserve

动态数组的容量增长是倍增策略：容量不足时按倍数扩张、整体搬迁。这保证了"追加 N 个元素的总搬迁成本是 O(N)"的摊还 bound——但单次 Append 仍可能触发一次大分配。已知量级时 Reserve(N) 一次到位，把摊还变成确定：装载 10 万条记录前先 Reserve(100000)，全程只有一次分配。配套的 Resize 显式设定元素数（增长的新元素为零值）、Trim 把容量收缩到当前元素数——装载完成、转入只读阶段后 Trim 一刀，长期驻留的内存立刻清爽。这一组容量 API（Reserve/Resize/Trim）是卷三所有动态容器的标配，语义在 xarray、xbuffer、xmap 上一致。

排序与查找

xrtArraySort 接受 qsort 兼容的比较函数——任何按 </> 三态写的比较器都能用。示例里那个 (a>b)-(a<b) 写法值得学：它避免了 a-b 的减法溢出（两个大负数相减翻转符号，排序结果悄悄错乱）。排好序的数组可用查找族按下标二分；查找函数接受"按元素查"与"按键查"（回调比较）两种形态。

指针数组：多态的入口

值数组解决了"同型元素的密集存放"，但有两类需求它天然接不住：元素是不同具体类型（渲染器里的形状族、解释器里的节点族），或元素的所有权属于别处（缓存不拥有对象，只是引用它们）。xptrarray 存的是指针——元素可以是不同具体类型（通过公共首部多态）、可以由别的容器拥有、可以是栈对象。代价：多一次间接跳转、逐元素的生命周期要你自己管（数组 Unit 不释放指针指向的对象）。选型口诀：元素同型且频繁整体遍历 → 值数组；元素多态或归属别处 → 指针数组。还有一个隐蔽但常见的第三选项：两者混用——值数组存"键与句柄"做密集索引，对象本体散放在池或 slot_map（第 17 章）里。本章练习的会话表就是这种"数组 + 句柄"架构的预演，第 67 章的网络连接表是它的完全体。

除了 Init，还有两个起步姿势值得知道：Create 直接返回堆上的数组对象（句柄本身也在堆上，适合放进别的结构长期持有），InitAligned 指定元素对齐（SIMD 或原子字段场景）。Clear 把元素数归零但保留容量——循环复用一批数组时，Clear 比配对的 Unit/Init 快得多，也不碰分配器。

14.3示例

完整程序：批量追加与原地排序

来自仓库范例 examples/containers/array/main.c：

 */

#include <stdio.h>

#include <xrt.h>



/* 示例记录：整条记录（而非指针）会直接放进数组内存。 */
typedef struct examplerecord {
	int ID;
	int Priority;
} examplerecord;






 */
static int exampleCompareRecord(const void* pLeft, const void* pRight)
{
	const examplerecord* pLeftRecord = (const examplerecord*)pLeft;
	const examplerecord* pRightRecord = (const examplerecord*)pRight;

	return (pLeftRecord->Priority > pRightRecord->Priority) -
		(pLeftRecord->Priority < pRightRecord->Priority);
}



int main(void)
{
	xarray tRecords;         /* 栈上句柄；缓冲由数组自己管理 */
	examplerecord pInput[] = {
		{ 101, 30 },
		{ 102, 10 },
		{ 103, 20 }
	};

	/* 初始化只需要元素大小——数组对元素类型完全泛型。 */
	if ( !xrtArrayInit(&tRecords, sizeof(examplerecord)) ) {
		return 1;
	}

	/* 一次追加 3 条（单次 memcpy + 可能的扩容），再原地排序。 */
	if (
		!xrtArrayAppend(&tRecords, pInput, 3) ||
		!xrtArraySort(&tRecords, exampleCompareRecord)
	) {
		xrtArrayUnit(&tRecords);
		return 2;
	}

	


	 */
	for ( size_t i = 0; i < tRecords.Count; i++ ) {
		examplerecord* pRecord = (examplerecord*)xrtArrayGet(&tRecords, i);

		printf("id=%d priority=%d\n", pRecord->ID, pRecord->Priority);
	}
	xrtArrayUnit(&tRecords);
	return 0;
}

刚才发生了什么。 ① xrtArrayInit 只传元素大小——泛型不靠宏不靠模板，靠"字节搬家"。② xrtArrayAppend(&tRecords, pInput, 3) 一次追加三条（单次 memcpy 加可能的扩容），批量接口比逐个 Append 少两次函数调用与两次容量检查。③ xrtArraySort 原地把乱序输入排成优先级升序——输出顺序 10/20/30 验证。④ 遍历用公开字段 Count 与 Get；Get 返回的是数组内存里的直接指针（可读写），越界返回 NULL。⑤ Unit 归还缓冲——数组句柄本身在栈上，归还的只是堆缓冲。

完整程序：指针数组遍历

来自 examples/containers/ptr_array/main.c，演示指针语义的存储与遍历：

 */

#include <stdio.h>
#include <xrt.h>



int main(void)
{
	xptrarray tArray;
	int iFirst = 10;
	int iSecond = 20;
	int iThird = 30;

	if ( !xrtPtrArrayInit(&tArray) ) {
		return 1;
	}

	


	 */
	if (
		!xrtPtrArrayPush(&tArray, &iFirst) ||
		!xrtPtrArrayPush(&tArray, &iSecond) ||
		!xrtPtrArrayInsert(&tArray, 1, &iThird)
	) {
		xrtPtrArrayUnit(&tArray);
		return 2;
	}

	/* 解引用打印：Get 返回 ptr，转回 int* 后取值。 */
	for ( size_t i = 0; i < tArray.Count; i++ ) {
		printf("[%zu] %d\n", i, *(int*)xrtPtrArrayGet(&tArray, i));
	}

	/* 释放的是指针槽位本身；栈上的目标对象不受影响。 */
	xrtPtrArrayUnit(&tArray);
	return 0;
}

刚才发生了什么。 数组里存的是 ptr——指向别处对象的引用。遍历取出的元素是"指针的值"，对象本体不在数组内存里。三种典型来源都合法：栈对象（本例）、其他容器拥有的对象、由你逐个分配并最终逐个释放的对象。注意指针数组的 Unit 只归还指针槽的存储——指向的对象一个都不会被释放，归属纪律完全在调用方，这正是坑 2 的主题。

把两个示例并排读一遍，"值 vs 指针"的取舍就立体了：值数组一次 memcpy 装三条记录、排序时整块搬家、遍历零间接；指针数组每次操作多一次解引用、排序搬的是 8 字节指针（元素本体不动——这对大对象反而是优势）、支持多态混装。经验法则：元素小于一个缓存行且同型，值数组几乎总是赢；元素巨大、或来自不同分配源、或需要多态，指针数组。

容器家族的共同约定（从本章开始生效）

本章建立的三条约定会贯穿卷三全部容器，先在这里立好，后面各章直接引用。约定一：句柄在栈、内存在堆——Init 拿栈上句柄开张，容器自管缓冲，Unit 精确归还；需要容器对象本身上堆时用 Create/Destroy 配对。约定二：读走字段、写走函数——只读状态（Count、Size、Data）是公开字段，零开销直读；会失败的操作全部走函数返回值并配合第 4 章错误槽。约定三：失败无副作用——任何编辑操作失败时容器保持调用前的状态，这让 Cleanup 段的代码可以写得毫无心理负担。三条约定的收益在后面每一章复利：读到任何一个新容器，你已经知道它的生命周期形状、字段风格与失败语义——只剩"这个容器擅长什么"一个新问题。

14.4契约

• 生命周期：Init/Unit 精确配对；失败路径同样要 Unit（失败无副作用让这行清理代码永远安全）。
• 公开字段：Count 等只读状态直接读字段；会失败的操作走函数返回值。
• 指针时效：扩容会使既有元素指针失效——需要稳定地址就先备好容量或改用指针数组/链表。
• 越界行为：Get 越界返回 NULL；编辑类操作越界失败并设置错误，绝不越界写。
• 指针数组归属：Unit 不释放元素指向的对象；谁分配谁释放。
• 比较器：用三态 (a>b)-(a<b) 风格，禁用 a-b（溢出）。
• 容量三件套：Reserve 预扩张、Resize 定长、Trim 收紧；Clear 归零保容量；语义与卷三所有动态容器一致。

常见错误

examplerecord* pRecord = (examplerecord*)xrtArrayGet(&tRecords, 0);
xrtArrayAppend(&tRecords, pMore, 100);   /* 可能触发扩容+搬迁 */
pRecord->ID = 42;                         /* pRecord 指向已释放的旧缓冲 */

examplerecord* pRecord;
xrtArrayAppend(&tRecords, pMore, 100);   /* 先做可能扩容的操作 */
pRecord = (examplerecord*)xrtArrayGet(&tRecords, 0);   /* 再取指针 */
pRecord->ID = 42;

xptrarray tObjects;
/* ... 装入一批 xrtMalloc 的对象 ... */
xrtPtrArrayUnit(&tObjects);   /* 只归还指针槽——元素全部泄漏 */

for ( size_t i = 0; i < tObjects.Count; i++ ) {
	xrtFree(xrtPtrArrayGet(&tObjects, i));   /* 先逐个归还元素 */
}
xrtPtrArrayUnit(&tObjects);                  /* 再归还数组本体 */

编程练习

小结