? ? ? ? ?

づ?ど

?🎉?歡迎點贊支持🎉

個人主頁：勵志不掉頭發的內向程序員；

專欄主頁：C++語言；

---

前言

通過我們上一章節對 list 的學習，我們已經知道了 list 的成員函數和 vector 的相似之處和不同之處，此章節我們來嘗試模擬實現 list 類，比起 vector 的模擬實現會困難一些，但是大家肯定能夠克服困難搞明白 list 的。接下來一起來看看吧。

---

一、基本框架

list是由我們一個節點一個節點相互連接所構成的邏輯層面上連續的一個容器，所以如果想要實現這一結構，我們還得多創建一個鏈表節點的類以供我們鏈表能夠有節點去鏈接。

namespace zxl
{// 鏈表節點template <class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;};// 鏈表的主體template <class T>class list{typedef list_node<T> Node;public:private:Node* _head;size_t _size;};
}

二、構造函數

我們的構造分為四種，分別是無參構造、帶參構造、迭代器構造和拷貝構造。

我們的無參構造實現十分簡單，就是創建一個節點的空間后，把我們節點的 next 和 prev 都指向自己即可。

list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}

同時我們也要注意，我們節點如果想要創建也得初始化，所以也得有構造函數。

list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr)
{}

這樣我們在list中創建節點就會調用這個構造函數為我們節點初始化啦。

拷貝構造可以使用迭代器的循環遍歷去實現，但是在這之前我們得先給我們的要賦值的對象創建一個頭節點，也是哨兵位節點。

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}list(const list<T>& lt)
{empty_init();for (auto& e : lt){push_back(e);}
}

三、析構函數

析構主要就是從后往前一個節點一個節點的刪除，但是這里為了方便就直接使用我們的函數復用，用迭代器去循環erase即可。

~list()
{auto it = begin();while (it != end()){it = erase(it);}delete _head;_head = nullptr;
}

當然，我們上面的刪除其實就是clear的操作，我們可以先實現clear后再來函數復用就會是這樣。

~list()
{clear()delete _head;_head = nullptr;
}

四、賦值重載

我們直接把臨時變量相互交換即可。

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

五、增刪查改

5.1、push_front/push_back函數

頭插和尾插都比較簡單。

這就是尾插的方式，先創建出一個新的節點 newnode，然后再把它和 _head 的 prev 節點插入好，然后再和 _head 節點插入好即可。

void push_back(const T& x)
{Node* newnode = new Node(x);newnode->_next = _head;newnode->_prev = _head->_prev;_head->_prev->_next = newnode;_head->_prev = newnode;++_size;
}

當然，如果覺得這樣麻煩，我們可以直接把尾部節點保存起來，這樣就可以隨便插入了。

void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;++_size;
}

當然，如果我們實現了 insert 函數后可以直接函數復用也很方便。

void push_back(const T& x)
{insert(end(), x);
}

我們頭插和尾插差不多，只不過是我們把尾節點換成我們頭節點的下一個罷了。

void push_front(const T& x)
{Node* newnode = new Node(x);newnode->_next = _head->_next;_head->_next->_prev = newnode;_head->_next = newnode;newnode->_prev = _head;
}

這里只展示一種，剩下的大家可以自己嘗試。

5.2、pop_front/pop_back函數

頭刪和尾刪也不困難，我們如果實現了 erase 可以嘗試函數復用，但是如果沒有實現，我們可以把這些節點都保存下來，然后直接連接后刪除即可。

void pop_front()
{Node* cur = _head->_next;Node* next = cur->_next;_head->_next = next;next->_prev = _head;delete cur;--_size;
}

當然也可以直接函數復用。

void pop_front()
{erase(begin());
}

尾刪同理

void pop_back()
{Node* cur = _head->_prev;Node* prev = cur->_prev;_head->_prev = prev;prev->_next = _head;delete cur;--_size;
}

void pop_back()
{erase(--end());
}

5.3、insert函數

任意位置的插入和我們頭插和尾插沒有任何的不同，只是把我們的節點變化一下而已，但是我們得先實現迭代器才行，因為我們頭插的參數都是迭代器。

在這里我們直接保存 pos 的位置和它之前的位置的兩個節點，然后直接把 pos 插入到其中即可。

void insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;
}

5.4、erase函數

任意位置刪除也很容易，但是同樣得先實現迭代器才行。

