Lesson 45: realloc 动态扩容

练习任务

难度：中

实现安全的动态数组扩容程序：

用 malloc 分配初始容量为 2 的 int 数组
循环读入数字 — 容量不够复用 realloc 加倍扩容
每次扩容前后用 uintptr_t 保存地址数值，判断原地扩容还是异常搬迁
掌握 realloc 的安全用法：为什么 arr = realloc(arr, size) 是灾难

验证用例:
  输入 "1 2 3 4 5\n" → 展示扩容进程 + in-place/moved + expansions: 2 + values: 1 2 3 4 5
  输入 "10 20\n"     → 无扩容, values: 10 20

提示：realloc 可能返回原指针（堆后有连续空间），也可能返回新指针（堆后无空间→分配新块→memcpy 旧数据→free 旧块→返回调地址）。你无法控制，也不能假设。此外，如果 realloc 失败返回 NULL，而你写的是 arr = realloc(...)，arr 就被覆盖为 NULL——原内存再也找不到了。

核心知识点

realloc 的两种行为 — 原地扩容（堆后有连续空闲，直接扩展返回原指针）vs 异地搬迁（无连续空间→分配新块→memcpy→free 旧块→返回新地址）
致命陷阱 — arr = realloc(arr, size) 失败时返回 NULL → arr 被覆盖 → 原内存泄漏 + 数据丢失 + 悬垂指针（后续访问 arr[i] 段错误）
安全模式 — tmp = realloc(arr, size); if (tmp) arr = tmp; else { free(arr); /* 处理失败 */ }
倍增策略 = 摊还 O(1) — cap×2：总拷贝次数 ≈ 2n，平均每次插入 O(1)；+1 策略 = O(n²) — cap+1：总拷贝次数 ≈ n²/2，每次插入 O(n)
uintptr_t 规避 GCC14 -Wuse-after-free 误报 — realloc 成功后编译器可能误判原指针已被释放；将地址保存为整数值再做比较，绕过无根据的警告
堆碎片迫使搬移 — 即使堆的总空闲空间足够，若当前块后无连续大空间，realloc 也只能搬移（异地搬迁），留下碎片空洞
边缘行为 — realloc(NULL, size) ≡ malloc(size)（统一分配/扩容逻辑）；realloc(ptr, 0) ≡ free(ptr)（实现定义，避免依赖）
2× vs 1.5× 增长系数 — 2× 复制最少但碎片最多（释放的旧块永远不够下次申请）；1.5× 空间利用率更好（多次扩容后旧块可被复用）；std::vector / ArrayList 使用类似策略

代码框架

45_realloc.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char line[256];
    fgets(line, sizeof(line), stdin);
    int len = strlen(line);
    if (len > 0 && line[len - 1] == '\n') line[len - 1] = '\0';

    int cap = 2, size = 0, expansions = 0;
    int *arr = malloc(cap * sizeof(int));

#error TODO: Finish this exercise. Run "clings hint" for help.
    /* 用 strtok 遍历 line 中的数字：
     *   for each token:
     *     val = atoi(token)
     *
     *     if (size >= cap):   // 需要扩容
     *       cap *= 2
     *       保存旧地址（uintptr_t old = (uintptr_t)arr）
     *       安全 realloc: int *tmp = realloc(arr, cap*sizeof(int))
     *       if (tmp) {
     *         判断是否 moved: ((uintptr_t)tmp != old)
     *         打印扩容详情（#N: cap X -> Y [in-place]/[moved]）
     *         arr = tmp; expansions++
     *       } else {
     *         free(arr); return 1;  // realloc 失败
     *       }
     *
     *     arr[size++] = val */

    /* 打印总结 */
    printf("expansions: %d\n", expansions);
    printf("values:");
    for (int i = 0; i < size; i++) printf(" %d", arr[i]);
    printf("\n");
    free(arr);
    return 0;
}

框架中的核心问题：

为什么用 uintptr_t 保存旧地址的整数形式，而不是直接用 arr 比较？
为什么 cap *= 2 而不是 cap += 1？
扩容时为什么要用临时指针 tmp，不能直接 arr = realloc(arr, ...)？
realloc 失败后，原来的 arr 指向的内存还存在吗？

TIP

先不要往下翻看参考解答。把 safe realloc 的逻辑写出来——临时变量接收、判断成功/失败、打开扩容信息——这是本课的核心。特别注意 printf 的格式要严格匹配。

本课中 malloc 的用法可回看 Lesson 30: 单链表插入。

深度讲解

1. realloc 的两种行为：原地扩容 vs 异地搬迁

realloc 不是"在原内存后面接一段"那么简单。堆管理器根据当前块后的空闲空间决定两种策略：

1.1 原地扩容 [in-place] — 堆后有连续空闲空间

