?
目錄
一，實(shí)現(xiàn)list所需要包含的三個(gè)類
二，三個(gè)類的實(shí)現(xiàn)
1.list_node
2.list類
?3.iterator_list類
三，功能實(shí)現(xiàn)
1.list類里的push_back()
??2.iterator類里的運(yùn)算符重載
3，list類里面的功能函數(shù)
1.insert（）
2.erase()函數(shù)
3.clear()與析構(gòu)函數(shù)
4.拷貝構(gòu)造函數(shù)賦值運(yùn)算符重載
5.打印函數(shù)
一，實(shí)現(xiàn)list所需要包含的三個(gè)類
? ? ?因?yàn)閘ist是一個(gè)帶頭雙向循環(huán)鏈表。所以list的實(shí)現(xiàn)會(huì)比較的復(fù)雜一些?？偟脕?lái)說(shuō)，實(shí)現(xiàn)一個(gè)雙向帶頭循環(huán)鏈表需要構(gòu)造三個(gè)類。1.list類，2.list_node類，3.list_iterator類。前兩個(gè)類相信大家會(huì)比較的熟悉。第三個(gè)類大家會(huì)比較不熟悉，因?yàn)樗且粋€(gè)迭代器的類。也就是說(shuō)這個(gè)類是迭代器的封裝。它的實(shí)現(xiàn)很有價(jià)值，因?yàn)樗茏屛覀冊(cè)谑褂胠ist時(shí)也可以像之前的數(shù)據(jù)結(jié)構(gòu)一樣方便。
二，三個(gè)類的實(shí)現(xiàn)
1.list_node
?這首先要實(shí)現(xiàn)的便是節(jié)點(diǎn)類。這個(gè)類是最容易實(shí)現(xiàn)的。這個(gè)類的作用便是給要產(chǎn)生的節(jié)點(diǎn)畫一個(gè)圖，定義一下這個(gè)節(jié)點(diǎn)的結(jié)構(gòu)和類型。代碼如下：
template<class T>//模板 struct list_node { list_node(const T& val =T()//匿名對(duì)象 )//構(gòu)造函數(shù)起初始化的作用 :val(val) , prev(nullptr) , next(nullptr) {} T val; list_node<T>* prev; list_node<T>* next; };現(xiàn)在你看到了，這個(gè)節(jié)點(diǎn)的結(jié)構(gòu)便是這樣。其實(shí)這與之前實(shí)現(xiàn)的那個(gè)帶頭雙向循環(huán)鏈表的結(jié)構(gòu)差不多。不過(guò)，在cpp中引入了模板的概念，所以這個(gè)節(jié)點(diǎn)便可以調(diào)用模板參數(shù)來(lái)進(jìn)行泛化。
2.list類
list類的定義可太簡(jiǎn)單了。list的成員變量只有一個(gè)參數(shù)，便是_head。這是哨兵位的頭節(jié)點(diǎn)。當(dāng)然還有一個(gè)無(wú)參的構(gòu)造函數(shù)和一個(gè)功能函數(shù)。代碼如下：
template<class T> class list { public: typedef list_node<T> Node; void empty()//初始化功能函數(shù)。 { _head = new Node; _head->prev = _head; _head->next = _head; } list()//構(gòu)造函數(shù) { empty(); } private: Node* _head; };當(dāng)然，這里的list類也是要用模板來(lái)進(jìn)行泛化的。
?3.iterator_list類
這個(gè)類就算是比較復(fù)雜的一個(gè)類了。因?yàn)榈饕獙?shí)現(xiàn)兩種重載版本：1.普通版本。2.const版本。所以迭代器類的模板參數(shù)會(huì)有三個(gè)：
template <class T, class Ref, class ptr>這三個(gè)模板參數(shù)會(huì)重載兩種版本的三個(gè)參數(shù)：T對(duì)象，T&，T指針類型。在這個(gè)類里面也只有一個(gè)成員：_node。類型與list類里面的成員類型相同。該類代碼如下：
template <class T, class Ref, class ptr> struct iterator_list { typedef list_node<T> Node; iterator_list(Node* node) :_node(node) {} Node* _node; };
三，功能實(shí)現(xiàn)
1.list類里的push_back()
首先來(lái)實(shí)現(xiàn)一個(gè)push_back()函數(shù)，這個(gè)函數(shù)的作用便是實(shí)現(xiàn)尾插數(shù)據(jù)。邏輯十分簡(jiǎn)單，代碼如下：
void push_back(const T& val) { Node* newnode = new Node(val); Node* tail = _head->prev; tail->next = newnode; newnode->prev = tail; newnode->next = _head; _head->prev = newnode; }寫完這個(gè)以后，我便想要通過(guò)顯示list里的數(shù)據(jù)來(lái)驗(yàn)證答案，但是很顯然，我們做不到。因?yàn)閘ist是一個(gè)自定義的類。但是我們有辦法，所以我們便可以通過(guò)iterator來(lái)達(dá)到這個(gè)目的。所以我們必須在iterator類里面實(shí)現(xiàn)幾個(gè)運(yùn)算符重載。
??2.iterator類里的運(yùn)算符重載
首先先實(shí)先這三個(gè)運(yùn)算符重載：1.*，2.++，3.！=
代碼如下：
Ref operator *()//Ref代表T& { return _node->val; } self operator++() { _node = _node->next; return *this; } bool operator!=(self& it) { return _node != it._node; }然后再在list類里面實(shí)現(xiàn)begin()與end()函數(shù)之后便可以實(shí)現(xiàn)范圍for的使用了，end與begin代碼如下：
//實(shí)現(xiàn)兩個(gè)版本的begin與end iterator begin() { return _head->next; } iterator end() { return _head; } const_iterator begin()const { return _head->next; } const_iterator end()const { return _head; }在實(shí)現(xiàn)了上面的代碼以后，為了讓迭代器的功能更加全面，那我們?cè)賹?shí)現(xiàn)幾個(gè)函數(shù)重載。再iterator_list里面的全部運(yùn)算符重載如下：
Ref operator *() { return _node->val; } self& operator++()//前置++ { _node = _node->next; return *this; } self operator++(int)//后置++ { Node* tmp(*this); _node = _node->next; return tmp; } self& operator --()//前置-- { _node = _node->prev; return *this; } self operator--(int)//后置-- { Node* tmp(*this); _node = _node->prev; return tmp; } bool operator!=(const self& it)//若用引用便要加上const { return _node != it._node; } bool operator==(self& it) { return _node == it._node; } self& operator+(int n) { while (n) { _node = _node->next; n--; } return *this; } ptr operator->()//箭頭解引用 { return &_node->val; }在實(shí)現(xiàn)了這些運(yùn)算符重載以后，list類里面的功能函數(shù)便好寫了許多。
3，list類里面的功能函數(shù)
1.insert（）
這個(gè)函數(shù)實(shí)現(xiàn)的功能便是在pos位置之前插入一個(gè)新的節(jié)點(diǎn)。這個(gè)pos的類型是迭代器類型。在list類里邊的迭代器重定義為：
typedef iterator_list<T, T& ,T*> iterator; typedef iterator_list<T, const T&, const T*> const_iterator;我們只需要關(guān)注第一個(gè)迭代器即可，因?yàn)榈诙€(gè)迭代器修飾的對(duì)象是不可以修改的。所以insert的實(shí)現(xiàn)代碼如下：
iterator insert(iterator pos, const T& x)//在pos位置之前插入新節(jié)點(diǎn) { Node* newnode = new Node(x); Node* prev = pos._node->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos._node; pos._node->prev = newnode; return pos._node->prev;//防止迭代器失效，所以返回pos的前一個(gè)位置 }檢驗(yàn)一下，檢驗(yàn)代碼如下：
void test_list2() { list<int> l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); l1.push_back(5); for (auto e : l1) { cout << e << " "; } cout << endl; l1.insert(l1.begin(), 9); l1.insert(l1.end(), 99); for (auto e : l1) { cout << e << " "; } cout << endl; }結(jié)果：正確
?在實(shí)現(xiàn)了insert（）函數(shù)以后便可以復(fù)用實(shí)現(xiàn)push_back()與push_front()。代碼如下：
void push_back(const T& val) { insert(begin(), val); } void push_front(const T& val) { insert(end(), val); }
2.erase()函數(shù)
erase()函數(shù)實(shí)現(xiàn)的功能便是傳入一個(gè)位置，然后將該位置上的節(jié)點(diǎn)刪除掉。代碼實(shí)現(xiàn)如下：
iterator erase(iterator pos) { Node* prev = pos._node->prev; Node* next = pos._node->next; Node* cur = pos._node; delete cur; prev->next = next; next->prev = prev; return iterator(next);//返回新的迭代器 }復(fù)用erase實(shí)現(xiàn)尾刪與頭刪，代碼如下：
? void pop_back() { erase(--end());//尾巴是--end()的位置 } void pop_front() { erase(begin()); } ?實(shí)驗(yàn)代碼：
void test_list3() { list<int> l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); l1.push_back(5); for (auto e : l1) { cout << e << " "; } cout << endl; l1.insert(l1.begin(), 9); l1.insert(l1.end(), 99); for (auto e : l1) { cout << e << " "; } cout << endl; l1.pop_back(); l1.pop_front(); for (auto e : l1) { cout << e << " "; } cout << endl; }結(jié)果：正確
3.clear()與析構(gòu)函數(shù)
實(shí)現(xiàn)了erase()函數(shù)以后再接再厲，接著復(fù)用實(shí)現(xiàn)clear函數(shù)，代碼如下：
void clear() { iterator it = begin(); while (it != end()) { it = erase(it);//erase()每次都會(huì)返回下一個(gè)位置 } }從上面代碼的邏輯便可以看出clear()函數(shù)是不會(huì)刪除掉頭節(jié)點(diǎn)的。但是析構(gòu)函數(shù)需要。于是復(fù)用clear()函數(shù)后析構(gòu)函數(shù)代碼如下：
~list() { clear(); delete _head; }
4.拷貝構(gòu)造函數(shù)賦值運(yùn)算符重載
拷貝構(gòu)造函數(shù)實(shí)現(xiàn)過(guò)程大概分三步，首先new出來(lái)一個(gè)空間。然后再?gòu)?fù)用push_back()函數(shù)將要賦值的數(shù)據(jù)拷貝到新節(jié)點(diǎn)內(nèi)。實(shí)現(xiàn)代碼如下：
list(const list<T>& l1) { empty(); for (auto e : l1) { push_back(e); } }實(shí)現(xiàn)了拷貝構(gòu)造以后，按照慣例，賦值也要被安排上了。賦值運(yùn)算符重載實(shí)現(xiàn)代碼如下：
list<T>& operator =( list<T>& l1) { if (this!= &l1) { clear(); for (auto e : l1) { push_back(e); } } return *this; }這是一個(gè)傳統(tǒng)寫法的運(yùn)算符重載。如果想要更加精簡(jiǎn)可以寫成現(xiàn)代寫法，代碼如下：
void swap( list<T>& l1)//別加const { std::swap(_head, l1._head);//記得這個(gè)swap是std里面的swap } list<T>& operator=(list<T> l1) { if (this != &l1) { swap(l1); } return *this; }
5.打印函數(shù)
在這里，我們每次打印一個(gè)list對(duì)象時(shí)會(huì)很麻煩，每次都要用范圍for來(lái)實(shí)現(xiàn)打印的功能。為了偷懶，我就想實(shí)現(xiàn)一個(gè)打印函數(shù)print來(lái)實(shí)現(xiàn)打印功能。實(shí)現(xiàn)代碼如下：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-659626.html
template<class T> void print(list<T>& l1) { typename list<T>::iterator it = l1.begin();//這里要用typename為前綴來(lái)告訴編譯器等list<T>實(shí)例化以后再來(lái)執(zhí)行這條語(yǔ)句 for (auto e : l1) { cout << e << " "; } cout << endl; }但是上面的代碼針對(duì)的類型時(shí)list類的泛型，如果想要實(shí)現(xiàn)能加載更多容器的print()函數(shù)那就得改一下類型，改為如下代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-659626.html
template <class Contains> void print(Contains& l1) { typename Contains::iterator it = l1.begin(); for (auto e : l1) { cout << e << " "; } cout << endl; }
到了這里，關(guān)于Cpp學(xué)習(xí)——list的模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
