先看代碼，常用的就是代碼中有的那些
#include <bits/stdc++.h>
using namespace std;
int main() {list<int> mylist;for(int i=0;i<5;i++){mylist.push_back(i);//TODO}for(const auto&i:mylist)cout<<i<<'\n';//fanzhuanreverse(mylist.begin(),mylist.end());cout<<" //fanzhuan\n ";for(const auto&i:mylist){cout<<i<<'\n'; //TODO}mylist.insert(++mylist.begin(),9);cout<<" //插入\n ";for(const auto&i:mylist){cout<<i<<'\n'; //TODO} mylist.erase(++ mylist.begin(),--mylist.end());//刪除了一個區間的數cout<<"size"<<mylist.size()<<'\n';for(const auto&i:mylist){cout<<i<<'\n'; //TODO} return 0;}- List的核心操作：如push_back, push_front, pop_back, pop_front等。
- 迭代器使用：如何遍歷list，不同迭代器的區別（正向、反向）。
- 容量與大小管理：size(), empty(), clear()等方法，以及與vector在內存管理上的對比。
- 元素訪問：通過迭代器和下標訪問的效率差異，at()方法的使用。
- 插入與刪除操作：在特定位置插入或刪除元素的效率，erase方法的不同用法。
- 自定義類型支持：如何存儲對象，需要重載哪些運算符。
- 性能比較：list在插入刪除時的優勢，以及隨機訪問的劣勢。
- 實際應用案例：比如實現棧、隊列，或者作為鏈表結構的使用場景。
一、核心成員函數詳解（修正拼寫錯誤后）
| 函數名稱 | 功能說明 | 示例代碼 | 注意事項 |
|---|---|---|---|
push_back() | 在鏈表尾部插入元素 | lst.push_back(10); | 時間 O(1) |
push_front() | 在鏈表頭部插入元素 | lst.push_front(20); | 時間 O(1) |
pop_back() | 移除鏈表尾部元素 | lst.pop_back(); | 空容器調用會崩潰 |
pop_front() | 移除鏈表頭部元素 | lst.pop_front(); | 同上 |
size() | 返回鏈表元素個數 | int n = lst.size(); | O(1) |
empty() | 檢查鏈表是否為空 | if (lst.empty()) {...} | O(1) |
clear() | 清空所有元素 | lst.clear(); | O(n) |
front() | 獲取第一個元素的引用 | int x = lst.front(); | 空容器調用崩潰 |
back() | 獲取最后一個元素的引用 | int y = lst.back(); | 同上 |
begin() | 返回首元素的迭代器 | auto it = lst.begin(); | |
end() | 返回尾元素后繼的迭代器 | auto rit = lst.rbegin(); | |
insert(pos, val) | 在位置 pos 前插入元素 | lst.insert(lst.begin()+1, 30); | 時間 O(n) |
erase(pos) | 刪除位置 pos 的元素 | lst.erase(lst.begin()+1); | 同上 |
二、常用擴展函數（圖片未提及）
| 函數名稱 | 功能說明 | 示例代碼 |
|---|---|---|
emplace_back(val) | 在尾部直接構造元素（比 push_back 更高效） | lst.emplace_back(100); |
splice(pos, other) | 將另一個鏈表的元素插入到當前位置 | lst.splice(it, other_lst); |
merge(other) | 合并兩個有序鏈表（保持有序性） | auto merged = merge(&a, &b); |
remove(val) | 刪除所有等于 val 的元素 | lst.remove(5); |
reverse() | 反轉鏈表順序 | lst.reverse(); |
assign(range) | 用區間內的元素覆蓋當前鏈表 | lst.assign(arr.begin(), arr.end()); |
三、安全操作示例
#include <iostream>
#include <list>
using namespace std;int main() {list<int> lst;// 安全插入lst.push_back(1);lst.push_front(2);// 避免空容器操作if (!lst.empty()) {cout << "首元素: " << lst.front() << endl; // 輸出 2cout << "末元素: " << lst.back() << endl; // 輸出 1}// 使用迭代器安全刪除if (lst.size() > 0) {auto it = lst.begin();lst.erase(it); // 刪除第一個元素}return 0;
}
四、list vs vector 對比分析
| 特性 | list（雙向鏈表） | vector（動態數組） |
|---|---|---|
| 內存分配 | 分散的內存塊（指針開銷大） | 連續內存塊（緊湊存儲） |
| 插入/刪除效率 | 頭部 O(1)，中間 O(1)（已知位置） | 頭部 O(n)，中間 O(n) |
| 隨機訪問 | O(n)（需遍歷） | O(1)（直接索引） |
| 內存占用 | 較高（每個節點存儲指針） | 較低（僅存儲數據） |
| 迭代器失效性 | 僅被刪除元素的迭代器失效 | 所有迭代器可能失效（擴容時） |
| 適用場景 | 頻繁插入/刪除元素 | 頻繁隨機訪問元素 |
1. 實現LRU緩存（基于list和unordered_map）
#include <list>
#include <unordered_map>
using namespace std;template<typename K, typename V>
class LRUCache {
private:list<pair<K, V>> cache; // 按訪問順序排列unordered_map<K, typename list<pair<K, V>>::iterator> pos_map;size_t capacity;public:LRUCache(size_t cap) : capacity(cap) {}void get(K key) {auto it = pos_map.find(key);if (it == pos_map.end()) return;// 將節點移到頭部（最近使用）cache.splice(cache.begin(), cache, it->second);}void put(K key, V value) {auto it = pos_map.find(key);if (it != pos_map.end()) {// 更新值并移到頭部it->second->second = value;cache.splice(cache.begin(), cache, it->second);} else {if (cache.size() >= capacity) {// 刪除末尾元素（最久未使用）auto last = cache.end();--last;pos_map.erase(last->first);cache.pop_back();}// 插入新節點到頭部auto newNode = cache.emplace_front(key, value);pos_map[key] = newNode;}}
};
2. 雙向鏈表反轉
void reverse_list(list<int>& lst) {auto it1 = lst.begin();auto it2 = lst.end();while (it1 != it2) {swap(*it1, *it2);++it1;--it2;}
}
二、核心內容架構
1. 雙向鏈表節點的底層實現
? 節點結構體解析：
template<typename T>
struct Node {T data; // 存儲元素Node* prev; // 前驅指針Node* next; // 后繼指針Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};
? 內存分配策略：
? 節點池技術：預分配內存塊減少動態分配開銷
? 分配器模式：與vector不同的allocator實現（如__gnu_pbds::node_allocator）
2. 關鍵成員函數源碼剖析
? 構造函數：
list() : head(nullptr), tail(nullptr), size(0) {} // 空鏈表初始化
list(initializer_list<T> il) { ... } // 包含初始化列表的構造
? 動態擴容機制：
? 無需擴容：鏈表結構支持O(1)時間復雜度的頭尾插入/刪除
? 迭代器失效性：只有被刪除元素的迭代器會失效，其他迭代器保持有效
3. 高效操作實現原理
? push_back()：
void push_back(const T& val) {Node* newNode = allocator.allocate(1);allocator.construct(newNode, val);if (empty()) {head = tail = newNode;} else {tail->next = newNode;newNode->prev = tail;tail = newNode;}++size;
}
? insert(pos, val)：
? 定位節點：雙向鏈表支持O(n)時間復雜度定位
? 指針調整：四步操作（新節點創建→前后指針重新鏈接）
4. 與vector的對比實驗
| 操作 | list | vector |
|---|---|---|
| 頭部插入 | O(1) | O(n) |
| 中間插入 | O(1)（已知位置） | O(n) |
| 隨機訪問 | O(n) | O(1) |
| 內存占用 | 較高（指針開銷） | 較低（緊湊存儲） |
| 適用場景 | 頻繁插入/刪除 | 頻繁隨機訪問 |
三、代碼示例與調試
1. 實現鏈表反轉（迭代器版）
void reverse_list(list<int>& lst) {auto it1 = lst.begin();auto it2 = lst.end();while (it1 != it2) {swap(*it1, *it2);++it1;--it2;}
}
2. 模擬LRU緩存淘汰算法
#include <list>
#include <unordered_map>template<typename K, typename V>
class LRUCache {
private:list<pair<K, V>> cache; // 按訪問順序排列unordered_map<K, typename list<pair<K, V>>::iterator> pos_map;size_t capacity;public:LRUCache(size_t cap) : capacity(cap) {}void get(K key) {auto it = pos_map.find(key);if (it == pos_map.end()) return;// 將訪問的節點移到鏈表頭部cache.splice(cache.begin(), cache, it->second);}void put(K key, V value) {auto it = pos_map.find(key);if (it != pos_map.end()) {// 存在則更新值并移動到頭部it->second->second = value;cache.splice(cache.begin(), cache, it->second);} else {if (cache.size() >= capacity) {// 淘汰末尾元素auto last = cache.end();--last;pos_map.erase(last->first);cache.pop_back();}// 插入新節點到頭部auto newNode = cache.emplace_front(key, value);pos_map[key] = newNode;}}
};
四、進階知識點
1. 內存泄漏檢測技巧
? 使用Valgrind工具檢測鏈表節點泄漏：
valgrind --leak-check=yes ./a.out
2. 自定義內存池優化
template<typename T>
class FastList : public std::list<T> {
private:struct Pool {T* buffer;size_t capacity;Pool(size_t cap) : capacity(cap) {buffer = static_cast<T*>(malloc(cap * sizeof(T)));}~Pool() { free(buffer); }};Pool pool(1024); // 預分配1024個節點// 重載allocatorusing allocator_type = typename std::list<T>::allocator_type;allocator_type alloc;public:FastList() : std::list<T>(alloc), pool(1024) {this->allocator = alloc; // 綁定自定義分配器}
};
五、學習建議
-
配套書籍推薦：
? 《Effective STL》Item 10：選擇合適的容器
? 《C++ Primer》第16章：鏈表容器詳解 -
實驗環境配置：
g++ -std=c++17 -Wall -Wextra list_exercise.cpp -o list_exercise -
常見錯誤總結：
? 誤用operator[]訪問鏈表（僅vector支持隨機訪問）
? 忘記釋放自定義分配的內存（內存泄漏）
? 在迭代器失效后繼續操作（未理解鏈表結構特性）
)