realloc(arr, 16) — 将 8 字节扩容到 16 字节：

  扩容前:                              扩容后:
  ┌── 原 8 字节 ──┬─── 空闲 ───┐       ┌─── 16 字节 ────────┬── 空闲 ──┐
  │ 1  2          │   free     │  →    │ 1  2  ?  ?         │  free    │
  └───────────────┴────────────┘       └────────────────────┴──────────┘
  ↑ arr                                ↑ tmp (= arr, 地址完全相同)

  条件: arr 后面的空闲空间 ≥ 16 - 8 = 8 字节
  结果: 返回原指针，原有数据不动，新增空间内容未初始化

1.2 异地搬迁 [moved] — 堆后无连续空间

realloc(arr, 16) — 将 8 字节扩容到 16 字节：

  扩容前:                              扩容后:
  ┌── 原 8 字节 ──┬── 占用(B) ─┐       ... ┌─── 16 字节 ────────┐ ...
  │ 1  2          │  B (8 字节) │           │ 1  2  ?  ?         │
  └───────────────┴─────────────┘           └────────────────────┘
  ↑ arr                                     ↑ tmp (新地址, ≠ arr!)

                          旧块已释放 [空洞]:
  ┌── 已释放 ──┬── 占用(B) ─┐
  │  (空洞)    │  B (8 字节) │  ← arr 指针已失效
  └────────────┴─────────────┘

  步骤:  1. 分配新 16 字节块
         2. memcpy 旧 8 字节到新块
         3. free 旧块
         4. 返回新块地址
  结果:  返回新指针，arr 失效

关键教训：调用者无法控制 realloc 的行为。写代码时，永远不要假设返回值等于原指针——即使 99 次都是原地，第 100 次也可能搬迁。

realloc 异地搬迁的内部搬家操作依赖底层内存拷贝——这正是 Lesson 26: my_memcpy 和 Lesson 27: my_memmove 所讲的内容。

2. 致命陷阱：`arr = realloc(arr, size)`

CAUTION

这是 C 语言动态内存管理中最隐蔽的陷阱之一。写法极其自然，后果极其严重。

2.1 灾难的完整过程

/* ❌ 看似自然的致命写法 */
int *arr = malloc(8 * sizeof(int));
// ... arr[0]=1, arr[1]=2, ...
arr = realloc(arr, 16 * sizeof(int));  // 试图扩容到 16 个 int
arr[2] = 3;  // ← 如果 realloc 失败，这里段错误！

假设 realloc 失败（如内存耗尽），事情的经过如下：

步骤 1: arr 指向有效内存
        ┌──────────────────────────┐
        │ 1  2  0  0  0  0  0  0   │  ← 8 个 int 的有效数据
        └──────────────────────────┘
        ↑ arr

步骤 2: realloc(arr, 64) 尝试扩容 → 失败！
        返回 NULL

步骤 3: arr = NULL  ← 灾难：
        ┌──────────────────────────┐
        │ 1  2  0  0  0  0  0  0   │  ← 这块内存还存在，但 arr 不指向它了！
        └──────────────────────────┘
        ↑ 无人指向 → 内存泄漏（永远无法 free）

步骤 4: arr[2] = 3  ← 空指针解引用 → SIGSEGV 段错误

三重灾难：

灾难	说明
内存泄漏	原内存的地址丢失，永远无法 `free`，程序运行越久泄漏越多
数据丢失	原数组中的所有数据（之前辛辛苦苦写入的值）都丢失了——arr 已不指向它们
段错误	后续 `arr[i]` 访问 → 解引用 NULL → SIGSEGV，程序崩溃

2.2 为什么这个陷阱特别隐蔽？

// 在实际开发中，这个 bug 可以潜伏很久才暴露：
int *buf = malloc(INITIAL_SIZE);
for (int i = 0; i < HUGE_COUNT; i++) {
    if (i >= current_size) {
        buf = realloc(buf, current_size * 2);  // ← 炸弹
        // 前 1000 次都成功 → 一切正常
        // 第 1001 次内存不足 → realloc 返回 NULL
        // buf = NULL → 之前 1000 个数据全部丢失 → 程序崩溃
    }
    buf[i] = process_item(i);
}

这个 bug 在开发环境（内存充足）可能永远不会触发，到了生产环境的高负载下才爆炸。

3. 安全模式：临时指针 + 成功判断

3.1 核心原则

永远用临时指针接收 realloc 的返回值，确认成功后再更新原指针。

/* ✅ 安全写入 — 两步走 */
int *tmp = realloc(arr, new_capacity * sizeof(int));
if (tmp) {
    arr = tmp;          // 成功 → 安全更新
} else {
    /* 失败：arr 仍然指向原内存，仍然有效！
       你可以选择：
       1. 继续使用当前大小
       2. 报告错误并释放已有数据
       3. 尝试更小规模的扩容
    */
    free(arr);
    fprintf(stderr, "realloc failed\n");
    return 1;
}

