30、综合实战：实现一个动态数组库（Vector）

终于到了最后一章实战课。说实话，前面讲了那么多内存分配的原理、陷阱、调试技巧，如果不亲手写一个能用的库，总觉得少了点什么。

今天我们就来实现一个动态数组库——我习惯叫它 Vector。为什么选这个？因为动态数组是 C 语言里最常用的数据结构之一，而且它完美地融合了 malloc、realloc、free 以及内存管理的各种细节。你想想看，一个项目里如果连动态数组都写不好，那内存泄漏基本是板上钉钉的事。

设计目标

我们要实现一个轻量级的 Vector，支持以下操作：

• 初始化：创建一个空数组，预留初始容量
• 插入：在尾部追加元素
• 删除：移除尾部元素
• 扩容：容量不足时自动翻倍
• 销毁：释放所有内存

嗯，这里要注意：我们不追求 STL 那种花哨的泛型，而是用 void* 配合元素大小来实现通用性。说白了，就是存任意类型的数据。

数据结构定义

typedef struct {
    void* data;        // 数据指针
    size_t elem_size;  // 每个元素的大小（字节）
    size_t capacity;   // 当前容量（元素个数）
    size_t size;       // 实际元素个数
} Vector;

我个人习惯把 capacity 和 size 分开存。为什么？因为这样扩容逻辑才清晰。容量是已经分配好的空间，大小是实际用到的空间。两者相等时，就该扩容了。

初始化函数

int vector_init(Vector* vec, size_t elem_size, size_t initial_capacity) {
    vec->data = malloc(elem_size * initial_capacity);
    if (!vec->data) return -1;  // 分配失败

    vec->elem_size = elem_size;
    vec->capacity = initial_capacity;
    vec->size = 0;
    return 0;
}

这里有个小细节：initial_capacity 不能为 0。我在项目中遇到过有人传 0 进来，结果 malloc(0) 的行为是未定义的。所以最好加个断言或者默认给个最小值，比如 4。

扩容机制

int vector_reserve(Vector* vec, size_t new_capacity) {
    if (new_capacity <= vec->capacity) return 0;

    void* new_data = realloc(vec->data, vec->elem_size * new_capacity);
    if (!new_data) return -1;  // 扩容失败

    vec->data = new_data;
    vec->capacity = new_capacity;
    return 0;
}

static int vector_grow(Vector* vec) {
    size_t new_capacity = vec->capacity * 2;
    if (new_capacity == 0) new_capacity = 4;  // 防止初始容量为0
    return vector_reserve(vec, new_capacity);
}

扩容策略我选的是翻倍。为什么不是加固定大小？你想想看，如果每次只加 10 个元素的空间，那插入 1000 个元素就要 realloc 100 次，性能太差了。翻倍的话，realloc 的次数是 O(log n)，而且均摊下来每次插入的时间复杂度是 O(1)。

插入与删除

int vector_push_back(Vector* vec, const void* elem) {
    if (vec->size >= vec->capacity) {
        if (vector_grow(vec) != 0) return -1;
    }

    // 计算目标地址，拷贝元素
    void* target = (char*)vec->data + vec->size * vec->elem_size;
    memcpy(target, elem, vec->elem_size);
    vec->size++;
    return 0;
}

int vector_pop_back(Vector* vec) {
    if (vec->size == 0) return -1;  // 空数组不能删除
    vec->size--;
    return 0;
}

注意看 target 的计算：(char*)vec->data + vec->size * vec->elem_size。这里把 void* 转成 char* 是为了做指针运算，因为 C 标准不允许对 void* 做算术操作。嗯，这个坑我踩过，当时编译报错我还愣了半天。

删除操作其实只是把 size 减一，并没有真正释放内存。为什么？因为释放内存是 vector_destroy 的事。而且如果删了又插，频繁 realloc 反而更慢。

销毁函数

void vector_destroy(Vector* vec) {
    free(vec->data);
    vec->data = NULL;
    vec->capacity = 0;
    vec->size = 0;
}

我曾经见过有人只 free 不置 NULL，结果后面不小心又用了这个指针，导致野指针崩溃。所以我的习惯是：free 之后立刻置 NULL，这样即使误用也会立刻 crash，而不是随机崩溃。

完整使用示例

#include <stdio.h>
#include "vector.h"

int main() {
    Vector vec;
    vector_init(&vec, sizeof(int), 4);

    for (int i = 0; i < 100; i++) {
        vector_push_back(&vec, &i);
    }

    printf("size = %zu, capacity = %zu\n", vec.size, vec.capacity);

    // 打印前10个元素
    for (size_t i = 0; i < 10; i++) {
        int* p = (int*)vec.data + i;
        printf("%d ", *p);
    }
    printf("\n");

    vector_destroy(&vec);
    return 0;
}

核心流程一览

下面这张图展示了 Vector 从初始化到销毁的完整生命周期：

避坑指南

• 我曾经在 realloc 失败后直接覆盖了原指针，结果原数据也丢了。正确的做法是先用临时变量接收 realloc 的返回值，检查成功后再赋值。
• 我曾经忘记在 vector_destroy 里把 size 和 capacity 清零，结果调试时看到非零值以为还有数据，浪费了半天时间。
• 注意：如果你的元素类型包含指针（比如字符串数组），那么 vector_destroy 之前需要先遍历释放每个元素内部的资源。这个库只管理内存本身，不管理元素内部的资源。

性能对比

操作	时间复杂度	备注
尾部插入（均摊）	O(1)	扩容时 O(n)，但均摊后是常数
尾部删除	O(1)	只减 size，不释放内存
随机访问	O(1)	通过指针偏移直接访问
扩容	O(n)	需要拷贝所有元素
销毁	O(1)	只释放一次内存

好了，这个 Vector 库虽然简单，但五脏俱全。你可以在它的基础上扩展出更多功能，比如 vector_insert、vector_erase、vector_clear 等。记住，写库代码时，接口设计比实现更重要——好的接口让使用者不容易犯错，差的接口让所有人头疼。

动手试试吧，把代码跑起来，然后试着改一改，加一加功能。只有亲手写过，才能真正理解动态内存管理的精髓。