先认识它,再手搓它

您要是写过几行 Python,大概率干过这件事:建一个空的 list,往里 append 十万条数据,中间一次都没操心过"会不会装不下"。凭什么?数组不是要提前定长吗?

答案先给一半:它在底下偷偷换了好几次房子,只是没告诉您。装满了就搬一栋更大的,把旧住户整队运过去,再把旧房子退掉。整个过程快得让您毫无察觉。这个结构就叫动态数组,接下来的五篇,咱们把它里里外外看清楚,然后亲手搓一个出来。

这一篇给咱们铺路:正文不放工程代码,只把三件事说透——它为什么存在,它长什么样,以及搬家贵不贵。认识清楚了,后面四册的硬仗打起来就有方向。

长度未知的世界

咱们先看看没有它会怎样。设想您在写一个读日志的小工具,日志文件有多少行?写代码的时候不知道,文件递到手里才知道。再设想一个游戏背包:玩家会捡多少件装备?策划都不知道,咱们更不可能知道。还有聊天记录、传感器采样、命令行参数,全是同一个脾气:要装多少,运行期才揭晓。

可普通数组是什么脾气?int a[10]; 一写下去,十个格子,一个都不多。想装第十一个,就是越界,是未定义行为,撞上谁算谁倒霉。这道"长度编译期定死"的墙,您当时就撞过。

有人会说,那开大一点,开一万个格子。行,内存便宜。可万一真来了一万零一条呢?开一百万?那读三行小文件的时候,九十九万多格子全程空转。您发现没有,开大开小都不对:小了装不下,大了浪费,而正确答案要到运行期才公布。

所以咱们需要一种会自己长的容器。长度没到,它按需备房;长度爆了,它自己搬家。这就是动态数组要办的全部事。

一块内存,两个数

它的样子朴素得让人意外:还是一块连续内存,不过是从 malloc 手里现拿的,旁边咱们再记两个数。一个数容量,开了几间房;一个数已用,住进去几人。用房子打比方:房子地址、房间总数、当前住户数,三样信息凑齐,一栋能换大的公寓就齐活了。

比喻搭完就拆,换机制的说法。容量乘以每个元素的字节数,就是这块内存的总大小。下标 i 的元素,住在起点往后数 i 个元素的位置。所以访问它还是一次指针算术,和普通数组一样快。这一点是动态数组立身的本钱,后面拿它跟链表对比时,咱们还会反复用到。

咱们装一个新元素,就是写进"已用"指的那一格,然后已用加一。什么时候算满?已用追上容量的那一刻。满了怎么办?去 malloc 手里换一块更大的,把旧住户整队拷过去,然后容量改成新的房间数。注意搬家前后"已用"一个没变,住户还是那些住户,变的只是房子。

骨架画出来,其实就三行:

typedef struct {
    int*   data;   /* 房子:malloc 来的连续内存 */
    size_t count;  /* 已用:住进去几个 */
    size_t cap;    /* 容量:一共开了几间房 */
} Vec;

别小看这三行。第 1 章咱们要手搓的 JYPVector,骨架和它一模一样,只是添了泛型的字节大小、可换的增长策略和分配器,长成了工程的样子。内核没有变。

您早就在用它

如果您觉得这结构眼生,其实您天天在用。Python 的 list,内核就是它。C++ 的 std::vector,名字直接就是"向量",内核也是它。Java 的 ArrayList,类名把话挑明了:Array 的 List,还是它。Rust 的 Vec<T>,缩写自 vector,同样还是它。

这几家语言各自身价不同,给这个结构配的礼节也各有讲究:有的增长步子大,有的步子小;有的内存紧张时会更精细地收缩。但拆开看,内核是同一套三件:连续内存、两个计数、满了搬家。咱们要手搓的,就是这套被亿万行代码踩在脚下的内核本身。搓完这一遍,您再去看任何一家的文档或源码,门牌全都认得。

不过这几家的搬家节奏并不相同,这里透一个底:Python 的 list 就没有翻倍,它用一种温和得多的步子。为什么、代价是什么,第 2 章咱们拿探针去量它的源码,当场对答案。

搬家贵不贵:一个直觉

听到"装满就搬家",您心里可能咯噔一下:往里塞十万个数,岂不是要搬无数次家,每次都整队拷贝?

咱们直接看两行真输出。同一个容器,同样十万次 push,只有"装满之后下一步容量给多大"这一处不同:

翻倍策略:100000 次 push,realloc 只调了 17 次(容量 131072)
+1 策略:100000 次 push,realloc 调了 99999 次(容量 100000)

翻倍,咱们只搬 17 次。每次只加一间房,要搬 99999 次。差距为什么会这么大?直觉是这样的:每次搬家房间数翻一倍,那么房间数从 1 涨到十万,需要的搬家次数就是"翻多少个倍"的事,十万的量级只要十七次翻倍就够。而每次加一间,每来一个新住户都得全体挪一次,一次都省不下来。

那 17 次搬家本身就便宜吗?不便宜,单次要整队拷贝。但贵的那几趟,摊到十万次 push 头上,平均每次摊到的搬运不到两个元素。偶尔贵一次,贵得有数,长远平均几乎可以忽略——这就是算法书里"摊还 O(1)"说的人话版本。正式的数学,第 2 章咱们亲手一项一项加出来。

这两个数您不用信书,点开下面这个沙盒就能亲手复现,改成自己的策略再跑一遍也行:

Compiler Explorer

亲手玩:十万次 push,realloc 各调几次

就是上面那两行输出的来历:一个自包含的小 vector 配上会数数的分配器。咱们把 plus_one 改成加四或翻三倍,再点运行,看看次数怎么变。

/demos/vector_amort.c

四册地图

铺路铺到这里,正式的手搓从第 1 章开始。四册各打一场,给您指个路。第 1 章把它用起来:接口怎么设计、越界了怎么办、中间插一个元素为什么全数组跟着挪。第 2 章拆"怎么长":扩容的机关、翻倍的数学、和 CPython 的增长曲线对答案。第 3 章拆"搬家的真相":realloc 这个函数到底承诺了什么、为什么拿到手的元素指针会过期。第 4 章收尾:元素里如果装的是指针,拆房子时谁替它们办后事,以及内存不够的那一天会发生什么。

配套练习在 练习 3.5:动态数组,手搓的工程在 projects/journey_your_pack/pack1_vector,每一步都有真实的终端输出垫底。再往后的第 5 章,咱们会换一种世界观:每个节点自己 malloc、用指针串起来的链表。两种形态撑起后面几乎所有的数据结构,咱们先把眼前这一种吃透。

下一章,开工。