安全模式的两条路径：

  realloc 成功:
    realloc → tmp (有效地址)
    arr → (旧地址, 已失效)
    arr = tmp → arr 指向新地址 ✓

  realloc 失败:
    realloc → tmp (NULL)
    arr → (旧地址, 仍然有效！)  ← 这是关闭！
    free(arr) → 安全释放 → return 1

3.2 完整的安全扩容循环

int cap = 2, size = 0, expansions = 0;
int *arr = malloc(cap * sizeof(int));
if (arr == NULL) return 1;  // 初始分配也要检查

while (/* 还有数据 */) {
    int val = /* 读取下一个值 */;

    if (size >= cap) {
        int old_cap = cap;
        cap *= 2;

        // Step 1: 保存旧地址的数值（用于判断 in-place vs moved）
        uintptr_t old_addr = (uintptr_t)arr;

        // Step 2: 用临时指针接收
        int *tmp = realloc(arr, cap * sizeof(int));

        if (tmp) {
            // Step 3: 判断原地还是异地
            int moved = ((uintptr_t)tmp != old_addr);
            printf("#%d: cap %d -> %d %s\n",
                   expansions + 1, old_cap, cap,
                   moved ? "[moved]" : "[in-place]");

            // Step 4: 安全更新
            arr = tmp;
            expansions++;
        } else {
            // Step 5: 失败处理 — arr 仍然有效
            free(arr);
            fprintf(stderr, "realloc failed\n");
            return 1;
        }
    }

    arr[size++] = val;
}

IMPORTANT

注意 malloc 初始分配置要检查返回值！如果 malloc(2*sizeof(int)) 返回 NULL，后续的所有操作都会在空指针上进行。动态内存的每一次分配都必须检查。

4. 倍增策略与摊还分析

4.1 为什么不用 +1 策略？

策略: capacity += 1 (每次扩容增加 1)
插入 n 个元素的过程:

  元素  容量变化     本次拷贝次数    累计拷贝次数
  1     cap=2        0              0
  2     cap=2        0              0
  3     cap=3        2              2
  4     cap=4        3              5
  5     cap=5        4              9
  ...   ...          ...            ...
  n     cap=n        n-1            0+0+2+3+...+(n-1) ≈ n²/2

总拷贝次数 ≈ n²/2 → 均摊每次插入 O(n) → 插入 n 个元素 O(n²)

策略: capacity *= 2 (倍增策略)
插入 n=16 个元素的过程:

  元素  容量优化     本次拷贝次数    说明
  1-2   cap=2        0              初始容量就够了
  3     cap=2→4      2              拷贝 2 个元素
  4     cap=4        0              无需扩容
  5     cap=4→8      4              拷贝 4 个元素
  6-8   cap=8        0              无需扩容
  9     cap=8→16     8              拷贝 8 个元素
  10-16 cap=16       0              无需扩容

  总拷贝 = 2 + 4 + 8 = 14  ← 约等于 n (而非 n²)

4.2 摊还 O(1) 的数学证明

假设从容量 1 开始倍增，插入 N 个元素：

  扩容次数 k = ⌈log₂ N⌉
  第 i 次扩容拷贝 2ⁱ 个元素
  总拷贝 = 1 + 2 + 4 + ... + N/2 + N
         = N + N/2 + N/4 + ... + 1
         ≈ 2N

  均摊每次插入的拷贝次数 ≤ 2N / N = 2 → O(1)

等比数列求和: N + N/2 + N/4 + ... ≈ 2N

  N:     ████████████████████████████████  32
  N/2:   ████████████████                  16
  N/4:   ████████                           8
  N/8:   ████                              4
  N/16:  ██                                2
  N/32:  █                                 1
        ────────────────────────────────
  Sum:  ████████████████████████████████████████████████████████████████  63
        ≈ 2N = 64

这就是算法分析中的经典结论：倍增数组的均摊插入时间为 O(1)。

4.3 类比：std::vector 和 ArrayList

这不是 C 语言的独特技巧——几乎所有主流语言的动态数组都使用倍增策略：

语言/库	类型	增长策略
C++	`std::vector`	2×（MSVC：1.5×）
Java	`ArrayList`	1.5×
Python	`list`	≈1.125×（逐步递增）
Rust	`Vec`	2×
Go	`slice`（append）	2×（小容量 N×1.25，大容量 N×1.63）

5. `uintptr_t` 规避 GCC14 `-Wuse-after-free` 误报

5.1 问题：编译器"误报"

GCC 14+ 在 -Wall 下会对 realloc 后的原指针比较发出 -Wuse-after-free 警告：

int *tmp = realloc(arr, new_size);
if (tmp != arr) {          // ← GCC14: warning: 'arr' used after 'realloc'
    printf("moved\n");
}

编译器分析道："realloc 可能 free 了原指针→arr 可能已失效→后面的比较使用了 arr→警告！" 即使 realloc 成...返回了原指针（原地扩容），编译器也可能无法区分这一情况，产生误报。

