我知道这个标题不太像人类，但是这不重要
我们可以先来看两段代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int main(int, char **)
{
DynamicArray *arr = arr_init(3);
arr_push(arr, 10);
arr_push(arr, 20);
arr_push(arr, 30);
arr_print(arr);
arr_free(arr);
return 0;
}
int main(int, char **)
{
int *numbers = NULL;
arr_push(numbers, 69);
arr_push(numbers, 420);
arr_push(numbers, 1337);
arr_push(numbers, 80085);
for (size_t i = 0; i < arr_len(numbers); ++i)
{
printf("%d\n", numbers[i]);
}
arr_free(numbers);
}
|
第一个 main 函数中，我们初始化的是 DynamicArray * 类型的自定义动态数组结构体指针，后续所有操作函数均基于该指针类型实现；第二个 main 函数中，我们仅初始化了单纯的 int * 类型原生整型指针，配套的操作函数(宏)也仅针对这个明确数据类型的指针进行操作。
在 C 语言及绝大多数编程语言中，一个完整可用的动态数组，必须包含以下三个关键要素：
数据块 存储数组元素的连续内存空间，是动态数组的数据存储载体。
当前使用量 (count) 标记数组中有效元素的实际个数，用于控制遍历、访问边界。
容量 (capacity) 标记当前内存最大可容纳的元素总数，用于判断动态扩容的时机。
这个数据块部分，在C语言这边的话，一般来说都是由一个指向要存储元素类型的指针跟一套内存分配机制一起组成的(比如glib实现的malloc)。
在我们常见的实现方法中，这三部分通常会被存放在一个结构体中，大概像这样
1
2
3
4
5
| typedef struct{
int *items;
size_t count;
size_t capacity;
} DynamicArray;
|
我们通常会先初始化一个动态数组结构体变量(malloc或者栈分配)，再通过结构体内部的指针，操作存储数据的内存块；当容量 capacity 不足时执行的 realloc 重分配操作，就是这类内存操作的典型例子。
而我们今天提到的 Header_Array（头部数组），其典型的 Header 结构体声明如下：
1
2
3
4
| typedef struct{
size_t count;
size_t capacity;
} Header;
|
我们可以发现，这个结构体中并没有存储数组元素的成员。基于此，我们可以提出两个关键问题：
在标准实现中，头部信息会存储在显式定义的结构体变量中，我们通过变量内部的指针对数据进行操作；此时，存储头部信息与存储实际数据的内存可能是相互分离、不连续的。
而在Header_Array（头部数组）中，整个动态数组占用一整块连续的内存，头部信息会隐式地存储在数据段的前方。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| ┌──────────────────────────────────────────────────────┐
│ DynamicArray 结构体 (栈上或堆上，此处假设堆上) │
├──────────────────────────────────────────────────────┤
│ count │ capacity │ items 指针 │
│ (size_t) │ (size_t) │ (int*) │
│ 4 │ 6 │ ────────┐ │
└────────────┴─────────────┴──────────┼────────────────┘
│
↓
┌─────────────────────────────┐
│ 数据区（另一个独立堆块） │
├─────────────────────────────┤
│ 10 │ 20 │ 30 │ 40 │ ? │ ? │
└─────────────────────────────┘
┌───────────────────────────────────────────────┐
│ Header │ 数据区（用户可访问） │
│ (count, capacity)│ [0] [1] [2] [3] ... │
└───────────────────────────────────────────────┘
▲ ▲
│ │
header指针 arr 指针（用户持有）
(Header*)(arr)-1
|
这种 Header_Array 还有一个显著优势：借助宏展开，可以很方便地实现泛型动态数组。
当然，这本身也是侵入式数据结构的一大特性，这部分内容我们可以放在最后再展开说明。
实现该操作依赖的核心语法特性是：对指针进行加减运算时，地址偏移量由指针指向的数据类型大小决定。
借助这一特性，我们可以通过强制转换指针类型、执行指针运算并对结果解引用，精准获取隐藏在内存块最前端的头部信息（Header），以及其中存储的元数据。
我们可以先从一个 int 类型的侵入式动态数组入手，实现逻辑其实非常简洁：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| int *arr_init(int *ptr, int size){
if (ptr == NULL)
{
Header *header = malloc(sizeof(*ptr) * size + sizeof(Header));
header->capacity = size;
header->count = 0;
ptr = (int *)(header + 1);
}
return ptr;
}
void arr_push(int **arr_ptr, int data){
int *arr = *arr_ptr;
Header *header = ((Header *)arr - 1);
if (header->count >= header->capacity)
{
header->capacity *= 2;
header = realloc(header, sizeof(*arr) * header->capacity +
sizeof(Header));
arr = (int *)(header + 1);
*arr_ptr = arr;
}
arr[header->count++] = data;
}
void arr_free(int *arr){
free((Header *)(arr)-1);
}
|
其实只要理解了前面提到的指针运算特性—— 对指针进行加减操作时，偏移量由指针指向类型的大小决定，这段代码就很好理解、也很好写了。
这里有一个细节需要重点注意：结合 realloc 的核心特性可知，当原内存地址后无足够连续空间时，realloc() 会将内存块整体迁移至新的内存位置。
若迁移成功，函数会返回新的内存地址，原指针将失效，必须用新地址覆盖旧指针，否则会引发野指针、内存访问异常等问题。
正是由于这一特性，我们在 arr_push 函数的参数列表中特意使用二级指针，核心目的就是：当 realloc 触发内存迁移时，能够直接修改并更新原数组指针的地址，保证指针始终有效。
但这种实现方式只能处理 int 类型的动态数组，如果想支持其他数据类型，就必须为每一种类型单独编写一套操作函数。
这时我们就可以用上 C 语言的宏，借助它来实现泛型动态数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #define arr_push(arr, x) \
do { \
if (arr == NULL) { \
Header *header = \
malloc(sizeof(*arr) * ARR_INIT_CAPACITY + sizeof(Header)); \
header->count = 0; \
header->capacity = ARR_INIT_CAPACITY; \
arr = (void *)(header + 1); \
} \
Header *header = (Header *)(arr) - 1; \
if (header->count >= header->capacity) { \
header->capacity *= 2; \
header = realloc(header, sizeof(*arr) * header->capacity + \
sizeof(Header)); \
arr = (void *)(header + 1); \
} \
(arr)[header->count++] = (x); \
} while (0)
|
可以看到，使用宏时，参数类型从二级指针简化成了一级指针。这是因为 C 语言的宏本质比较原始，仅仅是做单纯的文本替换。
这段宏会在调用处直接展开，并且 arr 会在宏内部完成更新。而不需要考虑局部变量的问题
当然，这段宏不太健壮，仍然可能出现野指针之类的问题，但只是作为一个demo来说，倒也够用