void erase(iterator pos)
{assert(pos != end());Node* next = pos._node->_next;Node* prev = pos._node->prev;prev->_next = next;next->_prev = prev;delete pos._node;--_size;
}

六、其他成員函數

6.1、迭代器

我們 list 的迭代器實現起來較為復雜，首先 list 的物理邏輯上是不連續的，這也就意味著它的 ++/-- 不像原生指針那樣方便，list 的一個節點 ++ 后并不是下一個節點。所以我們得去單獨實現一個關于迭代器的類，我們可以通過對其類的內部進行函數重載去實現 ++ 后就到下一個類的效果。

我們此時在封裝一個list_iterator 類。

	template <class>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;// 這個類的成員函數Node* _node;// 這個類的無參構造// 到時候list中返回begin時// 就得構造我們的iteratorlist_iterator(Node* node): _node(node){ }};

我們可以看出這個類的主要架構就是如此，因為這個類主要就是去函數重載我們的迭代器，所以用struct 即可。而且我們后面要返回 list_iterator<T> 的類型，所以提前 typedef 簡化代碼，另外一個也是如此。

我們的 ++ 重載主要就是讓我們能夠成功的找到 list 的下一個節點，所以只要返回我們 node 的下一個節點即可。

Self& operator++()
{_node = _node->_next;return *this;
}

我們返回 Self 的原因是因為我們得連續的 ++，如果返回的是 Node 下一次就不能 ++ 了。因為不滿足我們重載的參數，也就是隱藏的 this 指針。所以我們返回的就是 Self 了，引用則是可能有要修改的請求。

我們 -- 的重載也和 ++ 相似，就是把 next 變成 prev 即可。

Self& operator--()
{_node = _node->_prev;return *this;
}

解引用主要是返回我們的 data 的數據，而且要可以修改，所以我們就返回 T& 即可。

T& operator*()
{return _node->_data;
}

還有 == 和 != 的運算符重載，這兩個是在循環時判斷是不是到 end 時使用的。

bool operator==(const Self& s)
{return _node == s._node;
}bool operator!=(const Self& s)
{return _node != s._node;
}

這就是我們所需要的 list 迭代器的運算符重載，有了這個重載，我們就可以在我們 list 的類中實現我們的有關迭代器的函數了。

	template <class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T> iterator;iterator begin(){// 可以有名對象//iterator it(_head->_next);//return it;// 也可以匿名對象return iterator(_head->_next);}iterator end(){return terator(_head);}
};

這樣就可以實現我們的迭代器了。

我們嘗試著運行看看。

int main()
{zxl::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);zxl::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

成功打印出來了。這里我們就可以看出來我們上層看上去循環遍歷都是從 begin 一直 ++ 到 end，但是底層確實天差地別。

我們可以繼續來完善這個迭代器，我們已經實現了前置 ++/-- 了，現在可以嘗試來實現后置 ++/--。

Self& operator++(int)
{Self tmp(*this);_node = _node->_next;return tmp;
}Self& operator--(int)
{Self tmp(*this);_node = _node->_prev;return tmp;
}

在這里創建了 tmp，運用的是拷貝構造，但是我們沒有實現拷貝構造，那我們的系統就會對我們的內置類型進行值拷貝，我們的成員函數是 Node* 的指針，那我們到底要不要去實現拷貝構造呢？其實我們這里沒有必要去實現，如果我們不實現拷貝構造，我們的 tmp 和我們 *this 就是指向同一個 _node 空間的，但是由于我們的節點是由鏈表管理的，而不是我們 *this 管理，所以當我們_node 離開時并不會去銷毀我們的空間，同時，我們的 tmp 所指向的空間本就是我們所希望的空間，所以在這里淺拷貝就好了。

我們迭代器所指向的資源并不是屬于它的資源，也可以解釋為什么這里可以用淺拷貝而不用實現拷貝構造。同時也不用寫析構了。

我們接著來看下面這串代碼。

struct AA
{int a1 = 1;int a2 = 1;
};int main()
{zxl::list<AA> a;a.push_back(AA());a.push_back(AA());a.push_back(AA());a.push_back(AA());zxl::list<AA>::iterator it = a.begin();while (it != a.end()){cout << (*it).a1 << " " << (*it).a2 << endl;it++;}return 0;
}

當我們的list創建一個類類型的變量時，如果我們要打印就比較麻煩，因為我們 it 是類類型的指針，所以得先解引用在去用 . 來去打印。這里有2種優化方法，第一種就是給我們AA的流輸出運算符重載一下，但是如果換一個類時又得重載，還有一個就是在迭代器中重載一個 -> 符。

