C / C++ / 系统课时

容量不足时怎样扩容

容量不足时怎样扩容

顺序表使用连续内存保存元素,已用长度达到容量上限后,继续插入就必须先获得更大的存储空间。本节实现一个自动扩容的顺序表,并理解倍增容量为什么能减少频繁搬迁,同时兼顾内存占用与插入效率。

学习目标

  • 区分顺序表的元素数量 size 与已分配容量 capacity
  • 使用 realloc 安全地扩大连续存储空间
  • 理解倍增扩容对插入性能和内存使用的影响

先区分长度和容量

顺序表通常至少维护三个信息:数据区指针、当前元素数量和当前容量。size 表示已经存入多少个元素,capacity 表示当前内存最多能容纳多少个元素。

当 size < capacity 时,可以直接把新元素写到 data[size]。当 size == capacity 时,原有内存已经没有空位,必须扩容后才能继续写入,否则会越界访问未分配的内存。

扩容并不是每插入一个元素就申请一次内存。常见策略是在容量耗尽时一次扩大到原来的两倍,例如从 2 变成 4,再从 4 变成 8。这样虽然单次扩容可能需要复制已有数据,但扩容发生的次数会明显减少。

实现自动扩容

下面给出一个可运行的顺序表示例。ensure_capacity 只在容量真正不足时调用 realloc,并先把返回值保存到临时指针中,避免扩容失败后丢失原来的内存地址。

c
#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;
}

预期输出

text
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 这样的方式增长。某一次扩容仍然需要处理已有元素,因此单次成本可能是 O(n)O(n);但多数插入不需要扩容,连续多次尾部插入的平均成本可以看作摊还 O(1)O(1)。

代价是扩容后会暂时存在未使用空间。例如从容量 8 扩到 16 后,如果只存了 9 个元素,就有 7 个位置暂时空闲。因此增长倍率越大,扩容次数通常越少,但可能预留更多暂时不用的内存。

扩容失败时怎样处理

realloc 可能因为内存不足而返回 NULL。不要直接写成 list->data = realloc(...),因为一旦失败,就会覆盖保存原内存地址的唯一指针,造成内存泄漏。

正确做法是先接收到临时指针,确认成功后再更新 data 和 capacity。同时,只有扩容成功才能继续执行插入;失败时应把错误传递给调用者,让上层决定退出、重试或采取其他处理方式。

顺序表自动扩容的核心并不是单纯调用一次 realloc,而是把容量检查、增长策略、失败保护和插入顺序组合起来:先保证空间足够,再写入元素,最后更新长度。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

容量不足时怎样扩容

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通