學習目標

讀完本章後，你應該能夠：

  • 說明 STL 的三大支柱（容器、迭代器、演算法）如何協作，以及為何如此設計
  • 理解每種容器的 底層結構、記憶體佈局與時間複雜度（Big-O）
  • 熟練使用 序列容器：vector、deque、list、forward_list、array
  • 熟練使用 關聯容器：map、multimap、set、multiset（紅黑樹、有序）
  • 熟練使用 無序容器：unordered_map/unordered_set（雜湊表、負載因子、自訂雜湊）
  • 熟練使用 容器配接器：stack、queue、priority_queue
  • 區分 emplace 與 insert 的差異與適用時機
  • 掌握 迭代器失效（iterator invalidation）規則——這是實務上最常見的 bug 來源
  • 使用 std::pair 與 std::tuple 打包多個值
  • 依需求 選擇最合適的容器

1. STL 概觀：三大支柱如何協作

STL（Standard Template Library，標準模板庫）建立在 泛型程式設計 之上，由三大核心元件組成：

元件 角色 範例
容器（Containers） 儲存資料的資料結構 vector、map、set、unordered_map
迭代器（Iterators） 連接容器與演算法的「通用指標」 begin()、end()、++it、*it
演算法（Algorithms） 對資料進行操作的函式 sort、find、transform、accumulate

1.1 為什麼要這樣拆三層？

關鍵在 解耦合。如果沒有迭代器這層抽象，N 種容器 × M 種演算法就要寫 N×M 份程式碼。有了迭代器當「中間語言」，演算法只需針對「迭代器」撰寫一次，就能套用到所有容器：

   容器                迭代器                  演算法
┌─────────┐       ┌──────────────┐       ┌──────────────┐
│ vector  │──────►│              │       │   sort()     │
│ list    │──────►│  begin()     │──────►│   find()     │
│ deque   │──────►│  end()       │       │   count()    │
│ map     │──────►│  *it, ++it   │       │   for_each() │
└─────────┘       └──────────────┘       └──────────────┘
   N 種                橋樑                    M 種
        只需 N + M 份程式碼，而非 N × M

std::vector<int> v = {3, 1, 2};
std::sort(v.begin(), v.end());        // sort 透過迭代器操作，不需知道 v 是 vector

std::list<int> lst = {3, 1, 2};
// std::sort(lst.begin(), lst.end()); // ❌ list 的迭代器不支援隨機存取
lst.sort();                           // list 有自己的成員 sort

核心觀念：演算法不直接認識容器，只認識 迭代器。理解這點，後面的一切（包括迭代器失效）才會通透。迭代器與演算法的細節留待 Ch14。

2. 序列容器（Sequence Containers）

序列容器中的元素 按插入順序線性排列。

2.1 std::vector — 動態陣列（最重要！）

vector 是 連續記憶體 的動態陣列，是 90% 場合的首選。

#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};
v.push_back(6);           // 尾端加入（複製）
v.emplace_back(7);        // 尾端原地建構（通常更快，見 §6）
int x = v[0];             // 隨機存取 O(1)
v.size();                 // 元素數量
v.capacity();             // 目前已配置的空間（>= size）

成長機制：size vs capacity vs reserve

vector 的記憶體像這樣：當 size 即將超過 capacity，它會 配置一塊更大的記憶體（通常是 1.5 或 2 倍）、搬移所有元素、釋放舊記憶體。這個「重新配置（reallocation）」是 O(n) 的昂貴操作。

push_back 過程（容量 2 倍成長，實作而定）：
size=0 cap=0  ──push──►  size=1 cap=1
size=1 cap=1  ──push──►  size=2 cap=2   （重新配置）
size=2 cap=2  ──push──►  size=3 cap=4   （重新配置，搬 2 個）
size=4 cap=4  ──push──►  size=5 cap=8   （重新配置，搬 4 個）

每次 push_back 平均是 攤銷 O(1)（amortized O(1)）：雖然偶爾要 O(n) 搬移，但分攤到每次操作仍是常數。

reserve() 是重要的效能武器：若事先知道大概要存多少元素，先 reserve 可避免反覆重新配置：

std::vector<int> v;
v.reserve(1000);          // 一次配置足夠空間，後續 push_back 不再重新配置
for (int i = 0; i < 1000; ++i) v.push_back(i);