5.2 绕过方法：保存数值而非指针

#include <stdint.h>

uintptr_t old_addr = (uintptr_t)arr;        // 保存地址的整数值
int *tmp = realloc(arr, new_capacity * sizeof(int));

if (tmp) {
    int moved = ((uintptr_t)tmp != old_addr);  // 比较整数值，无警告
    printf("realloc: cap %d -> %d %s\n",
           old_cap, new_cap, moved ? "[moved]" : "[in-place]");
    arr = tmp;
}

uintptr_t 是 C99 引入的整数类型（<stdint.h>），保证能容纳任意指针值。将指针强转为 uintptr_t 后，它就是一个普通整数——编译器不会对整数比较发出 use-after-free 警告。

为什么这是"安全的绕过"？

  uintptr_t old_addr = (uintptr_t)arr;
  │                     │
  │                     └── 将指针值（地址）转为整数
  └── old_addr 只是数字，如 0x7fff1234
      │
      数字不会"失效"——它永远是 0x7fff1234
      即使 arr 指向的内存被释放，这个数字依然可用

  (uintptr_t)tmp != old_addr  ← 纯整数比较，编译器不介入

NOTE

这是一种绕过编译器保守分析的技术手段。真正需要注意的编写规范是：realloc 成功后不应该再通过旧指针访问数据——即使地址相同，也应该通过新指针 tmp 来访问。

6. 堆碎片：即使总空闲足够，realloc 也可能搬移

6.1 碎片的来源

堆管理器（malloc/realloc/free）并不整理内存碎片——多次交错分配和释放后，堆中可能散布大量不连续的小空洞：

堆内存布局（经历过多次 malloc/free 后）：

  ┌── A(16B) ──┬── 空间(8B) ──┬── B(32B) ──┬── 空洞(16B) ──┬── C(64B) ──┐
  │ 占用        │  空闲但不可用  │  占用       │  空闲但不可用  │  占用       │
  └────────────┴───────────────┴────────────┴────────────────┴────────────┘

  总空闲 = 8 + 16 = 24 字节 ✓ 足够
  但都是不连续小块 → realloc(A, 32) 无法原地扩展 → 必须搬移！

6.2 碎片迫使搬移的完整过程

realloc(A, 32) — A 后只有 8 字节空洞，不够扩展 16 字节：

  步骤 1: 发现 A 后无连续的 16 字节空闲
          → 选择异地搬迁

  步骤 2: 在堆的别处分配 32 字节新块
          ┌─────────── 新块(32B) ───────────┐
          │  A 的旧数据 + 新增空间             │
          └──────────────────────────────────┘
          ↑ tmp (新地址)

  步骤 3: memcpy(A → tmp, 16)
          free(A) → A 位置变成新空洞(16B)

  堆变成了:
  ┌── 空洞(16B) ─┬── 空洞(8B) ──┬── B(32B) ──┬── 空间(16B) ──┬── C(64B) ─┐
  │  A 旧址      │  旧空洞       │  占用       │  旧空洞       │  占用      │
  └──────────────┴───────────────┴────────────┴────────────────┴───────────┘
                ... ┌─── 新 A(32B) ───────┐ ...
                    │  数据已搬移           │
                    └──────────────────────┘

  注...：A 旧址和旧空洞合并成一个更大的空洞(24B)，但已经晚了

IMPORTANT

这就是为什么即使系统显示有大量空闲内存，realloc 仍可能返回新地址——空闲内存不连续。现代分配器（如 jemalloc, tcmalloc）通过分层策略（tcache/slab/large）缓解碎片问题，但不能完全消除。

7. realloc 的边缘行为

7.1 `realloc(NULL, size)` ≡ `malloc(size)`

// 这两行等价：
int *p1 = malloc(16);
int *p2 = realloc(NULL, 16);

这个特性允许用统一逻辑处理初始化和扩容：

// 无需区分"首次分配"和"扩容"：
int *dynamic_array = NULL;
size_t cap = 0, size = 0;

void push_back(int val) {
    if (size >= cap) {
        cap = (cap == 0) ? 2 : cap * 2;
        dynamic_array = realloc(dynamic_array, cap * sizeof(int));
        // realloc(NULL, ...) 等价于 malloc，无需特殊处理 ✓
    }
    dynamic_array[size++] = val;
}

7.2 `realloc(ptr, 0)` — 实现定义的行为

realloc(ptr, 0);  // ← 行为不确定，避免使用！

C 标准规定 realloc(ptr, 0) 是实现定义（implementation-defined）：

某些实现等价于 free(ptr)，返回 NULL
某些实现等价于 malloc(0)，返回一个小块或 NULL

因此：

/* ❌ 不可移植 —— 重要这样写 */
int *p = malloc(100);
p = realloc(p, 0);   // 可能返回 NULL 也可能返回非 NULL

