Stop Using Arrays for Everything

我是 AlanWu。當我開始學習 C++ 時，遇到「我需要儲存多個東西」的問題，我的答案永遠是陣列……

我是 AlanWu。當我開始學習 C++ 時，遇到「我需要儲存多個東西」的問題，我的答案永遠是陣列。int arr[1000]。每次都是如此。

後來我發現了 STL 容器，才意識到自己一直以來都太辛苦了。以下說明什麼時候該使用哪一種容器。

vector — 你的新預設選擇

如果你以前寫 int arr[1000]，那就改用 vector<int> arr 吧。它會自動擴展、縮減、知道自己的大小，而且傳遞給函式時不用另外傳長度。

// 舊寫法
int scores[100];
int n = 0;
scores[n++] = 95;  // 希望 n 不會超過 99

// 新寫法
vector<int> scores;
scores.push_back(95);  // 永遠不會溢位，也不用手動計數

Enter fullscreen mode Exit fullscreen mode

使用 vector 的時機：當你需要一個有序的清單，而且主要是在尾端新增或用索引存取。

不適合使用 vector 的時機：當你需要經常在中間插入或刪除元素。這時複雜度是 O(n) —— 後面的元素都要移動。

陣列和 vector 都使用整數索引。如果你想用名字而不是編號來查詢學生的分數呢？

map<string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 88;

cout << scores["Alice"];  // 95

Enter fullscreen mode Exit fullscreen mode

map 的底層是平衡二元搜尋樹。查詢複雜度是 O(log n)，而不是 O(1)。但對大多數情況來說已經夠快，而且程式碼非常簡單。

使用 map 的時機：當你有鍵值對，而且鍵不只是 0、1、2、3……

不適合使用 map 的時機：當你只需要整數索引 —— 這時應該用 vector。或者當你需要平均 O(1) 的查詢 —— 這時應該用 unordered_map。

unordered_map<string, int> scores;
scores["Alice"] = 95;

Enter fullscreen mode Exit fullscreen mode

看起來和 map 完全一樣。不同之處在於 unordered_map 使用雜湊表。平均查詢複雜度是 O(1) 而非 O(log n)。但若發生碰撞，最壞情況仍是 O(n)，而且鍵值沒有順序，也會使用更多記憶體。

我的原則：先從 unordered_map 開始。如果需要鍵值依序排列，再改用 map。

需要追蹤哪些 ID 已經看過？不要用 vector 然後每次都迴圈搜尋。

set<int> seen;
seen.insert(42);
seen.insert(17);

if (seen.count(42)) {  // true — O(log n)
    // 已經看過了
}

Enter fullscreen mode Exit fullscreen mode

set 會以排序順序儲存獨一無二的值。不允許重複。

若需要平均 O(1) 且不需要排序：使用 unordered_set。

這涵蓋了 90% 的情況。

我看到初學者因為覺得 deque 聽起來很酷而使用它。雙端佇列。可以在兩端插入。

除非你在寫滑動視窗演算法或排程器，否則你不需要 deque。用 push_back 的 vector 更快也更簡單。

下次當你想用一般陣列時，問問自己：vector、map 或 set 能不能用一半的程式碼完成這件事？答案通常是肯定的。