?
目錄
一、接口函數和類總覽
二、節點結構體的實現
構造函數
三、迭代器結構體的實現
迭代器模版參數
構造函數
重載++運算符
重載--運算符
重載==運算符
重載*運算符
重載->運算符
四、list的模擬實現
默認成員函數
構造函數
拷貝構造函數
賦值運算符重載函數
析構函數
迭代器相關函數
訪問容器的相關函數
插入和刪除函數
insert
erase
push_back和pop_back
push_front和pop_front
其他函數
size
clear
empty
swap
一、接口函數和類總覽
我們想要實現list類，需要一個節點的結構體，一個迭代器結構體，還要有一個list類。
總覽：
#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <assert.h>namespace xywl {// 首先，我們需要一個節點類，帶模版參數的template<class T>struct list_node {T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()) : _data(data), _next(nullptr), _prev(nullptr) {}};// list的迭代器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*();Ptr operator->();Self& operator++();Self& operator--();Self& operator++(int);Self& operator--(int);bool operator!=(const Self& s) const;bool operator==(const Self& s) const;};// list類的實現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();iterator end();const_iterator begin() const;const_iterator end() const;void empty_init();list();list(std::initializer_list<T> in);list(const list<T>& t);list<T>& operator=(list<T> t);~list();void clear();void swap(list<T>& t);void push_back(const T& x);void push_front(const T& x);iterator insert(iterator pos, const T& x);void pop_back();void pop_front();iterator erase(iterator pos);size_t size() const;bool empty() const;Node* _head;size_t _size;};
}二、節點結構體的實現
我們首先要明確一點，就是我們實現的list類在底層是一個帶頭節點的雙向循環鏈表。所以我們實現節點的時候要有前驅和后繼指針。如圖：
所以我們在實現節點類的時候，就需要存儲如下幾個信息：數據，前驅節點的地址和后繼節點的地址。
所以說我們這個結構體只需要實現一個構造函數即可：
構造函數
這里我們默認給兩個指針傳入空指針，數據默認是指定類型的默認構造函數傳入的值：
template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()) : _data(data), _next(nullptr), _prev(nullptr) {}
};三、迭代器結構體的實現
我們這里就會十分好奇，之前我們也沒有單獨實現一個迭代器結構體，為什么這里要實現呢？
這是因為之前我們實現的string類和vector類都是在一個連續的空間里面的，我們可以通過原生的指針實現自增、自減和解引用的操作。但是我們實現list是鏈表，鏈表的節點在內存中的位置可是隨機的，我們不可能通過使用節點指針的自增和自減操作來實現對節點的數據進行操作的。所以我們這里需要實現迭代器結構體。
所以我們這里需要對于節點指針進行封裝，對于節點操作的各個運算符進行合理地重載。
迭代器模版參數
我們這里可以看到我們在實現迭代器結構體的模板參數列表中傳入了三個模板參數：
template<class T, class Ref, class Ptr>我們這里T就是我們數據類型，Ref（reference）是引用類型，Ptr（pointer）是指針類型。
同時我們的list類的模擬實現里面，有兩種迭代器類型：
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;我們這里之所以要實現兩種，是因為我們要滿足不同的使用需求。
我們還需要說明一下，我們在實現迭代器對象的時候也將參數模版重定義了：
typedef list_iterator<T, Ref, Ptr> Self;構造函數
我們這里實現的迭代器結構體實際上就是分裝了一個節點的指針，歸根到底還是對指針的操作。所以我們這里的構造函數的實現就是對于指針的賦值了：
list_iterator(Node* node):_node(node) {}重載++運算符
我們這里需要實現兩種++操作，分別是前置++和后置++：
前置++：
我們實現前置++就是返回自增后的數據，實現起來也非常簡單：
Self& operator++() {_node = _node->_next;return *this;
}后置++：
和前置++不同，我們需要返回++之前的值，所以我們需要用臨時變量先存儲一下我們的當前的對象的成員，然后再自增，最后返回那個臨時變量：
Self& operator++(int) {Self temp(*this);_node = _node->_next;return temp;
}重載--運算符
這里的邏輯和++雷同，也是實現兩個：
前置--：
Self& operator--() {_node = _node->_prev;return *this;
}后置--：
Self& operator--(int) {Self temp(*this);_node = _node->_prev;return temp;
}重載==運算符
我們使用等于的運算符的時候，只需要判斷這兩個迭代器是不是同一個位置的迭代器即可，也就是判斷迭代器中的指針的指向是不是相同的：
bool operator==(const Self& s) const {return _node == s._node;
}重載*運算符
我們使用借用的時候就是要獲取到這個位置的數據內容即可，也就是返回當前接待的指針所指向的數據即可：
Ref operator*() {return _node->_data;
}重載->運算符
我們在使用迭代器的時候有可能會使用到->運算符，比如我們的list容器存儲的類型不是內置類型而是自定義類型，我們在拿到了一個位置的迭代器的時候，就需要使用->來訪問成員：
Ptr operator->() {return &_node->_data;
}這里我們有可能會有一個疑問，就是我們重載了->符號，但是我們只是獲得了對應數據的地址，也就是說我們還要調用一次->符號才能獲取到正真的數據（第一個箭頭是調用了重載函數返回指針，第二個箭頭才是指針取訪問對象中的成員），但是事實上我們只需要使用一個箭頭，這是因為我們的編譯器做了識別處理，為了增加可讀性省略了一個箭頭，但是我們還是要明白這里的過程。
四、list的模擬實現
默認成員函數
構造函數
這里就是我們之前學習到的只是了，我們在創建一個雙向循環的鏈表的時候，初始化的狀態是申請了一個頭節點，然后讓這個節點的前驅指針和后繼指針都是指向自己的，如圖：
void empty_init() {_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}
list() {empty_init();
}注意：我們這里為了讓代碼更加美觀，就把初始化動作單獨封裝成了一個函數。
拷貝構造函數
這里的實現邏輯比較簡單，就是先初始化出來一個節點，然后我們遍歷傳進來的list的每一個節點，然后將這每一個節點都尾插到開始創建的對象里面：
list(std::initializer_list<T> in) {empty_init();for(auto& s : in) {push_back(s);}
}賦值運算符重載函數
我們的賦值運算符重載函數有兩種常見的寫法，這里和我們之前的string類的模擬實現可以說是一模一樣了：
寫法一：傳統寫法
這里的實現邏輯比較容易理解，就是先將原來的對象清空，然后將傳入的對象里面的數據一個一個的尾插到我們清空的對象里面：
lsit<T>& operator=(const list<T>& in) {if(this != &in) {clear();for(auto& s : in) {push_back(s);}}return *this;
}寫法二：現代寫法
這里也是用到了swap函數來進行操作，這種寫法的原理和之前是想string的原理如出一轍就不多說了。
list<T>& operator=(list<T> t) {swap(t);return *this;
}析構函數
析構函數就是將對象中的每一個節點都釋放，然后將頭節點置空即可：
?
~list() {clear();delete _head;_head = nullptr;
}迭代器相關函數
我們首先需要實現的就是獲取begin和end這兩個迭代器，我們根據帶頭雙向循環鏈表的基本定義，我們就可以知道begin就是頭節點的下一個節點，而我們的end就是最后一個有效數據的下一個節點也就是頭節點了。
iterator begin() {return _head->_next;
}
iterator end() {return _head;
}我們這里還需要實現一個const對象的相關函數：
const_iterator begin() const
{return _head->_next;
}
const_iterator end() const
{return _head;
}訪問容器的相關函數
我們這里主要是實現back和front這兩個函數，一個返回第一個有效數據，一個返回最后一個有效數據即可：
T& front() {return *begin();
}T& back() {return *(--end());
}插入和刪除函數
insert
這里的實現邏輯需要一些之前學習鏈表的知識了，為了簡化操作，我們可以保存住當前位置的指針和前驅指針，當然了如果你不嫌麻煩也可以不保存直接實現對應的邏輯，最后要返回新的節點的迭代器，我們可以根據下面的圖來嘗試：
iterator insert(iterator pos, const T& x) {Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;++_size;return newnode;
}erase
我們首先要建立沒有該位置節點的連接關系，然后刪除該節點，最后返回下一個位置的迭代器：
?
iterator erase(iterator pos) {assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;next->_prev = prev;prev->_next = next;delete pos._node;_size--;return next;
}push_back和pop_back
其實這里的兩個操作完全可以復用我們實現的insert函數和erase函數，也就是下面的代碼：
void push_back(const T& x) {insert(end(), x);
}
void pop_back() {erase(--end());
}push_front和pop_front
這里的實現也是可以完全的復用之前的insert和erase函數：
void push_front(const T& x) {insert(begin(), x);
}
void pop_front() {erase(begin());
}其他函數
size
我們這里就是要返回有效的數據個數，而我們在定義成員的就考慮到了這個情況，所以我們只需要返回_size：
size_t size() const {return _size;
}clear
這個函數就是清空對象中的節點的函數，我們只需要遍歷一遍，然后刪除每一個節點就行了：
void clear() {auto it = begin();while(it != end()) {it = erase(it);}
}empty
這個函數就是判斷是不是空，我們這里因為提前定義了_size，所以只需要判斷_size是不是空的：
?
bool empty() const {return _size == 0;
}swap
這個函數就是用來交換我們的頭節點指針和我們的有效數據個數的，我們這里需要在前面加上std::的作用域限定符，告訴編譯器我們是用的庫函數提供的swap而不是自己實現的：
void swap(list<T>& t) {std::swap(_head, t._head);std::swap(_size, t._size);
}五、總的實現代碼
#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <assert.h>namespace xywl {// 首先，我們需要一個節點類，帶模版的template<class T>struct list_node {T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()) : _data(data), _next(nullptr), _prev(nullptr) {}};// list的迭代器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--() {_node = _node->_prev;return *this;}Self& operator++(int) {Self temp(*this);_node = _node->_next;return temp;}Self& operator--(int) {Self temp(*this);_node = _node->_prev;return temp;}bool operator!=(const Self& s) const {return _node != s._node;}bool operator==(const Self& s) const {return _node == s._node;}};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 _head->_next;}iterator end() {return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const {return _head;}void empty_init() {_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list() {empty_init();}list(std::initializer_list<T> in) {empty_init();for(auto& s : in) {push_back(s);}}list(const list<T>& t) {empty_init();for(auto& s : t) {push_back(s);}}list<T>& operator=(list<T> t) {swap(t);return *this;}~list() {clear();delete _head;_head = nullptr;}void clear() {auto it = begin();while(it != end()) {it = erase(it);}}void swap(list<T>& t) {std::swap(_head, t._head);std::swap(_size, t._size);}void push_back(const T& x) {insert(end(), x);}void push_front(const T& x) {insert(begin(), x);}iterator insert(iterator pos, const T& x) {Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;++_size;return newnode;}void pop_back() {erase(--end());}void pop_front() {erase(begin());}iterator erase(iterator pos) {assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;next->_prev = prev;prev->_next = next;delete pos._node;_size--;return next;}size_t size() const {return _size;}bool empty() const {return _size == 0;}private:Node* _head;size_t _size;};
}