T* operator->()
{return &_node->_data;
}

這樣就可以完成我們箭頭的工作了。

while (it != a.end())
{cout << it->a1 << " " << it->a2 << endl;it++;
}

但是有人會覺得這里很奇怪，為什么箭頭是這樣實現的？其實我們這里少了一個箭頭，它本質上是有兩個箭頭在這里的。把代碼改成這樣你就一定可以理解了。

while (it != a.end())
{cout << it.operator->()->a1 << " " << it.operator->()->a2 << endl;it++;
}

這個時候我們先返回類的指針后就可以用類的箭頭的操作了，但是為了美觀和可讀性，我們便省略了后面的箭頭，所以就是第一次那種樣子啦。

實現了普通迭代器后，我們來嘗試實現const迭代器。首先我們知道const迭代器的特點就是不能修改，所以我們只要對我們迭代器的 * 運算符和 -> 運算符重載時加入 const 即可。

template <class T>
struct list_const_iterator
{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node): _node(node){}Self& operator++(){_node = _node->_next;return *this;}Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}const T& operator*(){return _node->_data;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}const T* operator->(){return &_node->_data;}
};

這就是我們的反向迭代器，再在list中 typedef list_const_iterator const_iterator 即可。

這樣確實可是實現我們的const，但是我們會發現有大量的代碼重復，看上去就沒必要，因為只有兩個代碼是不同的，其余的都是相同代碼。那我們有沒有什么辦法把它們揉在一起呢？答案就是模板，模板可以讓編譯器去做重復的工作。那我們該怎么操作呢？

我們仔細觀察可以發現我們const迭代器和普通迭代器的差別無非就是一個是 T*/T&，而另一個是 const T*/const T&，所以我們可以創建一個模板，它有3個模板變量，

template <class T, class Ref, class Ptr>
struct list_iterator
{};

我們list是這樣傳參的

class list
{
public:typedef list_iterator<T, T&, T*> iterator;typedef list_const_iterator<T, const T&, const T*> const_iterator;
};

這就是我們模板的用法，此時我們傳不同的參數進去就會實例化出不同的對象，本質上就是我們上面寫兩個的情況讓我們編譯器自己去做了。

我們只要把剛才用到 T/T&/T* 用我們 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){ }Self& operator++(){_node = _node->_next;return *this;}Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Ref operator*(){return _node->_data;}bool operator==(const Self& s){return _node == s._node;}bool operator!=(const Self& s){return _node != s._node;}Ptr operator->(){return &_node->_data;}
};

這樣就完成了我們的模板實現。

我們接著來看看我們迭代器失效的問題，我們現在在任意位置插入后修改數據會不會迭代器失效呢？

int main()
{zxl::list<int> a;a.push_back(1);a.push_back(2);a.push_back(3);a.push_back(4);zxl::list<int>::iterator it = a.begin();it++;it++;a.insert(it, 10);*it *= 10;for (auto x : a){cout << x << ' ';}cout << endl;return 0;
}

我們來看看我們 it 的位置有沒有改變，3有沒有變成30。

很顯然，迭代器沒有失效，這是因為vector在插入數據時會平移數據而導致我們 it 所指向的空間數據發生了改變，但是我們list確實插入數據，它本身空間不連續，我們插入數據時 it 更不會改變了。所以迭代器不會失效。

我們erase刪除數據會導致迭代器失效，這是因為它刪除后所指向的空間已經給銷毀了，是野指針了，所以會失效。

我們可以讓我們的erase函數返回我們下一個迭代器，這樣我們用一個值記錄下來就可以實現連續的刪除了。

iterator erase(iterator pos)
{assert(pos != end());Node* next = pos._node->_next;Node* prev = pos._node->_prev;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;
}

所以迭代器到底失不失效得看容器的結構，我們默認它失效即可。

6.2、size函數

size_t size()
{return _size;
}

6.3、empty函數

bool empty()
{return _size == 0;
}

6.4、clear函數

它和析構函數很像，也是把所有節點都銷毀。

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

---

總結

以上便是我們list的主要內容啦，其實模擬實現并不難，主要的難點就在于實現迭代器，它和之前直接用原生指針的容器有很大的區別。大家可以慢慢研究了解，大家加油。

🎇堅持到這里已經很厲害啦，辛苦啦🎇

? ? ? ? ?

づ?ど