預期觀察到的成長（來自 vector_deque.cpp，實際倍率依編譯器標準庫而定）：

push_back(0) → size: 1, capacity: 1
push_back(1) → size: 2, capacity: 2
push_back(2) → size: 3, capacity: 4
push_back(4) → size: 5, capacity: 8
reserve(100) → size: 10, capacity: 100
shrink_to_fit() → size: 10, capacity: 10

⚠️ 重點：重新配置會 使所有迭代器、指標、參考失效！這是 §7 的核心。

操作 時間複雜度
隨機存取 [] / at() O(1)
尾端插入/刪除 push_back/pop_back 攤銷 O(1)
中間/頭端插入/刪除 O(n)（要搬移後面元素）
搜尋（未排序） O(n)

2.2 std::deque — 雙端佇列

deque（double-ended queue）支援 頭尾兩端都 O(1) 插入，同時保有 O(1) 隨機存取。

#include <deque>

std::deque<int> d = {2, 3, 4};
d.push_front(1);          // 頭端加入 O(1)  ← vector 做不到
d.push_back(5);           // 尾端加入 O(1)
d.pop_front();            // 頭端移除 O(1)
int x = d[2];             // 隨機存取 O(1)

deque 的內部結構

deque 不是連續記憶體，而是由「一塊塊固定大小的區塊（chunk）」組成，再用一個「中央地圖（map）」索引這些區塊：

中央地圖（指標陣列）
┌───┬───┬───┬───┐
│ ● │ ● │ ● │ ● │
└─┬─┴─┬─┴─┬─┴─┬─┘
  ▼   ▼   ▼   ▼
[區塊][區塊][區塊][區塊]   ← 各區塊內部連續，區塊之間不連續

這就是為什麼 deque 頭端插入便宜（在最前面的區塊前加新區塊即可），但因記憶體不完全連續，快取友好度與遍歷速度略遜於 vector。

操作 vector deque
隨機存取 O(1) O(1)
尾端增刪 攤銷 O(1) O(1)
頭端增刪 O(n) O(1)
中間增刪 O(n) O(n)
連續記憶體 ✅ ❌

2.3 std::list — 雙向鏈結串列

list 是 雙向鏈結串列，每個節點存有「值 + 前指標 + 後指標」。已知位置時插入/刪除是 O(1)，但 不支援隨機存取（沒有 []）。

#include <list>

std::list<int> lst = {3, 1, 4, 1, 5};
lst.push_front(0);        // O(1)
lst.push_back(9);         // O(1)
lst.sort();               // 成員 sort（不能用 std::sort）
lst.unique();             // 移除「連續」重複
lst.reverse();            // 反轉
lst.merge(other);         // 合併兩個已排序 list
lst.splice(pos, other);   // O(1) 把 other 接到 pos（鏈結串列獨有的拼接）

雙向鏈結串列：
nullptr ◄─ [3] ◄─► [1] ◄─► [4] ◄─► [5] ─► nullptr

list 的賣點是 splice（拼接）：不複製元素、只改指標，把一段節點 O(1) 搬到另一個 list。代價是每個節點額外存兩個指標，記憶體開銷大、快取不友好。

2.4 std::forward_list — 單向鏈結串列（C++11）

只存「後指標」，更省記憶體，但只能 前向遍歷，且操作是 insert_after / erase_after（操作「某節點之後」）。

#include <forward_list>

std::forward_list<int> fl = {1, 2, 3};
fl.push_front(0);                       // 只有 push_front，沒有 push_back
fl.insert_after(fl.begin(), 10);        // 在第一個元素「後面」插入
fl.insert_after(fl.before_begin(), -1); // before_begin() 才能在最前面插入
// 注意：forward_list 沒有 size()！

2.5 std::array — 固定大小陣列（C++11）

大小在 編譯期 決定，是 C 陣列的安全替代品，沒有動態配置成本。

#include <array>

std::array<int, 5> arr = {1, 2, 3, 4, 5};
arr.size();               // 永遠是 5（編譯期常數）
arr.at(2);                // 有邊界檢查
arr.front(); arr.back();  // 支援 STL 介面

📖 完整範例：vector_deque.cpp、list_forward_list.cpp

3. 關聯容器（Associative Containers）

元素依鍵值 自動排序（預設升序），底層是 紅黑樹（red-black tree，一種自平衡二元搜尋樹），所有操作都是 O(log n)。

