本文首發於我的個人博客：Better Mistakes

版權聲明：本文為原創文章，轉載請附上原文出處鏈接及本聲明。
由於技術迭代較快，文章內容可能隨時更新（含勘誤及補充）。為了確保您看到的是最新版本，並獲得更好的代碼閲讀體驗，請訪問：

🍭 原文鏈接：https://bfmhno3.github.io/note/list-in-cpp/

在現代 C++ 開發中，雖然 std::vector 足以應付絕大多數的場景，但是在某些特定場景下，std::list 依舊是不可替代的神器。

核心概念與底層原理

• 頭文件：#include <list>
• 本質：雙向鏈表（Doubly Linked List）
• 內存模型：非連續內存。每個元素（節點）都是獨立分配在堆上的，節點之間通過指針（prev 和 next）連接
• 特點：
  • 不支持隨機訪問：不能使用下標 l[5] 訪問元素，必須從頭一個一個遍歷過去
  • 插入 / 刪除極快：只要持有了某個位置的迭代器，在該位置插入或刪除元素的操作是 \(O(1)\) 的，且不需要移動其他元素

初始化與構造

用法與 std::vector 非常相似：

#include <list>

std::list<int> l1;              // 空鏈表
std::list<int> l2 = {1, 2, 3};  // 列表初始化
std::list<int> l3(l2);          // 拷貝構造
std::list<int> l4(5, 100);      // 5 個 元素，全是 100

獨有的操作優勢（std::vector 做不到的）

這是 std::list 存在的理由。由於它是鏈表，它支持一些操作極其高效，或者提供了 std::vector 根本沒有的接口。

頭部操作

std::vector 在頭部插入 / 刪除操作極其低效（\(O(N)\)），而 std::list 則是瞬間完成（\(O(1)\)）。

• push_front(val)：頭部插入
• pop_front()：頭部刪除

接合（Splicing）

可以將一個 std::list 的元素（全部或部分）直接 “剪切” 並 “粘貼” 到另一個 std::list 中，這是純指針操作，沒有數據拷貝，所以速度極快。

std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};

auto it =  list1.begin();
++it; // 指向 2

// 將 list2 的所有元素 “移動” 到 list1 的 2 前面
// list2 變空，list1 變為 {1, 4, 5, 6, 2, 3}
list1.splice(it, list2);

專用成員函數

由於 std::list 無法隨機訪問，標準庫算法（如 std::sort）對它無效。因此 list 自帶了一套經過優化的成員函數：

• l.sort()：排序（穩定排序，底層通常是歸併排序）。注意：千萬別讀 std::list 用 std::sort(l.begin(), l.end())，編譯會報錯
• l.remove(val)：刪除所有等於 val 的元素
• l.remove_if(pred)：刪除滿足條件的元素
• l.unique()：刪除相鄰的重複元素（去重前通常要先 sort）
• l.reverse()：逆置鏈表
• l.merge(l2)：合併兩個已排序的鏈表（l2 會變空）

迭代器特性

這是決定選擇 std::vector 還是 std::list 的關鍵因素。

• 類型：雙向迭代器（Bidirectional Iterator）
  • 支持：++it、--it、*it
  • 不支持：it + 5，it < other_it（不能跳躍，不能比較大小）
• 穩定性（Validity）：極高
  • 摻入操作：絕對不會讓現有的迭代器失效
  • 刪除操作：只有指向被刪除節點的那個迭代器會失效，其他的完全不受影響
  • 對比 std::vector：std::vector 一旦擴容，所有迭代器全部失效；中間插入，後面所有迭代器失效。

std::list 和 std::vector 的選擇

這是一個經典的 Trade-off（權衡）問題：

結論：

• 95% 的情況用 std::vector：現代 CPU 的緩存機制非常依賴內存連續性。即使是在中間插入，對於小對象（如 int），std::vector 往往也比 std::list 快，因為 std::list 的遍歷會導致大量的 Cache Miss。
• 以下情況可以用 std::list：
  1. 需要頻繁在頭部或中間插入 / 刪除，且元素總數很多
  2. 對象非常大，拷貝代價極高（雖然 C++11 移動語義緩解了這個問題）
  3. 核心需求：你需要保存指向某個元素的迭代器，並且在後續操作中（無論怎麼插入刪除其他元素），希望這個迭代器一直有效

C++11 新增：std::forword_list

C++11 引入了 std::forword_list（單向鏈表）：

• 特點：只有 next 指針，沒有 prev 指針
• 優勢：比 std::list 更省內存（少存一個指針）
• 劣勢：只能向前遍歷，功能受限
• 場景：極其追求內存優化的哈希表桶實現等

📢 寫在最後

如果你覺得這篇文章對你有幫助，歡迎到我的個人博客 Better Mistakes 逛逛。

在那裏我歸檔了更多高質量的技術文章，也歡迎通過 RSS 訂閲我的最新動態！