/* ✅ 明确释放 */
free(p);
p = NULL;

8. 2× vs 1.5× — 增长系数的工程选择

8.1 2× 的优势与弊端

2 倍增长的优点是拷贝次数最少（摊还 O(1) 的常数最小）。但它有一个致命问题——释放的所有旧块永远无法被后续扩容复用。

从容量 8 开始 2× 增长:

  cap=8  → 释放 8  → 申请 16  → 空洞 8  (不够 16)
  cap=16 → 释放 16 → 申请 32  → 空洞 16 (不够 32)
  cap=32 → 释放 32 → 申请 64  → 空洞 32 (不够 64)

  累积空洞总和 = 8+16+32 = 56
  但每次当前请求都是 2×，永远大于之前释放的任何单块
  → 所有旧块都变成永久碎片！

2× 增长: 旧块无法复用

  释放:  ████ (8B)     → 空洞
  申请:  ████████████ (16B)  > 8B → 无法填入旧空洞
  释放:  ████████████ (16B)
  申请:  ████████████████████████ (32B) > 16B → 无法填入旧空洞
  ...
  所有旧块都是碎片，新块总是新分配

8.2 1.5× 为什么能复用旧块

从容量 8 开始 1.5× 增长:

  cap=8  → 释放 8  → 申请 12  → 空洞 8
  cap=12 → 释放 12 → 申请 18  → 空洞 12
  cap=18 → 释放 18 → 申请 27  → 空洞 18
  cap=27 → 释放 27 → 申请 40  → 空洞 27

更准确的分析——考虑多次扩容后旧空洞的累积效应：

假设从容量 C 开始，1.5× 增长：

  cap 序列: C, 1.5C, 2.25C, 3.375C, 5.0625C, ...

  第 k 次扩容后，释放的空洞大小 = 1.5ᵏ⁻¹·C
  第 k+1 次请求大小 = 1.5ᵏ·C

  之前所有空洞的总和:
  S = C + 1.5C + 2.25C + ... + 1.5ᵏ⁻²·C
    = C · (1.5ᵏ⁻¹ - 1) / (1.5 - 1)
    = C · (1.5ᵏ⁻¹ - 1) / 0.5
    = 2C · (1.5ᵏ⁻¹ - 1)

  比较: 总空洞 S vs 下次请求 1.5ᵏ·C
  S > 1.5ᵏ·C  ⇔  2·(1.5ᵏ⁻¹ - 1) > 1.5ᵏ
              ⇔  2·1.5ᵏ⁻¹ - 2 > 1.5·1.5ᵏ⁻¹
              ⇔  0.5·1.5ᵏ⁻¹ > 2
              ⇔  1.5ᵏ⁻¹ > 4
              ⇔  k-1 > log₁.₅4 ≈ 3.4
              ⇔  k > 4.4

  结论: 从第 5 次扩容开始，累积空洞总和 > 下次请求大小
        → 旧块可以之后续请求复用！

1.5× 增长: 旧块可被复用

  cap 序列: 8 → 12 → 18 → 27 → 40 → 60

  释放...空洞: 8, 12, 18, 27, 40
  第 5 次扩容请求 40B 时:
    空洞总和 = 8+12+18+27 = 65 > 40
    → 可以在旧空洞中找到空间，而不是在堆末尾新分配 ✓

8.3 现实世界的选择

实现	增长系数	原因
GNU libstdc++ (GCC)	2×	简单快速，多数场景足够
MSVC std::vector	1.5×	空间利用率更好
Facebook folly::FBVector	1.5×	内存效率优先
OpenJDK ArrayList	1.5×	平衡性能与空间

选择建议：

教学/简单项目：2×——代码最简洁，理解最容易
内存受限环境...1.5×——降低碎片，提高空间利用率
极致性能：2×——拷贝参数最少

参考解答

练习: realloc 安全扩容完整实现

solution_45_realloc.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char line[256];
    fgets(line, sizeof(line), stdin);
    int len = strlen(line);
    if (len > 0 && line[len - 1] == '\n') line[len - 1] = '\0';

    int cap = 2, size = 0, expansions = 0;
    int *arr = malloc(cap * sizeof(int));
    if (arr == NULL) {
        fprintf(stderr, "initial malloc failed\n");
        return 1;
    }

    char *token = strtok(line, " ");
    while (token != NULL) {
        int val = atoi(token);

        if (size >= cap) {
            int old_cap = cap;
            cap *= 2;  /* 倍增策略 */

            uintptr_t old_addr = (uintptr_t)arr;
            int *tmp = realloc(arr, cap * sizeof(int));

            if (tmp) {
                int moved = ((uintptr_t)tmp != old_addr);
                printf("#%d: cap %d -> %d %s\n",
                       expansions + 1, old_cap, cap,
                       moved ? "[moved]" : "[in-place]");
                arr = tmp;
                expansions++;
            } else {
                free(arr);  /* arr 仍然有效，安全释放 */
                fprintf(stderr, "realloc failed\n");
                return 1;
            }
        }

        arr[size++] = val;
        token = strtok(NULL, " ");
    }

    printf("expansions: %d\n", expansions);
    printf("values:");
    for (int i = 0; i < size; i++) printf(" %d", arr[i]);
    printf("\n");
    free(arr);
    return 0;
}

