【C/C++】纯C实现变长数组
编写一个动态数组库可以帮助我们深入理解数据结构和内存管理,特别是在没有 C++ STL 的情况下使用 C 语言创建动态数组。我们将逐步搭建这个动态数组库(称为 Vector),并逐行解释其实现方式,让读者理解每一行代码的作用和实现细节。
基础结构设计
在 C 语言中,我们常使用固定大小的数组,但动态数组则能灵活扩展。这里的目标是设计一个宏生成的动态数组结构体,确保我们能在编译时创建适用于各种数据类型的动态数组。
#define Vector(type) \struct { \size_t size; \size_t capacity; \type *data; \}
解释:
Vector(type)
是一个宏,它使用传入的type
数据类型定义了一个动态数组的结构体。size_t size
:用于跟踪数组中元素的数量。size_t capacity
:记录当前分配的内存空间允许存储的最大元素数。type *data
:存储实际数据的指针。
注意:我们没有使用命名空间封装,因为这是 C 语言而非 C++。这个宏将在使用时扩展为结构体定义,使用时需实例化变量并指定 type
类型。
初始化动态数组
为了使用动态数组,我们需要一个初始化宏,用于设置 size
和 capacity
的初始值。
#define VecInit(vec) \do { \(vec).size = 0; \(vec).capacity = 0; \(vec).data = NULL; \} while (0)
解释:
VecInit
是初始化宏,用于将动态数组的size
和capacity
设置为 0,并将data
指针初始化为NULL
。- 使用
do...while(0)
包裹是 C 中的一种安全宏写法,可以避免宏在使用过程中出现错误。
销毁动态数组
为了避免内存泄漏,在不再需要动态数组时,我们应当释放它所占用的内存。
#define VecDestroy(vec) free((vec).data)
解释:
free((vec).data)
用于释放data
指针所指向的内存。注意我们只释放data
的内存,因为size
和capacity
是栈上分配的,不需要显式释放。
访问动态数组的元素
创建一个简单的宏,用于直接访问数组的元素:
#define VecAt(vec, i) ((vec).data[(i)])
解释:
VecAt
宏用于访问索引i
处的元素,相当于数组的下标运算。- 需要注意访问的
i
索引应在size
范围内,否则可能引发越界错误。
弹出元素
我们实现一个弹出数组最后一个元素的功能,并减少数组的 size
。
#define VecPop(vec) ((vec).data[--(vec).size])
解释:
VecPop
将size
减一,并返回该位置的元素。因为我们并未真正删除内存中的值,只是标记最后一个元素不可用。
获取数组的大小和容量
我们提供两个简单的宏来获取数组的大小和容量,便于在使用过程中查看动态数组的状态。
#define VecSize(vec) ((vec).size)
#define VecCapacity(vec) ((vec).capacity)
解释:
VecSize
返回动态数组的当前元素个数,而VecCapacity
则返回已分配的内存容量。
调整数组容量
动态数组的核心是可以在容量不够时自动扩展,我们通过 VecResize
宏来实现这一点。
#define VecResize(vec, new_size) \do { \(vec).capacity = (new_size); \(vec).data = (typeof((vec).data))realloc((vec).data, sizeof(*(vec).data) * (vec).capacity); \} while (0)
解释:
VecResize
将capacity
设置为new_size
,并使用realloc
重新分配data
指针的内存空间。(typeof((vec).data))
是 GNU C 扩展typeof
的用法,用于确保realloc
返回的void*
被转换为正确的指针类型。realloc
将现有数据复制到新分配的内存空间中。如果new_size
小于当前容量,则会截断数据。
复制动态数组
在某些情况下,我们可能需要将一个动态数组的内容复制到另一个数组中,这可以通过 VecCopy
宏来实现。
#define VecCopy(dest, src) \do { \if ((dest).capacity < (src).size) \VecResize(dest, (src).size); \(dest).size = (src).size; \memcpy((dest).data, (src).data, sizeof(*(src).data) * (src).size); \} while (0)
解释:
VecCopy
首先检查dest
的容量是否大于src
的大小,如果不是则调整dest
的大小。- 然后使用
memcpy
复制数据内容。
添加元素到数组
当数组满时自动扩展容量,将新元素添加到数组尾部。
#define VecPush(vec, value) \do { \if ((vec).size == (vec).capacity) { \(vec).capacity = (vec).capacity ? (vec).capacity * 2 : 2; \(vec).data = (typeof((vec).data))realloc((vec).data, sizeof(*(vec).data) * (vec).capacity); \} \(vec).data[(vec).size++] = (value); \} while (0)
解释:
VecPush
首先检查是否已达当前容量限制,若已满则将容量扩大一倍(或最小值 2)。realloc
调整data
指针的内存空间,并将新元素value
放入数组的尾部。
排序数组
我们可以使用 C 标准库中的 qsort
函数对数组进行排序。
#define VecSort(vec, cmp) \do { \if ((vec).size > 1) { \qsort((vec).data, (vec).size, sizeof(*(vec).data), cmp); \} \} while (0)
解释:
VecSort
使用qsort
对数组进行排序,需要传入比较函数cmp
。- 这里的
qsort
将data
中的元素按指定的比较规则排序。 cmp
是用户自定义的比较函数,用于指定排序方式。
非GCC实现
typeof
是 GCC 提供的扩展,不在 C 标准中,因此在其他编译器(如 MSVC、Clang 在标准模式下)中可能不可用。为了确保跨平台兼容性,typeof
可以用更通用的写法替代,比如通过传入数据类型参数来避免依赖非标准的特性。
例如,可以重构如下:
#define Vector(type) \struct { \size_t size; \size_t capacity; \type *data; \}#define VecResize(vec, type, new_size) \do { \(vec).capacity = (new_size); \(vec).data = (type *)realloc((vec).data, sizeof(type) * (vec).capacity); \} while (0)#define VecPush(vec, type, value) \do { \if ((vec).size == (vec).capacity) { \(vec).capacity = (vec).capacity ? (vec).capacity * 2 : 2; \(vec).data = (type *)realloc((vec).data, sizeof(type) * (vec).capacity); \} \(vec).data[(vec).size++] = (value); \} while (0)
在这里:
- 我们在
VecResize
和VecPush
宏中加入了type
参数,避免使用typeof
关键字。 - 调用
VecPush
和VecResize
时,需要显式指定数据类型,如VecPush(my_vector, int, 5);
,从而确保在任何编译器上都能正确识别并处理指针类型转换。
这种写法稍显冗长,但可以更好地兼容不同的编译器。
总结
通过以上宏,我们实现了一个基础的 C 语言动态数组库,包括初始化、销毁、添加、访问、弹出、复制和排序等操作。这个库使用 C 的动态内存管理来支持数组自动扩展,适用于任意类型的数据。这种宏定义的写法避免了复杂的函数模板,便于理解和扩展。下面展示了完整代码:
#ifndef VECTOR_H
#define VECTOR_H#include <stdlib.h> // 引入标准库,便于使用内存管理函数// 定义动态数组结构体
#define Vector(type) \struct { \size_t size; \size_t capacity; \type *data; \}// 初始化动态数组
#define VecInit(vec) \do { \(vec).size = 0; \(vec).capacity = 0; \(vec).data = NULL; \} while (0)// 销毁动态数组,释放内存
#define VecDestroy(vec) free((vec).data)// 获取索引 i 处的元素
#define VecAt(vec, i) ((vec).data[(i)])// 弹出最后一个元素
#define VecPop(vec) ((vec).data[--(vec).size])// 获取当前元素个数
#define VecSize(vec) ((vec).size)// 获取当前容量
#define VecCapacity(vec) ((vec).capacity)// 调整动态数组容量
#define VecResize(vec, new_size) \do { \(vec).capacity = (new_size); \(vec).data = (typeof((vec).data))realloc((vec).data, sizeof(*(vec).data) * (vec).capacity); \} while (0)// 复制另一个动态数组的内容
#define VecCopy(dest, src) \do { \if ((dest).capacity < (src).size) \VecResize(dest, (src).size); \(dest).size = (src).size; \memcpy((dest).data, (src).data, sizeof(*(src).data) * (src).size); \} while (0)// 向动态数组末尾添加元素,如果需要,自动扩展数组容量
#define VecPush(vec, value) \do { \if ((vec).size == (vec).capacity) { \(vec).capacity = (vec).capacity ? (vec).capacity * 2 : 2; \(vec).data = (typeof((vec).data))realloc((vec).data, sizeof(*(vec).data) * (vec).capacity); \} \(vec).data[(vec).size++] = (value); \} while (0)// 对动态数组进行排序
#define VecSort(vec, cmp) \do { \if ((vec).size > 1) { \qsort((vec).data, (vec).size, sizeof(*(vec).data), cmp); \} \} while (0)#endif // VECTOR_H