紅黑樹（概念）：保持平衡，高度約 log n
            [4]
           /   \
        [2]     [6]
        / \     / \
      [1] [3] [5] [7]
   → 中序走訪即得有序序列：1 2 3 4 5 6 7

3.1 std::map — 鍵值對映（key 唯一、有序）

#include <map>

std::map<std::string, int> scores;
scores["Alice"] = 95;             // [] 不存在則「插入」，存在則「更新」
scores.insert({"Bob", 87});       // insert：已存在則不動作
scores.emplace("Eve", 88);        // emplace：原地建構
int a = scores.at("Alice");       // at：不存在拋 std::out_of_range
auto it = scores.find("Charlie"); // find：回傳迭代器，O(log n)

for (const auto& [name, score] : scores) {   // C++17 結構化綁定，依 key 排序
    std::cout << name << ": " << score << '\n';
}

⚠️ 經典陷阱：map::operator[] 在 key 不存在時 會自動插入一個預設值！若只是想「查詢」，請用 find() 或 at()，否則會意外讓 map 變大。

std::map<std::string, int> m;
if (m["missing"] == 0) { }   // ❌ 這行已經把 "missing" 插入成 0 了！
if (m.find("missing") != m.end()) { }   // ✅ 純查詢，不會插入

3.2 std::multimap — 允許重複鍵

std::multimap<std::string, int> mm;
mm.insert({"Alice", 95});
mm.insert({"Alice", 88});          // 同一 key 可有多筆
auto [lo, hi] = mm.equal_range("Alice");   // 取得某 key 的所有值
for (auto it = lo; it != hi; ++it) std::cout << it->second << ' ';

3.3 std::set / std::multiset

set 是「唯一值 的有序集合」；multiset 允許重複。

#include <set>

std::set<int> s = {3, 1, 4, 1, 5};   // 自動排序、去重 → {1, 3, 4, 5}
auto [it, inserted] = s.insert(2);   // insert 回傳 pair<迭代器, 是否插入成功>
s.count(3);                          // set 回傳 0 或 1

std::multiset<int> ms = {3, 1, 4, 1, 5};  // {1, 1, 3, 4, 5}
ms.count(1);                              // 回傳 2
操作 時間複雜度
插入 / 搜尋 / 刪除 O(log n)
走訪（依序） O(n)
最小/最大值 *begin() / *rbegin()，O(1)

使用前提：key 型別必須支援 operator<（或提供自訂比較器）。

📖 完整範例：map_set.cpp

4. 無序容器（Unordered Containers，C++11）

底層是 雜湊表（hash table），平均操作 O(1)，但 不保證任何順序。

4.1 雜湊表如何運作？

  1. 把 key 丟進 雜湊函式（hash function） 得到一個雜湊值。
  2. 雜湊值對「桶（bucket）」數量取模，決定該 key 放在哪個桶。
  3. 同一桶內若有多個 key（雜湊碰撞 collision），通常用鏈結串列串起來。
雜湊函式 h(key) % bucket_count
key="Bob" → bucket[2]
                 buckets
        ┌───┬───┬───┬───┬───┐
        │ 0 │ 1 │ 2 │ 3 │ 4 │
        └───┴───┴─┬─┴───┴───┘
                  ▼
              [Bob:30] → [Eve:28]   ← 碰撞時鏈在同一桶

4.2 負載因子（load factor）與 rehash

  • load_factor = 元素數 / 桶數。當它超過 max_load_factor（預設 1.0），容器會 rehash：增加桶數、重新分配所有元素（O(n)）。
  • 糟糕的雜湊函式會讓元素擠在少數桶，退化成 O(n)。
#include <unordered_map>

std::unordered_map<std::string, int> um;
um["key1"] = 100;
um.bucket_count();        // 桶的數量
um.load_factor();         // 目前負載因子
um.max_load_factor();     // 觸發 rehash 的門檻
um.reserve(1000);         // 預留空間，減少 rehash

4.3 自訂型別當 key：需要 operator== 與雜湊函式

struct Point { int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};
std::unordered_set<Point, PointHash> ps;   // 第二個模板參數提供雜湊器
操作 平均 最差
插入 / 搜尋 / 刪除 O(1) O(n)（全部碰撞時）

📖 完整範例：unordered_containers.cpp

4.4 map vs unordered_map 怎麼選？