核心设计决策：

安全 realloc：用 tmp 接收返回值，成功才更新 arr，失败时 arr 依然指向原有效内存
uintptr_t：保存旧地址为整数值再做比较，绕过 GCC14 -Wuse-after-free 误报
*cap = 2：倍增策...，摊还 O(1) 插入时间复杂度
初始 malloc 检查：arr == NULL 时直接返回，不制造后续空指针操作
扩容计数器：expansions 准确反映扩容次数，用于输出验证

对照检查：realloc 返回值用了临时变量吗？扩容后更新了 cap 吗？打印格式是 #N: cap X -> Y [in-place] 吗？realloc 失败时释放了原指针吗？

课堂讨论

如果 realloc 扩容时恰好是原地扩容（返回值等于原指针），那 old_addr 和 (uintptr_t)tmp 相等吗？为什么？
为什么 C++ 的 std::vector 扩容时不直接用 realloc，而是 new+搬移构造+delete？
假设你的程序在 32 位系统上运行，最大能用多少内存？realloc 在接近上限时应该如何设计防御？
用 uintptr_t 保存地址比较的做法，能否用在判断"两个指针是否指向同一块 malloc 分配的内存"上？
如果 realloc(ptr, 0) 在某平台返回了非 NULL 的小块，而你写了 ptr = realloc(ptr, 0); if (ptr == NULL) 想检测"已释放"，会发生什么？
2× 增长中，假设从 cap=16 开始被 5 次扩容释放的空洞依次是 16、32、64、128、256。这些空洞能合并成一个连续的大块吗？如果不合并，下一次请求 512 能用上它们吗？

讨论答案

Q1: 原地扩容时 old_addr 和 (uintptr_t)tmp 相等吗？

相等。 原地扩容意味着 realloc 直接在当前块后面扩展——不分配新块、不 memcpy、不释放旧块。返回值就是原指针。(uintptr_t)tmp 就是原来地址的整数值，moved 为 0，输出 [in-place]。

注意：即使相等，也应该通过 tmp（新指针变量）访问数组，而不是继续使用 arr——这是防御性编程的良好习惯。

Q2: 为什么 std::vector 不用 realloc？

C++ 对象有构造函数和析构函数，realloc 只做原始内存搬运。

realloc 内部用 memcpy（或类似机制）搬运字节——不调用拷贝构造函数、不调用析构函数。对于 C++ 对象：

cpp

std::vector<std::string> v;
// realloc 会做: 把 std::string 的内存逐字节拷贝到新位置
// 问题: std::string 内部有指针指向堆上的字符数据
//       逐字节拷贝 → 新旧两个 std::string 的 data 指针指向同一块堆内存
//       旧 std::string 没有被析构 → 堆内存泄漏
//       两个 std::string 共享堆内存 → 一个一个被析构，另一个悬垂

C++ 必须用 new 分配新空间→搬移构造（std::move）→析构旧对象→delete 旧空间。C 的原始类型（int、char、指针等）没有构造/析构，所以 realloc 对 C 是完美适配的。

Q3: 32 位系统的内存上限与防御策略

32 位系统进程地址空间约 4GB，但用户空间通常只有 2-3GB。

realloc 接近上限时的防御策略：

分级降级：先尝试 2× 扩容→失败则 1.5×→失败则 1.2×→失败则报错
检查返回值：永远是第一道防线——if (tmp == NULL) 后安全退出
预分配上限...设置 MAX_CAPACITY，避免无限制增长
使用磁盘缓存：超大数据集用内存映射文件（mmap）代替纯内存

#define MAX_CAPACITY (256 * 1024 * 1024 / sizeof(int))  // 约 256MB

if (cap < MAX_CAPACITY) {
    cap *= 2;
} else {
    fprintf(stderr, "capacity limit reached\n");
    break;
}

Q4: uintptr_t 能否判断两个指针是否指向同一块内存？

不能直接判断。 uintptr_t 比较的是地址的数值，两个指针数值相同说明它们指向同一地址——这只能判断"是否指向同一位置"，不能判断"是否由同一次 malloc 分配"。

int *a = malloc(100);
int *b = a + 50;   // b 指向 a 内部的偏移位置
// (uintptr_t)a != (uintptr_t)b  → 数值不等
// 但 b 确实在 a 分配的内存内部！

判断"是否在同一个分配块内"需要堆管理器的元数据（glibc 内部用 malloc_usable_size 或跟踪 chunk 边界）——这些都是平台相关、不可移植的操作。

