?

目錄

一，實(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)說，實(shí)現(xiàn)一個(gè)雙向帶頭循環(huán)鏈表需要構(gòu)造三個(gè)類。1.list類，2.list_node類，3.list_iterator類。前兩個(gè)類相信大家會(huì)比較的熟悉。第三個(gè)類大家會(huì)比較不熟悉，因?yàn)樗且粋€(gè)迭代器的類。也就是說這個(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)差不多。不過，在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è)以后，我便想要通過顯示list里的數(shù)據(jù)來(lái)驗(yàn)證答案，但是很顯然，我們做不到。因?yàn)閘ist是一個(gè)自定義的類。但是我們有辦法，所以我們便可以通過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與enditerator 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)過程大概分三步，首先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)代碼如下：

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ù)那就得改一下類型，改為如下代碼：

template <class Contains>void print(Contains& l1){typename Contains::iterator it = l1.begin();for (auto e : l1){cout << e << " ";}cout << endl;}