C++ STL list 容器完整指南：雙向鏈表操作詳解與迭代器失效避坑

list 核心特性

• 底層：雙向循環鏈表，每節點含 prev/next 指針
• 不支持隨機訪問（無 operator[]、at()），只能順序遍歷
• 任意位置插入/刪除 O(1)，只需調整指針
• 插入/刪除不會導致其他迭代器/引用/指針失效（除被刪除元素）
• 強異常安全：操作要么成功，要么無副作用

構造與賦值

list<int> c1;                    // 空
list<int> c2(c1);               // 拷貝構造
list<int> c3 = c1;              // 拷貝賦值
list<int> c4(std::move(c1));    // 移動構造 (C++11)
list<int> c5(5, 10);            // 5 個 10
list<int> c6(c1.begin(), c1.end()); // 區間構造
list<int> c7 = {1,2,3};         // 初始化列表 (C++11)

核心操作分類

1. 容量與訪問

c.empty(); c.size(); c.max_size();
c.front(); c.back();  // 首尾元素引用，無邊界檢查

2. 迭代器

c.begin(); c.end();           // 正向
c.rbegin(); c.rend();         // 反向
c.cbegin(); c.cend();         // const 正向 (C++11)
c.crbegin(); c.crend();       // const 反向 (C++11)

3. 元素修改：插入

c.insert(pos, val);           // pos 前插入 val，返回新元素迭代器
c.insert(pos, n, val);        // 插入 n 個 val
c.insert(pos, first, last);   // 插入區間 [first, last)
c.insert(pos, {1,2,3});       // 初始化列表 (C++11)
c.push_front(val); c.push_back(val);
c.emplace(pos, args...);      // 原地構造 (C++11)
c.emplace_front(args...); c.emplace_back(args...);

4. 元素修改：刪除

c.erase(pos);                 // 刪除 pos，返回下一個迭代器
c.erase(first, last);         // 刪除區間
c.pop_front(); c.pop_back();  // 刪除首尾，無返回值
c.clear();                    // 清空
c.remove(val);                // 刪除所有 == val
c.remove_if(pred);            // 刪除滿足謂詞的元素

5. 特有算法

c.sort();                     // 升序，O(N log N)
c.sort(comp);                 // 自定義比較
c.reverse();                  // 反轉
c.unique();                   // 刪除相鄰重複（需先 sort）
c.unique(pred);               // 自定義相等判斷
c.merge(c2);                  // 合併兩個已排序 list，c2 變空
c.merge(c2, comp);            // 自定義比較
c.splice(pos, c2);            // 將 c2 全部移至 pos 前，c2 變空
c.splice(pos, c2, it);        // 移動 c2 的 it
c.splice(pos, c2, first, last); // 移動 c2 區間
c.resize(n); c.resize(n, val); // 調整大小

迭代器失效鐵律（必背）

正確刪除遍歷模式（避坑指南）

// ✅ 正確：erase 返回下一個有效迭代器
for (auto it = lst.begin(); it != lst.end(); ) {
    if (shouldDelete(*it)) it = lst.erase(it);
    else ++it;
}

// ✅ 正確：後置 ++ 先保存舊值再遞增
for (auto it = lst.begin(); it != lst.end(); ) {
    if (shouldDelete(*it)) lst.erase(it++);
    else ++it;
}

// ❌ 錯誤：erase 後 it 已失效，再 ++ 未定義行為
for (auto it = lst.begin(); it != lst.end(); ) {
    if (shouldDelete(*it)) lst.erase(it);
    ++it;  // 危險！
}

原理：erase 返回下一個節點迭代器；it++ 返回舊值（遞增前），舊值雖被刪除但返回值已拷貝，安全。

list vs vector vs deque 選擇指南

總結

std::list 是穩定迭代器、O(1) 任意位置插刪的唯一標準容器。掌握 erase 返回值模式、splice 零拷貝移動、merge/sort/unique 成員算法，能在正確場景下發揮最大效能。記住：無隨機訪問、無容量概念、迭代器極其穩定是其核心特徵。