Q5: realloc(ptr, 0) 返回非 NULL 的隐患

会导致悬垂指针判断失败。

int *p = malloc(100);
p = realloc(p, 0);
// 如果平台行为是: free(p) 且返回非 NULL 的小块
// → p != NULL → 你以为内存还在 → deref p → UB!

正确做法：

/* 明确释放，不依赖 realloc(ptr, 0) */
free(p);
p = NULL;

Q6: 2× 空洞能否满足下次请求？

不能合并，也不能满足。 释放的空洞 16+32+64+128+256 = 496 字节，但每个空洞是分散的——它们之间被其他分配块隔开。堆管理器不会自动移动已分配的数据来整理碎片（那样会改变指针，破坏程序逻辑）。下一次请求 512 字节时，任何单块空洞最大只有 256，都不够用——分配器只能在堆末尾另找地方。

这就是 2× 增长导致碎片问题的数学本质：每个释放的旧块严格小于下次请求的新块，形成递增的空洞链，永远无法被复用。

课后练习

实现简单的动态数组库。仿照 C++ std::vector 的核心接口，实现：

typedef struct { int *data; size_t size; size_t cap; } Vector;
void vec_init(Vector *v);
void vec_push_back(Vector *v, int val);
int  vec_at(Vector *v, size_t i);
void vec_free(Vector *v);

vec_init 初始容量为 2，vec_push_back 用安全 realloc + 2× 策略扩容。

知识点提示：注意 realloc 的安全模式——tmp = realloc(v->data, ...); if (tmp) v->data = tmp;。vec_free 不要忘记 free(v->data) 并把指针置 NULL。

参考解答

vector.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int *data;
    size_t size;
    size_t cap;
} Vector;

void vec_init(Vector *v) {
    v->cap = 2;
    v->size = 0;
    v->data = malloc(v->cap * sizeof(int));
    if (v->data == NULL) { v->cap = 0; return; }
}

void vec_push_back(Vector *v, int val) {
    if (v->size >= v->cap) {
        size_t new_cap = v->cap * 2;
        int *tmp = realloc(v->data, new_cap * sizeof(int));
        if (tmp) {
            v->data = tmp;
            v->cap = new_cap;
        } else {
            fprintf(stderr, "realloc failed\n");
            return;  /* 不更新 size，调用者可检查 */
        }
    }
    v->data[v->size++] = val;
}

int vec_at(Vector *v, size_t i) {
    return v->data[i];
}

void vec_free(Vector *v) {
    free(v->data);
    v->data = NULL;
    v->size = v->cap = 0;
}

int main(void) {
    Vector v;
    vec_init(&v);
    for (int i = 1; i <= 10; i++)
        vec_push_back(&v, i * 10);
    for (size_t i = 0; i < v.size; i++)
        printf("%d ", vec_at(&v, i));
    printf("\n");
    vec_free(&v);
    return 0;
}

比较 2× 和 1.5× 策略的拷贝次数。编写程序分别用 2× 和 1.5× 策略插入 1000 个元素，统计各自的总拷贝次数（不实际分配，只模拟计数）。

知识点提示：用循环模拟扩容过程——每次 size == capacity 时，累加 total_copies += size，然后 capacity *= factor。1.5× 策略需要把 capacity 设为整数（(capacity * 3) / 2 或 capacity + (capacity >> 1)）。

参考解答

growth_compare.c

#include <stdio.h>

int count_copies(int n, double factor) {
    int cap = 2, total = 0;
    for (int i = 0; i < n; i++) {
        if (i >= cap) {
            total += cap;  /* 拷贝 cap 个元素 */
            cap = (int)(cap * factor);
            if (cap < 2) cap = 2;
        }
    }
    return total;
}

int main(void) {
    int n = 1000;
    int copies_2x   = count_copies(n, 2.0);
    int copies_15x  = count_copies(n, 1.5);

    printf("Inserting %d elements:\n", n);
    printf("  2.0x strategy: %d copies (%.2f per insert)\n",
           copies_2x, (double)copies_2x / n);
    printf("  1.5x strategy: %d copies (%.2f per insert)\n",
           copies_15x, (double)copies_15x / n);
    return 0;
}

典型输出对比：

2×：约 1000 次拷贝（≈1.0/插入）
1.5×：约 1500 次拷贝（≈1.5/插入）
两者都是 O(n) 总拷贝，远优于 +1 策略的 O(n²)

