会长大的数组

第 22 课，共 30 课 · 第 4 部分 · 内存 · 约 15 分钟

用 malloc 要内存时，得说好要多少。可很多时候一开始根本不知道：一天会来几个订单、一个文件里有几行。这一课做一个会长大的数组：放满了，就换一块更大的。换块用的是 realloc：

main.c

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int *scores = malloc(2 * sizeof(int));6    if (scores == NULL) {7        return 1;8    }9    scores[0] = 78;10    scores[1] = 85;11    int *bigger = realloc(scores, 4 * sizeof(int));12    if (bigger == NULL) {13        free(scores);14        return 1;15    }16    scores = bigger;17    scores[2] = 90;18    scores[3] = 66;19    printf("%d %d %d %d\n", scores[0], scores[1], scores[2], scores[3]);20    free(scores);21    return 0;22}

输出

78 85 90 66

realloc(旧指针, 新的字节数) 给你一块新大小的内存，原来的内容原样搬过去，返回新块的地址。原来的 78 和 85 还在，后面多出了两格可以用。

realloc 做了什么

点单步，走过第 11 行：堆上多了一个「16 字节 · 第 11 行」的块，里面是 78 和 85，后两格还空着；旧的「8 字节」块变成了灰色的「已释放」。realloc 做的就是这三件事：要一块新的、把旧的内容复制过去、把旧的还掉。

在这个页面上，realloc 每次都是这样搬家。真的 C 里，如果旧块后面正好空着，它可能就地把块变大，地址不变。你不知道它会怎么做，所以：

只用 realloc 返回的地址，别再用旧指针；
旧块已经被 realloc 还掉了，不要再 free 它，最后只 free 新的。

main.c

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int *old = malloc(2 * sizeof(int));6    old[0] = 78;7    old[1] = 85;8    int *scores = realloc(old, 4 * sizeof(int));9    printf("%d\n", old[0]);10    free(scores);11    return 0;12}

输出

heap-use-after-free

发生了什么： 停在第 9 行：这块内存已经 free 了（还回去了），不能再用。

第 9 行还在用 old，可它指着的块已经被 realloc 还掉了。我们的引擎在这里停下，和上一课「还了还在用」一样。真的 C 里，要是块碰巧是就地变大的，这一行看起来没事，换一台电脑或者多放几个数就出事了：这种错最难找。点「看看是怎么出错的」，看 old 的红色虚线箭头。

先存进另一个指针

上面的程序没有写 scores = realloc(scores, ...)，而是先存进 bigger。原因是：要不到内存时，realloc 返回 NULL，而旧块还在、没有还。要是直接写

1scores = realloc(scores, 4 * sizeof(int));

一失败，scores 就变成了 NULL，旧块再也找不到了：不但数据没了，还泄漏了一块内存。所以总是这样写：

1int *bigger = realloc(scores, 4 * sizeof(int));2if (bigger == NULL) {3    // scores 还能用；不要了就 free(scores)4}5scores = bigger;

小技巧： realloc(NULL, n) 和 malloc(n) 一样。所以有人一开始把指针设成 NULL，第一次也用 realloc 来要。

长度和容量

每放一个数就 realloc 一次太费事了。会长大的数组记着两个数：

	意思	变量
长度	现在放了几个	`count`
容量	这块内存一共能放几个	`capacity`

放之前先看一眼：count 和 capacity 一样大，说明满了，就把容量翻一倍；没满就直接放。下面一天放一个步数，放 6 天：

main.c

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int capacity = 2;6    int count = 0;7    int *steps = malloc(capacity * sizeof(int));8    if (steps == NULL) {9        return 1;10    }11    for (int day = 1; day <= 6; day++) {12        if (count == capacity) {13            int *bigger = realloc(steps, capacity * 2 * sizeof(int));14            if (bigger == NULL) {15                free(steps);16                return 1;17            }18            steps = bigger;19            capacity *= 2;20            printf("满了，容量变成 %d\n", capacity);21        }22        steps[count] = day * 1000;23        count++;24    }25    printf("长度 %d，容量 %d\n", count, capacity);26    free(steps);27    return 0;28}

输出

满了，容量变成 4
满了，容量变成 8
长度 6，容量 8

点单步，盯着堆：先是「8 字节」的块，放到第 3 个时换成「16 字节」，放到第 5 个时换成「32 字节」，旧块一个个变灰。最后长度是 6、容量是 8，有两格空着，等着下一个数。程序结束时只有最后那块是活的，被 free 还掉了。

为什么要翻倍

每次只多要一格行不行？行，可是太慢。每次 realloc 搬家，都要把已有的数全部复制一遍。数一数放 1000 个数要搬几次、一共复制多少个：

main.c

1#include <stdio.h>2 3int main(void) {4    int moves_one = 0;5    int copied_one = 0;6    int moves_double = 0;7    int copied_double = 0;8    int cap_one = 1;9    int cap_double = 1;10    for (int count = 1; count <= 1000; count++) {11        if (count > cap_one) {12            copied_one += cap_one;13            cap_one += 1;14            moves_one++;15        }16        if (count > cap_double) {17            copied_double += cap_double;18            cap_double *= 2;19            moves_double++;20        }21    }22    printf("每次加 1：搬 %d 次，复制 %d 个\n", moves_one, copied_one);23    printf("每次翻倍：搬 %d 次，复制 %d 个\n", moves_double, copied_double);24    return 0;25}