特性 map（紅黑樹） unordered_map（雜湊表）
複雜度 O(log n) 平均 O(1)
元素順序 有序 無序
需要 operator< ✅ ❌
需要雜湊函式 ❌ ✅
記憶體 較少 較多
適用 需要排序走訪、範圍查詢 只需快速查找

5. 容器配接器（Container Adaptors）

配接器是對底層容器的 介面封裝，刻意限制操作以符合特定資料結構語意。

5.1 std::stack — 堆疊（LIFO，後進先出）

#include <stack>
std::stack<int> st;
st.push(1); st.push(2);
st.top();      // 2（看頂端，不移除）
st.pop();      // 移除頂端（注意：pop 不回傳值！）
st.empty();

5.2 std::queue — 佇列（FIFO，先進先出）

#include <queue>
std::queue<int> q;
q.push(1); q.push(2);
q.front();     // 1（最先進的）
q.back();      // 2
q.pop();       // 移除前端

5.3 std::priority_queue — 優先佇列（堆積）

預設是 最大堆（max-heap），top() 永遠是最大值。

#include <queue>
std::priority_queue<int> pq;          // 最大堆
pq.push(3); pq.push(1); pq.push(4);
pq.top();                             // 4

// 最小堆：用 greater 比較器
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
配接器 語意 預設底層容器
stack LIFO deque
queue FIFO deque
priority_queue 取最大/最小 vector（堆積化）

6. emplace vs insert／push

動作 行為
push_back(obj) / insert(obj) 先 建立 物件，再 複製/搬移 進容器
emplace_back(args...) / emplace(args...) 把建構引數 直接傳入容器內就地建構，省去中間的暫時物件 
std::vector<std::pair<int, std::string>> v;
v.push_back(std::make_pair(1, "a"));   // 建立 pair → 再搬進去
v.emplace_back(1, "a");                // 直接在容器內建構 pair(1, "a")
  • 何時用 emplace：元素是「建構成本較高」或「需要多個引數建構」的物件時，emplace 能避免多餘的暫時物件。
  • 注意：對於已存在的物件或簡單型別（如 int），emplace 與 push 幾乎沒差別；不要為了 emplace 而 emplace。map::emplace 即使 key 已存在也會先建構引數（可能浪費），此時 C++17 的 try_emplace 更好。

7. 迭代器失效規則（非常重要！）

當容器被修改，先前取得的迭代器/指標/參考可能指向 已被搬移或釋放的記憶體，繼續使用就是 未定義行為（UB）。這是 STL 實務最常見的 bug 來源。

7.1 各容器的失效規則總表

容器 插入時 刪除時
vector 若觸發重新配置 → 全部失效；否則插入點 之後 的失效 被刪元素及 其後 的全部失效
deque 插入頭/尾 → 迭代器失效但 參考不失效；插入中間 → 全部失效 刪頭/尾 → 只該元素失效；刪中間 → 全部失效
list / forward_list 不失效（只動指標） 僅被刪除的元素 失效
set / map（紅黑樹） 不失效 僅被刪除的元素 失效
unordered_*（雜湊表） 若 rehash → 迭代器全失效（參考/指標不失效） 僅被刪除的元素 失效

記憶法：節點式容器（list、map、set）對「其他元素」很安全，因為元素各自獨立配置；連續/區塊容器（vector、deque、unordered） 會因重新配置而大範圍失效。

7.2 最常見的錯誤：邊走訪邊刪除

// ❌ 錯誤：erase 後 it 失效，++it 是 UB
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it % 2 == 0) v.erase(it);

// ✅ 正確：用 erase 的回傳值（指向被刪元素的下一個）
for (auto it = v.begin(); it != v.end(); )
    if (*it % 2 == 0) it = v.erase(it);
    else ++it;

對 vector 移除符合條件的元素，最佳實踐是 erase-remove 慣用法（C++20 後可用 std::erase_if）：

v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x){ return x % 2 == 0; }),
        v.end());

對 map/set，C++11 起 erase 也會回傳下一個迭代器：

for (auto it = m.begin(); it != m.end(); )
    if (should_remove(it->first)) it = m.erase(it);
    else ++it;

8. std::pair 與 std::tuple

8.1 std::pair — 打包兩個值

#include <utility>

std::pair<std::string, int> p{"Alice", 95};
p.first;                            // "Alice"
p.second;                           // 95
auto p2 = std::make_pair(1, 3.14);  // 自動推導型別

