探索 List 的奧秘：自己動手寫一個 STL List?

📖引言

大家好！今天我們要一起來揭開 C++ 中?list?容器的神秘面紗——不是直接用 STL，而是親手實現一個簡化版的?list！🎉

你是不是曾經好奇過：

list?是怎么做到高效插入和刪除的？🔍
迭代器到底是怎么工作的？🔄
為什么?list?是雙向循環鏈表？🔗

在這篇博客中，我們將從零開始，一步步實現一個名為?amber::list?的模板類，包含：

? 雙向鏈表結構?list_node
? 迭代器?__list_iterator（支持?++、--、*、->）
? 常用接口：push_back、push_front、insert、erase、clear...
? 拷貝構造、賦值重載、初始化列表構造
? 異常安全的資源管理 🛡?

我們還會深入探討：

🧠 迭代器的設計哲學
🔄 雙向鏈表的插入與刪除邏輯
💡 模板編程中的技巧與陷阱

不管你是剛學完數據結構，還是想深入理解 STL 的實現，這篇博客都會讓你收獲滿滿！🌟

接下來，就讓我們一起進入?list?的世界吧！👇

在 list 的模擬實現中，我們一共會用到三個類，分別是?list_node，__list_iterator 和?list。我們需要多加關注的是如何利用c++的特性去模擬實現STL中的list（例如一個模板完成兩種迭代器的實現）。

list<T> │├── 包含多個 list_node<T> 節點│└── 提供 iterator 和 const_iterator│└── 由 __list_iterator<T, Ref, Ptr> 實現│└── 內部持有 list_node<T>* 用于遍歷

`1. list_node<T>`：鏈表節點類

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;explicit list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}
};

list_node<T>是鏈表節點類，用于list類的數據存儲。
這個類一共有三個成員對象，存儲數據的_data和用于指向前后節點的_prev和_next指針。

list_node構造函數初始化了一個階段存放了數據 x，這里的參數接口設計采用了c++的匿名對象和參數缺省值的語法，然后賦值給const修飾的T類型引用的x形參，缺省值用匿名對象有效的防止了創建節點時未傳參的情況。
如果沒傳參在會創建一個T類型的對象并且調用對應的默認構造，可以在不傳參構建一個節點（在用list創建的鏈表對象的哨兵位節點_head就采用了這一特性，哨兵位節點只用于找鏈表的頭與尾，不存儲有效數據）。
我們通過初始化列表，在將x賦值給_data后把_next和_prev指針都初始化為nullptr空指針。
然后我們explicit關鍵字修飾構造函數防止了隱式類型轉換，在編譯時能夠有效的發現代碼編寫錯誤。

`2. __list_iterator<T, Ref, Ptr>`：迭代器類

template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> Self;Node* _node;//迭代器構造函數__list_iterator(Node* node):_node(node){}//成員數據訪問運算符Ref operator*(){return _node->_data;//返回當前節點的數據類型對象}//自定義類型成員數據訪問運算符Ptr operator->(){return &_node->_data;}//前置++Self& operator++(){_node = _node->_next;//迭代器只想下一個節點return *this;//返回當前迭代器對象}//后置++Self operator++(int){Node* temp = _node;//創建一個臨時對象保存當前迭代器指向_node = _node->_next;//迭代器指向下一個節點return temp;//返回臨時對象}//前置--Self& operator--(){_node = _node->_prev;//迭代器指向當前節點的前一個節點return *this;//返回當前對象}//后置--Self operator--(int){Node* temp = _node;//創建一個臨時對象保存當前迭代器指向_node = _node->_prev;//迭代器指向當前節點的前一個節點return temp;//返回臨時對象}//不等于比較運算符bool operator!=(const Self& it) const{return _node != it._node;//兩個迭代器指向節點不相等返回true}//等于比較運算符bool operator==(const Self& it) const{return _node == it._node;//兩個迭代器指向節點相等返回true}
};

迭代器類采用了三個模版參數 數據類型T，數據對象引用?Ref 和 控制訪問權限參數 Ptr。
T：元素類型。
Ref：引用類型（T&?或?const T&）。
Ptr：指針類型（T*?或?const T*）。
該類有一個成員對象為_node，并且把list_node<T>類型和__list_iterator<T, Ref, Ptr>類型進行了typedef為Node和Self便于讀寫以及實現不同版本的迭代器iterator和常量迭代器const_iterator，由于兩種迭代器的實現僅僅只有類型的不同，所以我們通過一個迭代器模板就有效地減少了代碼的冗余，符合STL一貫的書寫習慣。

由于list鏈表在物理空間上的不連續性，無法通過簡單的typedef指針類型來進行迭代器模擬。
基于此原因，我們需要單獨把模擬實現的list的迭代器封裝到一個類里面，并且自主實現前置后置版本的++和--，以及比較運算符，以便于模擬迭代器的行為有助于list鏈表對象的遍歷。

->操作符

