C++ std::list 概念詳解

std::list 是 C++ 標準模板庫（STL）中的一個雙向鏈表容器。與 vector 和 array 不同，它不保證元素在內存中連續存儲，而是通過指針將各個元素連接起來。

核心特性

1. 雙向鏈表結構：
   • 每個元素包含指向前驅和后繼的指針
   • 支持雙向遍歷（前向和后向）
2. 時間復雜度：
   • 任意位置插入/刪除：O(1)
   • 隨機訪問：O(n)（效率低）
   • 排序：O(n log n)（使用成員函數 sort()）
3. 內存特性：
   • 非連續內存分配
   • 每個元素有額外指針開銷（前驅 + 后繼）
   • 不會導致迭代器失效（除被刪除元素）
4. 迭代器類型：
   • 雙向迭代器（支持 ++ 和 --）
   • 不支持隨機訪問（不能 + n）

---

常用成員函數

操作	函數	示例
插入元素	push_back()	list.push_back(10);
	push_front()	list.push_front(5);
	insert()	list.insert(it, 7);
刪除元素	pop_back()	list.pop_back();
	pop_front()	list.pop_front();
	erase()	list.erase(it);
訪問元素	front()	int first = list.front()
	back()	int last = list.back()
容量操作	size()	int len = list.size()
	empty()	if (list.empty()) ...
特殊操作	splice()	list1.splice(pos, list2)
	sort()	list.sort();
	merge()	list1.merge(list2);
	reverse()	list.reverse();

---

使用案例：訂單管理系統

#include <iostream>
#include <list>
#include <string>
#include <algorithm>// 訂單結構
struct Order {int id;std::string customer;double amount;Order(int i, std::string c, double a) : id(i), customer(c), amount(a) {}
};int main() {// 創建訂單鏈表std::list<Order> orders;// 添加訂單（三種方式）orders.push_back(Order(101, "Alice", 150.0));     // 尾部添加orders.emplace_back(102, "Bob", 99.99);           // 直接構造（C++11）orders.push_front(Order(100, "VIP", 500.0));      // 頭部添加// 在特定位置插入auto it = orders.begin();std::advance(it, 2);  // 移動到第三個位置orders.insert(it, Order(103, "Charlie", 75.5));// 遍歷并打印訂單（C++11范圍循環）std::cout << "All Orders:\n";for (const auto& order : orders) {std::cout << "ID: " << order.id << ", Customer: " << order.customer << ", Amount: $" << order.amount << "\n";}// 刪除特定訂單（金額<100）orders.remove_if([](const Order& o) {return o.amount < 100.0;});// 按金額升序排序orders.sort([](const Order& a, const Order& b) {return a.amount < b.amount;});// 新訂單批次std::list<Order> newOrders = {{201, "David", 200.0},{202, "Eva", 350.0}};// 合并訂單（到鏈表尾部）orders.splice(orders.end(), newOrders);// 遍歷打印最終訂單std::cout << "\nFinal Orders (Sorted & Merged):\n";for (const auto& order : orders) {std::cout << "ID: " << order.id << ", Customer: " << order.customer << ", Amount: $" << order.amount << "\n";}// 查找特定訂單auto findIt = std::find_if(orders.begin(), orders.end(), [](const Order& o) { return o.customer == "Eva"; });if (findIt != orders.end()) {std::cout << "\nFound Eva's order: $" << findIt->amount << "\n";}return 0;
}

輸出示例：

All Orders:
ID: 100, Customer: VIP, Amount: $500
ID: 101, Customer: Alice, Amount: $150
ID: 103, Customer: Charlie, Amount: $75.5
ID: 102, Customer: Bob, Amount: $99.99Final Orders (Sorted & Merged):
ID: 103, Customer: Charlie, Amount: $75.5
ID: 102, Customer: Bob, Amount: $99.99
ID: 101, Customer: Alice, Amount: $150
ID: 201, Customer: David, Amount: $200
ID: 202, Customer: Eva, Amount: $350
ID: 100, Customer: VIP, Amount: $500Found Eva's order: $350

---

關鍵操作詳解

1. 高效插入/刪除：

   // 在任意位置插入（O(1)）
   auto it = orders.begin();
   std::advance(it, 3);
   orders.insert(it, Order(105, "Frank", 120.0));// 刪除指定位置元素（O(1)）
   orders.erase(it);
   

2. 鏈表拼接：

   // 將list2的所有元素移動到list1的指定位置
   list1.splice(position, list2);// 移動list2中的單個元素
   list1.splice(pos, list2, elementIt);// 移動list2中的元素范圍
   list1.splice(pos, list2, startIt, endIt);
   

3. 專用排序算法：

   // 成員函數sort（比std::sort更高效）
   orders.sort(); // 默認使用operator<// 自定義排序
   orders.sort([](const Order& a, const Order& b) {return a.amount > b.amount; // 按金額降序
   });
   

4. 鏈表合并：

   // 合并兩個有序鏈表
   list1.merge(list2); 
   // 注意：合并后list2為空
   

---

性能對比（vs vector）

操作	std::list	std::vector
隨機訪問	O(n)	O(1)
頭部插入/刪除	O(1)	O(n)
尾部插入/刪除	O(1)	O(1) 攤銷
中間插入	O(1)	O(n)
內存連續性	否	是
內存開銷	高（指針）	低

---

最佳實踐

1. 適用場景：

   • 需要頻繁在任意位置插入/刪除
   • 不需要隨機訪問
   • 需要穩定迭代器（不失效）
   • 需要高效合并/拆分操作

2. 不適用場景：

   • 需要隨機訪問元素
   • 內存受限環境
   • 需要緩存友好的操作

3. 現代C++技巧：

   // 結構化綁定（C++17）
   for (const auto& [id, customer, amount] : orders) {std::cout << customer << ": $" << amount << "\n";
   }// 自定義內存分配器
   std::list<int, MyAllocator> customList;
   

---

經典應用場景

1. LRU緩存實現：使用鏈表+哈希表
2. 撤銷/重做功能：維護操作歷史
3. 消息隊列系統：高效插入/刪除
4. 圖算法：鄰接表表示
5. 多線程任務池：任務調度