C / C++ / 系统课时
容量不足时怎样扩容
容量不足时怎样扩容
顺序表使用连续内存保存元素,已用长度达到容量上限后,继续插入就必须先获得更大的存储空间。本节实现一个自动扩容的顺序表,并理解倍增容量为什么能减少频繁搬迁,同时兼顾内存占用与插入效率。
学习目标
- 区分顺序表的元素数量
size与已分配容量capacity - 使用
realloc安全地扩大连续存储空间 - 理解倍增扩容对插入性能和内存使用的影响
先区分长度和容量
顺序表通常至少维护三个信息:数据区指针、当前元素数量和当前容量。size 表示已经存入多少个元素,capacity 表示当前内存最多能容纳多少个元素。
当 size < capacity 时,可以直接把新元素写到 data[size]。当 size == capacity 时,原有内存已经没有空位,必须扩容后才能继续写入,否则会越界访问未分配的内存。
扩容并不是每插入一个元素就申请一次内存。常见策略是在容量耗尽时一次扩大到原来的两倍,例如从 2 变成 4,再从 4 变成 8。这样虽然单次扩容可能需要复制已有数据,但扩容发生的次数会明显减少。
实现自动扩容
下面给出一个可运行的顺序表示例。ensure_capacity 只在容量真正不足时调用 realloc,并先把返回值保存到临时指针中,避免扩容失败后丢失原来的内存地址。
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data;
size_t size;
size_t capacity;
} SeqList;
int init_list(SeqList *list, size_t initial_capacity) {
list->data = malloc(initial_capacity * sizeof(int));
if (list->data == NULL) {
return 0;
}
list->size = 0;
list->capacity = initial_capacity;
return 1;
}
int ensure_capacity(SeqList *list) {
if (list->size < list->capacity) {
return 1;
}
size_t new_capacity = list->capacity == 0 ? 2 : list->capacity * 2;
/* 先保存 realloc 的结果,失败时原指针仍然有效。 */
int *new_data = realloc(list->data, new_capacity * sizeof(int));
if (new_data == NULL) {
return 0;
}
list->data = new_data;
list->capacity = new_capacity;
return 1;
}
int append(SeqList *list, int value) {
if (!ensure_capacity(list)) {
return 0;
}
list->data[list->size++] = value;
return 1;
}
int main(void) {
SeqList list;
if (!init_list(&list, 2)) {
return 1;
}
int values[] = {10, 20, 30};
size_t count = sizeof(values) / sizeof(values[0]);
for (size_t i = 0; i < count; ++i) {
if (!append(&list, values[i])) {
free(list.data);
return 1;
}
printf("append %d -> size=%zu, capacity=%zu\n",
values[i], list.size, list.capacity);
}
printf("data:");
for (size_t i = 0; i < list.size; ++i) {
printf(" %d", list.data[i]);
}
printf("\n");
free(list.data);
return 0;
}预期输出
append 10 -> size=1, capacity=2
append 20 -> size=2, capacity=2
append 30 -> size=3, capacity=4
data: 10 20 30第三次插入前 size 与 capacity 都是 2,因此触发扩容。扩容成功后容量变成 4,原来的两个元素仍然保留,然后才把 30 写入新的尾部位置。
为什么常用倍增策略
如果容量每次只增加 1,那么插入大量元素时会频繁重新分配内存,并可能反复复制已有数据。假设连续插入很多元素,总搬迁量会快速增长。
倍增策略把容量按 2、4、8、16 这样的方式增长。某一次扩容仍然需要处理已有元素,因此单次成本可能是 ;但多数插入不需要扩容,连续多次尾部插入的平均成本可以看作摊还 。
代价是扩容后会暂时存在未使用空间。例如从容量 8 扩到 16 后,如果只存了 9 个元素,就有 7 个位置暂时空闲。因此增长倍率越大,扩容次数通常越少,但可能预留更多暂时不用的内存。
扩容失败时怎样处理
realloc 可能因为内存不足而返回 NULL。不要直接写成 list->data = realloc(...),因为一旦失败,就会覆盖保存原内存地址的唯一指针,造成内存泄漏。
正确做法是先接收到临时指针,确认成功后再更新 data 和 capacity。同时,只有扩容成功才能继续执行插入;失败时应把错误传递给调用者,让上层决定退出、重试或采取其他处理方式。
顺序表自动扩容的核心并不是单纯调用一次 realloc,而是把容量检查、增长策略、失败保护和插入顺序组合起来:先保证空间足够,再写入元素,最后更新长度。