基于->操作符的特殊性，這里我們需要單獨講解一下->操作符：
//自定義類型成員數據訪問運算符Ptr operator->(){return &_node->_data;}
對于有多個成員的內置結構類型的指針,我們可以通過一次->訪問到其對應的成員，例如：
typedef struct student
{int score;int grade;
}student;student s1 = {99,1};
student* ps1 = &s1;//內置類型箭頭訪問操作
ps1->grade
而對于list的模板數據類型T也有可能是有多個成員的結構體類型或者類類型，我們就需要重載出對應的->訪問操作符，但這里要特殊強調的是編譯的底層理解。
void list_test_5()
{student s1 = { 100,1 };student* ps1 = &s1;std::cout << ps1->score << ps1->grade << std::endl;amber::list<student> slt;slt.push_back({ 99,4 });slt.push_back({ 98,5 });slt.push_back({ 97,6 });slt.push_back({ 96,7 });amber::list<student>::iterator sit = slt.begin();while (sit != slt.end()){std::cout << "{" << sit->grade << "," << (*sit).grade << "}" << " ";sit++;}std::cout << std::endl;
}
上面這段代碼實現了一個自定義結構體類型的list對象的遍歷和成員變量的訪問，其中 sit->
grade看似是調用了一次->操作符，但實際上從編譯器的角度來看是兩次，先調用了一次迭代器的重載，然后調用了內置類型的->操作符。
sit->grade│├── 第1次->：調用 sit.operator->()│     ↓│    返回 student* (指向真實數據)│└── 第2次->：對返回的指針使用 ->↓訪問真實的 grade 成員

3.?`list<T>`：鏈表容器類

template<class T>
class list
{typedef list_node<T> Node;
public:typedef __list_iterator<T, T&, T*> iterator;//迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;//常量迭代器iterator begin(){return iterator(_head->_next);//返回哨兵位的下一個節點（返回鏈表的頭節點）}iterator end(){return iterator(_head);//返回哨兵位節點}const_iterator begin() const{return const_iterator(_head->_next);//返回哨兵位的下一個節點（返回鏈表的頭節點）}const_iterator end() const{return const_iterator(_head);//返回哨兵位節點}//空鏈表初始化void empty_init(){_head = new Node;//new一個節點但不初始化賦值給哨兵位節點_head->_next = _head;_head->_prev = _head;//哨兵位的前后指針指向自己}//默認構造函數list(){empty_init();//調用空鏈表初始化}//拷貝構造函數list(const list<T>& lt){empty_init();//調用空鏈表初始化for (auto e : lt){push_back(e);//遍歷lt對象并逐個尾插到當前鏈表}}///初始化鏈表構造list(std::initializer_list<T> il){empty_init();//調用空鏈表初始化for (const auto e : il){push_back(e);//遍歷初始化鏈表的所有對象并逐個尾插到當前鏈表}}//成員交換函數void swap(list<T>& lt){std::swap(_head, lt._head);//調用std標準庫交換函數，交換哨兵位節點std::swap(_size, lt._size);//調用std標準庫交換函數，交換_size}//賦值運算符重載list<T>& operator=(list<T> lt){swap(lt);//創建一個形參lt并與當前對象交換return (*this);//返回當前對象}//析構函數~list(){clear();//清空鏈表delete _head;//回收哨兵位頭節點資源_head = nullptr;//置空}//鏈表清空void clear(){iterator it = begin();while (it != end()){it = erase(it);//遍歷鏈表并將成員逐個erase掉}}//尾插void push_back(const T& x){insert(end(), x);//復用指定位置插入}//頭插void push_front(const T& x){insert(begin(), x);//復用指定位置插入}//尾刪void pop_back(){erase(_head->_prev);//復用指定位置刪除}//頭刪void pop_front(){erase(_head->_next);//復用指定位置刪除}//指定位置插入iterator insert(iterator pos, const T& val){Node* cur = pos._node;//保存當前指定位置Node* newnode = new Node(val);//new一個新節點出來并用val初始化Node* prev = cur->_prev;//保存當前位置的前一個節點newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;_size++;//更新_sizereturn newnode;//返回新節點}//指定位置刪除iterator erase(iterator pos){if (_size == 0 || pos._node == _head){return end();//如果鏈表為空或者刪除頭節點時返回end()}Node* cur = pos._node;//保存當前指定位置Node* next = cur->_next;Node* prev = cur->_prev;if (prev != nullptr && next != nullptr)//確保前后指針的有效性{prev->_next = next;next->_prev = prev;//鏈接刪除位置的前后節點}delete cur;//刪除當前位置的節點_size--;//更新_sizereturn iterator(next);}//返回容量大小size_t size() const{return _size;}//全局友元交換函數friend void swap(list<T>& lhs, list<T>& rhs);private:Node* _head;//哨兵位節點size_t _size = 0;//節點數量
};// 在類外部定義友元函數模板
template<class T>
void swap(list<T>& lhs, list<T>& rhs) {lhs.swap(rhs);
}