输出

每次加 1：搬 999 次，复制 499500 个
每次翻倍：搬 10 次，复制 1023 个

这段程序没有真的要内存，只是把两种做法各自要搬几次算出来。差别很大：每次加 1 要搬 999 次、复制将近 50 万个数；翻倍只搬 10 次、复制 1023 个。数越多，差得越多。代价是最多会空着将近一半的格子，一般来说很划算。

先猜一猜

容量从 1 开始，满了就翻倍，放进 10 个数。这段程序显示什么？

1#include <stdio.h>2 3int main(void) {4    int capacity = 1;5    int moves = 0;6    for (int count = 1; count <= 10; count++) {7        if (count > capacity) {8            capacity *= 2;9            moves++;10        }11    }12    printf("%d %d\n", moves, capacity);13    return 0;14}

输出

写成函数

每次放数都写一遍 if 和 realloc 太长了，把它写成函数 push。它要改 main 里的长度和容量，所以这两个传地址（第 16 课）；块可能搬家，所以把（可能是新的）地址返回来：

main.c

1#include <stdio.h>2#include <stdlib.h>3 4int *push(int *items, int *count, int *capacity, int value) {5    if (*count == *capacity) {6        int *bigger = realloc(items, *capacity * 2 * sizeof(int));7        if (bigger == NULL) {8            return items;9        }10        items = bigger;11        *capacity *= 2;12    }13    items[*count] = value;14    *count += 1;15    return items;16}17 18int main(void) {19    int prices[5] = {12, 8, 25, 4, 30};20    int count = 0;21    int capacity = 1;22    int *list = malloc(capacity * sizeof(int));23    if (list == NULL) {24        return 1;25    }26    for (int i = 0; i < 5; i++) {27        list = push(list, &count, &capacity, prices[i]);28    }29    for (int i = 0; i < count; i++) {30        printf("%d ", list[i]);31    }32    printf("\n长度 %d，容量 %d\n", count, capacity);33    free(list);34    return 0;35}

输出

12 8 25 4 30 
长度 5，容量 8

点单步，进到 push 里看：它的框里 count 和 capacity 两根箭头指回 main 框里的变量，items 指着堆上的块。要不到内存时，push 什么也不放，把原来的地址原样还回去，main 的 list 不会丢。

*count += 1 不要写成 *count++：++ 比 * 先算，那样加的是指针本身，不是它指着的数。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。

练习 1

再加两个

scores 现在能放 3 个分数。用 realloc 把它变成能放 5 个（先存进另一个指针，检查 NULL），放进 70 和 95，显示 88 76 91 70 95。

要显示

88 76 91 70 95

exercise1.c

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int *scores = malloc(3 * sizeof(int));6    if (scores == NULL) {7        return 1;8    }9    scores[0] = 88;10    scores[1] = 76;11    scores[2] = 91;12 13    for (int i = 0; i < 5; i++) {14        printf("%d ", scores[i]);15    }16    printf("\n");17    free(scores);18    return 0;19}

输出

点「运行」或按 Ctrl+Enter

练习 2

只留偶数

把 numbers 里的偶数一个个放进会长大的数组 evens（容量从 2 开始，满了翻倍），最后显示放进去的数，再显示 长度 5，容量 8。

要显示

8 6 4 10 2 
长度 5，容量 8

exercise2.c

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int numbers[8] = {3, 8, 6, 1, 4, 10, 7, 2};6    int count = 0;7    int capacity = 2;8    int *evens = malloc(capacity * sizeof(int));9    if (evens == NULL) {10        return 1;11    }12 13    for (int i = 0; i < count; i++) {14        printf("%d ", evens[i]);15    }16    printf("\n长度 %d，容量 %d\n", count, capacity);17    free(evens);18    return 0;19}

输出

点「运行」或按 Ctrl+Enter

练习 3

修好它

这个会长大的数组放到第 3 个数就越界了。找出判断「满了」那一行的错，改好它，让程序显示 5 9 2 7 ，然后换行。

要显示

5 9 2 7

exercise3.c

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int values[4] = {5, 9, 2, 7};6    int count = 0;7    int capacity = 2;8    int *list = malloc(capacity * sizeof(int));9    if (list == NULL) {10        return 1;11    }12    for (int i = 0; i < 4; i++) {13        if (count > capacity) {14            int *bigger = realloc(list, capacity * 2 * sizeof(int));15            if (bigger == NULL) {16                free(list);17                return 1;18            }19            list = bigger;20            capacity *= 2;21        }22        list[count] = values[i];23        count++;24    }25    for (int i = 0; i < count; i++) {26        printf("%d ", list[i]);27    }28    printf("\n");29    free(list);30    return 0;31}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

realloc(p, 新字节数) 换一块新大小的内存，原来的内容搬过去，返回新地址；之后只用新地址。
先存进另一个指针再检查 NULL：失败时旧块还在，直接写 p = realloc(p, ...) 会把它丢掉。
会长大的数组记着长度（放了几个）和容量（能放几个）；长度等于容量时就是满了。
满了就把容量翻倍：比每次多一格搬得少得多。
写成函数时，长度和容量传地址，块的地址作为返回值交回来；最后 free 一次。