auto [name, score] = p;             // C++17 結構化綁定，超好用

map 的元素其實就是 std::pair<const Key, Value>，這也是為什麼 it->first、it->second 能用。

8.2 std::tuple — 打包任意數量的值

#include <tuple>

std::tuple<int, std::string, double> t{1, "Bob", 4.5};
std::get<0>(t);                     // 1（用索引存取）
std::get<1>(t);                     // "Bob"

auto t2 = std::make_tuple(42, "hi", 3.14);
auto [id, name, value] = t2;        // C++17 結構化綁定一次拆開

// 常見用途：讓函式回傳多個值
std::tuple<int, int> divmod(int a, int b) { return {a / b, a % b}; }
auto [q, r] = divmod(17, 5);        // q=3, r=2
特性 pair tuple
元素數量 固定 2 個 任意數量
存取 .first / .second std::get<N>()
結構化綁定 ✅ ✅

9. 如何選擇容器（決策指南）

需要 key→value 對映嗎？
├─ 是 → 需要「有序」走訪或範圍查詢嗎？
│        ├─ 是 → std::map / std::multimap
│        └─ 否 → std::unordered_map（更快）
└─ 否 → 只存「值」，需要去重/集合運算嗎？
         ├─ 是 → 需要有序嗎？ set / multiset  vs  unordered_set
         └─ 否 → 是線性序列，主要操作在哪裡？
                  ├─ 尾端為主、要隨機存取 → std::vector（首選）
                  ├─ 頭尾都要快速增刪      → std::deque
                  ├─ 大量任意位置增刪/拼接 → std::list
                  └─ 固定大小、編譯期已知  → std::array
需求 推薦容器
隨機存取、尾端增刪 vector
頭尾都要增刪 deque
大量中間插入刪除、拼接 list
鍵值查詢（有序） map
鍵值查詢（極速） unordered_map
唯一元素集合（有序） set
唯一元素集合（極速） unordered_set
LIFO / FIFO / 取極值 stack / queue / priority_queue

經驗法則（C++ Core Guidelines 精神）：不確定就先用 vector。連續記憶體帶來的快取友好性，常讓 vector 即使在理論上「較差」的操作上，實測仍勝過 list/deque。先求正確與簡單，真有效能問題再用實測（profiling）決定是否換容器。

10. 最佳實踐（參考 C++ Core Guidelines）

  • [SL.con.1] 優先使用 STL vector、array 而非 C 陣列：自動管理記憶體、有邊界檢查的 at()。
  • [SL.con.2] 預設選 vector，除非有理由用別的。
  • [SL.con.3] 避免邊界錯誤：用範圍 for、at()、迭代器範圍，少用裸索引。
  • [ES.27 / 善用 reserve]：已知大小時先 reserve，避免反覆重新配置。
  • 善用結構化綁定（C++17） 走訪 map：for (const auto& [k, v] : m)，比 it->first/second 清楚。
  • 查詢別用 map::operator[]：用 find() / at() / count()（C++20 後可用 contains()），避免意外插入。
  • 就地建構用 emplace，但別盲目；簡單型別或已有物件時 push/insert 即可。
  • 修改容器後重新取得迭代器：牢記 §7 的失效規則，刪除時用 erase 回傳值或 std::erase_if。
  • 為演算法選對容器：要 std::sort 就用支援隨機存取的 vector/deque/array，list 用自身 sort。

11. 常見錯誤與陷阱

錯誤 說明與解法
vector 迭代器失效 push_back 觸發重新配置後，舊迭代器/指標/參考全失效。解法：操作後重新取得，或先 reserve。
map::operator[] 意外插入 查詢時用 [] 會插入預設值。解法：用 find()/at()/count()。
邊走訪邊 erase erase 後迭代器失效仍 ++it → UB。解法：it = c.erase(it) 或 erase-remove。
unordered 退化成 O(n) 雜湊函式太差導致大量碰撞。解法：設計良好的雜湊、適時 reserve。
混淆 size() 與 capacity() size 是元素數，capacity 是已配置空間。clear() 不會降低 capacity。
對 list 用 std::sort list 迭代器非隨機存取。解法：用 lst.sort()。
forward_list 找不到 size() 它刻意不提供 size()。需要可換 list。
stack/queue 的 pop() 不回傳值 要先 top()/front() 取值再 pop()。
priority_queue 預設是最大堆 想要最小堆需指定 std::greater。
忘記 #include 對應標頭 <vector>、<map>、<set>、<unordered_map>、<queue>、<utility>、<tuple> 等各自獨立。

