16｜動態陣列

還沒完成只限 CCPU 時間上限 1 秒heap 上限 1048576 bytes

相關主題： 控制記憶體的必備指令

題目說明

只限 C｜CPU 時間上限 1 秒｜計算 heap 用量：最高不能超過 1 MiB（1048576 bytes），有記憶體洩漏就不通過

題目

讀入一串整數，事先不知道有幾個，一直讀到輸入結束（EOF）為止。全部讀完之後，先輸出整數的個數，再把它們倒過來輸出。

因為要倒過來輸出，所以一定要先把全部的數存起來。問題是：不知道有幾個，陣列要開多大？

這一題要你自己做一個動態陣列（會自己長大的陣列），這也是 C++ std::vector 在底層做的事：

用一個指標指向 heap 上配置的空間，另外記住「目前存了幾個」（size）和「目前的空間放得下幾個」（capacity，容量）。
每讀到一個數，如果空間已經滿了（size == capacity），就用 realloc 把空間加倍，再把數放進去。
用完之後用 free 釋放。

規定：

必須用 malloc / realloc 配置空間，用完要 free。
不要開一個固定大小的全域陣列（例如 int a[100000];）。測試資料雖然最多 10 萬個數，但這一題請假裝你不知道上限——真實世界常常是這樣，例如讀一個不知道多大的檔案。全域陣列不在 heap 上，檢查程式看不出來，請自己遵守。
heap 最高用量不能超過 1 MiB（1048576 bytes）。容量加倍的寫法最多只會用到大約 800 KB；「保險起見一開始就 malloc 一百萬個 int」要 4000000 bytes，會得到「heap 超過上限」。
程式結束時配置的記憶體都要釋放，否則會得到「記憶體洩漏」。

記帳器怎麼算 realloc：把它當成「釋放舊的那塊，再配置新的那塊」。（實際上 realloc 搬家的瞬間新舊兩塊會同時存在，這裡不計較。）所以 heap 最高用量大約就是「最後的容量 × 4 bytes」。

輸入

若干個整數（可能是 0 個），以空白或換行分隔：一行可能有好幾個數，也可能有空行或多餘的空白。

每個整數都在 int 的範圍內（−2147483648 到 2147483647）。
整數的個數 N 滿足 0 ≤ N ≤ 100000，但輸入裡沒有事先告訴你 N 是多少。

輸出

第一行：整數的個數 N。
第二行：把讀到的 N 個整數倒過來（最後讀到的先輸出），以一個空白分隔。

N = 0 時只輸出第一行的 0。

範例

輸入：

3 1 4 1 5
9 2 6

輸出：

8
6 2 9 5 1 4 1 3

複習重點

C：

malloc(bytes) 配置一塊 heap 記憶體，回傳指向它的指標；失敗時回傳 NULL
慣用寫法：int *p = malloc(n * sizeof *p);——用 sizeof *p 而不是 sizeof(int)，以後改了型別也不會算錯
realloc(p, new_bytes) 把一塊記憶體改成新的大小：可能原地變大，也可能搬到新的位置（自動把舊資料複製過去、釋放舊的那塊），所以一定要用它的回傳值
realloc(NULL, n) 等於 malloc(n)；free(NULL) 什麼都不做，都是合法的
每一個 malloc / realloc 配置的區塊，最後都要剛好 free 一次：忘了 free 是記憶體洩漏，free 兩次（double free）或 free 之後還使用（use-after-free）是更嚴重的錯誤
scanf 回傳成功讀到幾個項目，讀到輸入結束時回傳 EOF，所以 while (scanf("%d", &x) == 1) 可以一直讀到結束

C++ 對照：

std::vector<int> 的 push_back 就是這一題的做法：size() 是存了幾個，capacity() 是容量，滿了就配置更大的空間、搬過去
vector 離開範圍時會自動釋放記憶體（解構子），所以不會忘記 free——第 19 題會再練這個觀念（RAII）

提示 1：要記住哪些東西？怎麼「放進一個數」？

把三個相關的變數包成一個 struct，再寫一個函式負責「放進一個數」：

typedef struct {
    int *data;       // 指向 heap 上的空間，一開始是 NULL
    size_t size;     // 目前存了幾個
    size_t cap;      // 目前的空間放得下幾個
} IntVec;

int vec_push(IntVec *v, int x);   // 成功回傳 1，記憶體不夠回傳 0

函式要修改 v 裡面的欄位，所以參數是指標 IntVec *v，用 v->size 存取欄位（等於 (*v).size）。

提示 2：realloc 的正確寫法

size_t new_cap = (v->cap == 0) ? 16 : v->cap * 2;
int *tmp = realloc(v->data, new_cap * sizeof *tmp);
if (tmp == NULL) {
    return 0;          // 失敗時舊的 v->data 還在，呼叫端之後照樣可以 free 它
}
v->data = tmp;
v->cap = new_cap;

為什麼不直接寫 v->data = realloc(v->data, ...)？因為 realloc 失敗時回傳 NULL，但舊的那塊沒有被釋放；直接蓋掉的話，舊的位址就弄丟了，再也沒辦法 free 它——這本身就是一個記憶體洩漏。

提示 3：為什麼要加倍，而不是每次多 1 格？怎麼看自己用了多少 heap？

realloc 可能需要把資料搬到新的位置。如果每次只多 1 格，最壞的情況每放一個數都要搬一次：1 + 2 + 3 + … + 100000 大約是 50 億次複製，太慢了。容量加倍的話，搬的總次數不會超過 2N，而且最後的容量一定小於 2N，記憶體也不會浪費太多。

練習時可以看記憶體報告：在終端機輸入

run exercises\3-memory\16-dynamic-array\main.c --mem --input exercises\3-memory\16-dynamic-array\tests\01.in

或者在 VS Code 開著 main.c，按 Ctrl+Shift+P → Tasks: Run Task → 「執行並顯示記憶體報告」，再自己打輸入（打完按 Ctrl+Z 再按 Enter 表示輸入結束）。報告會顯示 heap 最高同時用量、配置次數，以及哪一行配置的記憶體沒有釋放。