C++ STL 核心容器與算法深度掌握：string、vector、list、set、map 實戰指南

STL 三大核心組件

• 容器：管理數據集合的內存分配與存取 (序列式/關聯式/無序/適配器)
• 迭代器：統一訪問接口，泛化指針操作 (輸入/輸出/前向/雙向/隨機訪問)
• 算法：通用操作 (排序、查找、變換、數值、集合運算)，基於迭代器與容器解耦

第 17 章：std::string — 字符串處理利器

核心優勢

• 自動內存管理 (SSO 小字符串優化，通常 ≤15/22 字符不分配堆內存)
• 豐富操作：+, +=, append, insert, erase, replace, substr, find, rfind, compare
• 兼容 C 風格：c_str() (null 結尾), data() (C++17 保證 null 結尾)
• 支持移動語義，傳遞高效

關鍵用法示例

#include <string>
#include <algorithm> // for transform

void string_demo() {
    std::string s1 = "Hello";
    std::string s2 = s1 + ", World!";        // 拼接
    s1 += " C++";                            // 追加
    
    // 查找與替換
    auto pos = s2.find("World");
    if (pos != std::string::npos) s2.replace(pos, 5, "STL");
    
    // 大小寫轉換 (需注意 locale)
    std::transform(s2.begin(), s2.end(), s2.begin(), ::toupper);
    
    // 分割字符串 (C++20 可用 ranges::views::split)
    std::string csv = "a,b,c,d";
    std::stringstream ss(csv);
    std::string token;
    while (std::getline(ss, token, ',')) { /* 處理 token */ }
    
    // 原始字面量 (C++11)
    std::string path = R"(C:\Users\Name\Documents)"; // 無需轉義
}

第 18 章：std::vector & std::deque — 動態數組

vector 核心特性

• 連續內存，隨機訪問 O(1)，尾部增刪攤還 O(1)，頭部/中間增刪 O(n)
• size() (元素數) vs capacity() (分配容量)，reserve() 預分配避免重分配
• shrink_to_fit() (C++11) 釋放多餘容量
• 迭代器失效規則：擴容/插入/刪除導致所有迭代器失效

deque (雙端隊列) 差異

• 分段連續存儲 (塊映射)，支持雙端 O(1) 插刪
• 隨機訪問 O(1) 但常數因子較大
• 迭代器失效：中間插刪導致所有失效，雙端操作不失效
• 適合寬度優先搜索 (BFS) 隊列、滑動窗口

void vector_deque_demo() {
    std::vector<int> v = {1, 2, 3};
    v.reserve(100);           // 預分配
    v.push_back(4);           // 尾部插入
    v.insert(v.begin()+1, 9); // 中間插入 (O(n))
    
    std::deque<int> d = {1, 2, 3};
    d.push_front(0);          // 頭部插入 O(1)
    d.push_back(4);           // 尾部插入 O(1)
    
    // 算法配合
    std::sort(v.begin(), v.end());
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) v.erase(it);
}

第 19 章：std::list — 雙向鏈表

• 節點離散存儲，雙向鏈接，任意位置插刪 O(1) (給定迭代器)
• 不支持隨機訪問，只能順序遍歷
• 迭代器穩定：插入/刪除/拼接 不會 使其他迭代器失效 (極大優勢)
• 成員函數算法：sort(), merge(), splice(), unique(), remove(), reverse() — 比通用算法高效 (不移動元素，只調整指針)

void list_demo() {
    std::list<int> lst = {5, 2, 8, 2, 1};
    lst.sort();               // 成員排序 O(n log n)
    lst.unique();             // 刪除相鄰重複 (需先排序)
    lst.remove(2);            // 刪除所有值為 2 的節點
    
    std::list<int> lst2 = {10, 20};
    lst.splice(lst.begin(), lst2); // lst2 內容移動到 lst 開頭，lst2 變空，O(1)
}

第 20 章：std::set & std::multiset — 有序集合

• 底層紅黑樹，元素有序 (默認 std::less，即升序)
• set：鍵值唯一；multiset：允許重複鍵
• 插入/刪除/查找 O(log n)
• 迭代器雙向，遍歷有序
• 自定義比較：std::set<T, Comp>，Comp 需嚴格弱序