重點整理

  1. STL 三大支柱：容器、迭代器、演算法，透過迭代器解耦，達成 N+M 而非 N×M 的程式碼複用。
  2. vector 是預設首選：連續記憶體、O(1) 隨機存取、攤銷 O(1) 尾端增刪；善用 reserve。
  3. deque 頭尾皆 O(1)，但記憶體分區塊、快取較不友好。
  4. list/forward_list 任意位置 O(1) 增刪與 splice，但無隨機存取、開銷大。
  5. map/set（紅黑樹） 有序、O(log n)；unordered_*（雜湊表） 無序、平均 O(1)。
  6. 配接器 stack/queue/priority_queue 提供受限介面的特定語意。
  7. emplace 就地建構省暫時物件，但別盲目使用。
  8. 迭代器失效規則 是實務最大坑：節點式容器安全，連續/雜湊容器在重新配置時大範圍失效。
  9. pair/tuple + 結構化綁定 方便打包與回傳多值。
  10. 選容器先看存取模式、增刪位置、是否需排序、效能需求；不確定就用 vector。

練習題

以下每題都能用 g++ -std=c++17 -Wall 編譯。建議先自己嘗試，再對照對應的 .cpp 範例。

練習 1（基礎）：向量過濾與反向輸出

建立 vector<int>，放入 1~10，移除所有偶數，最後 反向 印出。

  • 提示：移除偶數用 erase-remove 慣用法（std::remove_if + erase）；反向輸出用 rbegin()/rend()。可參考 vector_deque.cpp 的第 5、6 節。

練習 2（基礎）：單字計數器

給一段寫死的英文文字，用 map<string, int> 統計每個單字出現次數，並 按字母順序 輸出。

  • 提示：用 std::istringstream 配合 >> 切詞；word_count[word]++ 自動計數；map 走訪即有序。可參考 map_set.cpp 第 6 節。

練習 3（基礎）：去重排序

給一個含重複元素的 vector<int>，用 set 去重並輸出排序結果，再用 unordered_set 做一次，比較兩者輸出順序的差異。

  • 提示：std::set<int> s(v.begin(), v.end()); 一行去重排序。可參考 map_set.cpp 第 4 節與 unordered_containers.cpp。

練習 4（中級）：括號匹配檢查

用 std::stack 寫一個函式，檢查字串中的 ()、[]、{} 是否正確配對（例如 "{[()]}" 合法，"([)]" 不合法）。

  • 提示：遇到開括號 push，遇到閉括號就檢查 top() 是否為對應開括號，匹配則 pop；最後 stack 須為空。

練習 5（中級）：學生成績系統

用 map<string, vector<int>> 儲存多位學生的多次成績，實作：新增成績、查詢平均分、依平均分 印出全班排名。

  • 提示：排名時把 (平均, 姓名) 收集到 vector<pair<double,string>> 再 std::sort（用 std::greater 或自訂比較降序）。可參考 map_set.cpp 末段的成績系統。

練習 6（中級）：迭代器失效實驗

寫程式 故意觸發 一次 vector 迭代器失效（先存 auto it = v.begin();，再大量 push_back 觸發重新配置），印出 capacity 變化說明為何 it 失效；接著示範 正確 的安全寫法（重新取得迭代器或先 reserve）。

  • 提示：對照失效前後的 v.capacity() 與 &v[0] 位址變化即可看出記憶體被搬移。不要 真的解參考失效的迭代器（UB），用位址說明即可。

練習 7（中級）：兩陣列交集

給兩個 vector<int>，用 unordered_set 在 平均 O(n) 時間內求出交集。

  • 提示：把 arr1 放進 unordered_set，再走訪 arr2，用 count() 判斷是否在集合內。可參考 unordered_containers.cpp 第 5 節。

練習 8（挑戰）：Top-K 高頻單字

給一段文字，先用 unordered_map<string,int> 統計詞頻，再用 priority_queue 找出 出現次數最多的前 K 個單字（次數相同時按字母序）。

  • 提示：詞頻統計後，把 (count, word) 丟進 priority_queue；或用最小堆維持大小為 K 的堆積。注意比較器要正確處理「次數降序、字母升序」。

對應程式碼檔案