基本介紹

在 C++ 標準庫（STL）中，std::list 是一個基于雙向鏈表實現的序列容器。它與 std::vector、std::deque 等連續存儲容器不同，提供了在序列中高效插入和刪除元素的能力，尤其是在序列中間位置操作時優勢明顯。

---

1. std::list 的底層原理

std::list 是由一組雙向鏈表節點組成，每個節點包含：

• 元素數據本身

• 指向前一個節點的指針（prev）

• 指向后一個節點的指針（next）

整個鏈表通過節點指針串聯起來，頭節點的 prev 和尾節點的 next 通常指向特殊的哨兵節點或 nullptr。

結構示意

nullptr <- [Node1] <-> [Node2] <-> [Node3] -> nullptr

鏈表不保證元素在內存上的連續存儲，每個節點單獨分配內存。

---

2. 主要接口和用法

#include <list>
#include <iostream>int main() {std::list<int> lst = {1, 2, 3};// 頭部插入lst.push_front(0);// 尾部插入lst.push_back(4);// 插入到指定位置（通過迭代器）auto it = std::next(lst.begin(), 2);lst.insert(it, 99);// 遍歷for (auto val : lst) {std::cout << val << " ";}// 輸出: 0 1 99 2 3 4// 刪除元素lst.remove(99);// 清空lst.clear();return 0;
}

常用接口

• push_front / push_back?/ emplace_front?/ emplace_back：頭尾插入

• pop_front / pop_back：頭尾刪除

• insert：在指定位置插入元素

• erase：刪除指定位置元素

• remove / remove_if：刪除滿足條件的元素

• splice：將另一個鏈表的部分或全部節點移動到當前鏈表中（無需復制，效率極高）

• 雙向迭代器支持，允許雙向遍歷

---

3. 性能特征與對比

操作	std::list	std::vector	備注
插入/刪除頭尾	O(1)	頭部 O(n)，尾部 O(1)
插入/刪除中間	O(1) (有迭代器)	O(n)	list不需移動元素
隨機訪問	不支持（無 operator[]）	O(1)	list只能順序訪問
內存占用	較大（節點指針額外開銷）	較小，連續內存
緩存局部性	差	好	影響訪問效率

std::list 適合頻繁中間插入/刪除，且不需要隨機訪問的場景。

---

4. 典型使用場景

• 需要頻繁在序列中間插入、刪除元素，且已知具體位置的迭代器（如鏈表實現的任務隊列）

• 實現算法時需要快速拆分、合并鏈表（splice 功能）

• 保持迭代器或引用穩定，插入刪除時不會使其他元素迭代器失效（與 vector 不同）

---

5. 高級用法與優化建議

5.1 利用 splice 高效合并鏈表

splice 是 std::list 獨有且非常高效的操作。它允許將另一個鏈表的節點直接接入當前鏈表，避免拷貝和內存分配。

std::list<int> a = {1, 2, 3};
std::list<int> b = {4, 5, 6};// 將b的全部節點接入a的末尾，b變為空鏈表
a.splice(a.end(), b);

5.2 避免不必要的內存分配

每個節點都單獨分配內存，頻繁插入大量元素時可能導致性能瓶頸。可以考慮：

• 批量插入，減少頻繁的調用

• 在性能要求極高時，考慮自定義內存池

5.3 迭代器有效性保證

std::list 插入和刪除不會使其他節點的迭代器失效，適合要求迭代器長時間穩定的算法。

5.4 避免誤用

• 不要用 std::list 做需要隨機訪問的場景

• 不要為了“感覺好”就盲目使用鏈表，很多時候 std::vector 更優

---

6. 其他常用成員函數

size()：返回元素個數
empty()：判斷是否為空
assign(n, val)：賦值n個val
remove(val)：刪除所有等于val的元素
unique()：去除連續重復元素
reverse()：反轉鏈表
sort()：排序

7. 示例：LRU緩存

#include <list>
#include <unordered_map>
using namespace std;class LRUCache {
public:LRUCache(int capacity) : cap(capacity) {}int get(int key) {auto it = mp.find(key);if (it == mp.end()) return -1;cache.splice(cache.begin(), cache, it->second);return it->second->second;}void put(int key, int value) {auto it = mp.find(key);if (it != mp.end()) {it->second->second = value;cache.splice(cache.begin(), cache, it->second);} else {if (cache.size() == cap) {mp.erase(cache.back().first);cache.pop_back();}cache.emplace_front(key, value);mp[key] = cache.begin();}}private:int cap;list<pair<int, int>> cache;unordered_map<int, list<pair<int, int>>::iterator> mp;
};

---

8. 總結

• std::list 是雙向鏈表實現，支持高效插入刪除，迭代器穩定

• 犧牲了內存局部性和隨機訪問能力，不適合頻繁隨機訪問

• 適合需要頻繁中間操作或合并拆分鏈表的復雜算法

• 使用時要結合具體需求，避免濫用導致性能下降

• 利用高級接口如 splice 可實現高效鏈表操作