void set_demo() {
    std::set<int> s = {3, 1, 4, 1, 5}; // 自動去重: {1,3,4,5}
    s.insert(2);                       // {1,2,3,4,5}
    
    auto it = s.find(3);               // 查找
    if (it != s.end()) s.erase(it);    // 按迭代器刪除
    
    // 區間操作
    auto range = s.equal_range(3);     // pair<lower_bound, upper_bound>
    
    // multiset 允許重複
    std::multiset<int> ms = {1, 1, 2};
    ms.insert(1);                      // {1,1,1,2}
    std::cout << ms.count(1);          // 3
    ms.erase(1);                       // 刪除所有 1
    ms.erase(ms.find(2));              // 刪除一個 2
}

第 21 章：std::map & std::multimap — 關聯映射

• 鍵值對 std::pair<const Key, Value>，按 Key 有序
• map：Key 唯一；multimap：Key 可重複
• operator[]：若 Key 不存在會默認構造 Value 並插入 (僅 map 有)，查找請用 find() 或 at() (C++11 拋出異常)
• 插入方式：insert({k,v}), emplace(k,v) (C++11 原地構造)，try_emplace (C++17 安全插入)

void map_demo() {
    std::map<int, std::string> m;
    m[1] = "one";                    // 插入/修改
    m.emplace(2, "two");             // 高效插入
    m.insert({3, "three"});
    
    // 遍歷 (有序)
    for (const auto& [k, v] : m) { /* C++17 結構化綁定 */ }
    
    // 查找
    if (auto it = m.find(2); it != m.end()) { /* it->second */ }
    
    // multimap
    std::multimap<int, std::string> mm;
    mm.emplace(1, "a");
    mm.emplace(1, "b");
    auto range = mm.equal_range(1);  // 獲取所有 key=1 的元素
    for (auto it = range.first; it != range.second; ++it) { /* it->second */ }
    
    // 自定義排序 (降序)
    std::map<int, std::string, std::greater<>> desc_map;
}

容器選擇決策樹

需要關聯查找 (Key-Value)?
  ├─ Key 唯一 → std::map / std::unordered_map (哈希, O(1) 平均)
  └─ Key 可重複 → std::multimap / std::unordered_multimap

僅需存儲元素，頻繁查找/去重?
  ├─ 有序 → std::set / std::multiset
  └─ 無序 → std::unordered_set / std::unordered_multiset

序列容器選擇:
  ├─ 隨機訪問、尾部增刪為主 → std::vector
  ├─ 雙端增刪、固定大小、BFS → std::deque
  ├─ 中間頻繁增刪、迭代器穩定性要求高 → std::list
  └─ 棧/隊列/優先隊列 → std::stack / std::queue / std::priority_queue (適配器)

現代 C++ 最佳實踐 (C++11/14/17/20)

• 優先使用 emplace_back/emplace 避免臨時對象構造拷貝
• 範圍 for + 結構化綁定：for (auto& [k, v] : map)
• 異構查找 (C++14)：map.find("key") 直接用字符串字面量查 map<string, ...>，需比較器透明 std::less<>
• 節點提取/插入 (C++17)：node_type nh = map.extract(it); other_map.insert(std::move(nh)); 零拷貝轉移節點
• 並行算法 (C++17)：std::sort(std::execution::par, v.begin(), v.end())
• Ranges (C++20)：v | std::views::filter(...) | std::views::transform(...)

總結

STL 容器是 C++ 高效開發的基石。掌握各容器的底層數據結構、時間複雜度、迭代器失效規則、成員函數 vs 通用算法 的取捨，並結合現代 C++ 特性 (移動語義、emplace、結構化綁定、Ranges)，能編寫出既簡潔又高性能的代碼。實際項目中，建議：

1. 默認選 vector，除非有明確理由選其他
2. 關聯查找首選 unordered_map/set (需自定義哈希時用有序版)
3. 頻繁中間插刪且需迭代器穩定選 list
4. 利用算法替代手寫循環 (find_if, accumulate, transform, partition 等)
5. 注意 map::operator[] 的副作用，查找用 find/contains(C++20)