追踪堆内存布局。在每次 malloc/realloc/free 后打印当前地址，观察原地与搬移的发生时机。连续分配多个不同大小的块，然后对中间某个块做 realloc 扩容，观察它是否搬移。
知识点提示：先用 malloc 分配 3 个块（如 16B、32B、16B），然后命中间块 realloc 到 64B——由于后面紧挨着第 3 个块，几乎必然导致搬移。打印三个块的地址变化，验证堆碎片迫使搬移的结论。
阅读 glibc 的 realloc 实现。在 glibc 源码 malloc/malloc.c 中搜索 __libc_realloc 函数，理解它如何判断"原地扩容还是异地搬迁"——关键检查是 old_size 和后继 chunk 的状态。
知识点提示：glibc 用 chunk 元数据（前一个 chunk 的 size 域、当前 chunk 的 prev_size 域）和 top chunk 边界来判断是否有足够连续空间。如果后续 chunk 是 top chunk（堆末尾），可以直接扩展；否则需要检查后续 chunk 是否空闲且足够大。
使用 Valgrind 检测内存泄漏。用 arr = realloc(arr, size)（故意错误）编写一个测试程序，在 Valgrind 下运行，观察 Valgrind 是否能检测到"失败时内存泄漏"的 bug。
知识点提示：用 valgrind --leak-check=full ./your_program 运行。如果 realloc 在分配巨大容量时失败（用系统 ulimit -v 限制虚拟内存来强制失败），Valgrind 会报告"definitely lost"——即原 arr 指向的内存已无法释放。然后再用安全模式重写，确认 Valgrind 报告 clean。

参考资料

man realloc — Linux 手册页，查看标准库 realloc 的函数签名、返回值和错误行为
C 标准 §7.22.3.5 — realloc 函数的正式规范（C11 起为 §7.22.3.5）
glibc malloc/malloc.c — __libc_realloc — 工业级实现，理解 chunk 合并、top chunk 扩展、mmap 映射等决策逻辑
Facebook folly::FBVector — 1.5× 扩容策略的设计文档，讨论内存效率和性能的权衡
Wilson et al. (1995) "Dynamic Storage Allocation: A Survey and Critical Review" — 内存分配器的经典综述，涵盖碎片、策略和性能模型

"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies." — C.A.R. Hoare

Lesson 45: realloc 动态扩容 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. realloc 的两种行为：原地扩容 vs 异地搬迁 ​

1.1 原地扩容 [in-place] — 堆后有连续空闲空间 ​

1.2 异地搬迁 [moved] — 堆后无连续空间 ​

2. 致命陷阱：arr = realloc(arr, size) ​

2.1 灾难的完整过程 ​

2.2 为什么这个陷阱特别隐蔽？ ​

3. 安全模式：临时指针 + 成功判断 ​

3.1 核心原则 ​

3.2 完整的安全扩容循环 ​

4. 倍增策略与摊还分析 ​

4.1 为什么不用 +1 策略？ ​

4.2 摊还 O(1) 的数学证明 ​

4.3 类比：std::vector 和 ArrayList ​

5. uintptr_t 规避 GCC14 -Wuse-after-free 误报 ​

5.1 问题：编译器"误报" ​

5.2 绕过方法：保存数值而非指针 ​

6. 堆碎片：即使总空闲足够，realloc 也可能搬移 ​

6.1 碎片的来源 ​

6.2 碎片迫使搬移的完整过程 ​

7. realloc 的边缘行为 ​

7.1 realloc(NULL, size) ≡ malloc(size) ​

7.2 realloc(ptr, 0) — 实现定义的行为 ​

8. 2× vs 1.5× — 增长系数的工程选择 ​

8.1 2× 的优势与弊端 ​

8.2 1.5× 为什么能复用旧块 ​

8.3 现实世界的选择 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 45: realloc 动态扩容

练习任务

核心知识点

代码框架

深度讲解

1. realloc 的两种行为：原地扩容 vs 异地搬迁

1.1 原地扩容 [in-place] — 堆后有连续空闲空间

1.2 异地搬迁 [moved] — 堆后无连续空间

2. 致命陷阱：`arr = realloc(arr, size)`

2.1 灾难的完整过程

2.2 为什么这个陷阱特别隐蔽？

3. 安全模式：临时指针 + 成功判断

3.1 核心原则

3.2 完整的安全扩容循环

4. 倍增策略与摊还分析

4.1 为什么不用 +1 策略？

4.2 摊还 O(1) 的数学证明

4.3 类比：std::vector 和 ArrayList

5. `uintptr_t` 规避 GCC14 `-Wuse-after-free` 误报

5.1 问题：编译器"误报"

5.2 绕过方法：保存数值而非指针

6. 堆碎片：即使总空闲足够，realloc 也可能搬移

6.1 碎片的来源

6.2 碎片迫使搬移的完整过程

7. realloc 的边缘行为

7.1 `realloc(NULL, size)` ≡ `malloc(size)`

7.2 `realloc(ptr, 0)` — 实现定义的行为

8. 2× vs 1.5× — 增长系数的工程选择

8.1 2× 的优势与弊端

8.2 1.5× 为什么能复用旧块

8.3 现实世界的选择

参考解答

课堂讨论

讨论答案

课后练习

参考资料