目錄

一、模擬實(shí)現(xiàn)前的準(zhǔn)備

1.list結(jié)構(gòu)認(rèn)識(shí)

2.迭代器的實(shí)現(xiàn)不同

3.如何實(shí)現(xiàn)需要的功能

二.結(jié)點(diǎn)類實(shí)現(xiàn)

三.迭代器實(shí)現(xiàn)

1.實(shí)現(xiàn)前的問題

2._list_iterator類的成員變量和構(gòu)造函數(shù)

3.*和->運(yùn)算符重載

4.前置++和后置++的實(shí)現(xiàn)

5.前置--和后置--

6.==和!=運(yùn)算符重載

四.list類的實(shí)現(xiàn)

1.list類和構(gòu)造函數(shù)

2.析構(gòu)

3.拷貝構(gòu)造函數(shù)

4.賦值運(yùn)算符重載

5.迭代器

6.insert()

7.erase()

8.clear()

9.頭插頭刪，尾插尾刪

10.判空

五.完整代碼

---

一、模擬實(shí)現(xiàn)前的準(zhǔn)備

1.list結(jié)構(gòu)認(rèn)識(shí)

1.STLe的list的底層結(jié)構(gòu)其實(shí)是帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過指針指向其前一個(gè)元素和后一個(gè)元素。

?

2.迭代器的實(shí)現(xiàn)不同

list插入元素不會(huì)導(dǎo)致迭代器失效，刪除元素時(shí)，只會(huì)導(dǎo)致當(dāng)前迭代器失效，其他迭代器不受影響。list的迭代器是自定義類型對(duì)原生指針的封裝，模擬指針的行為，那為什么不像vector那樣直接用原生指針呢？因?yàn)閘ist的每個(gè)結(jié)點(diǎn)在物理結(jié)構(gòu)上面不是連續(xù)的，直接對(duì)結(jié)點(diǎn)++，其得到的不是下一個(gè)結(jié)點(diǎn)指針。

3.如何實(shí)現(xiàn)需要的功能

這里我們可以用三個(gè)類來模擬實(shí)現(xiàn)，結(jié)點(diǎn)類和list迭代器類用struct封裝，因?yàn)槲覀儾恍枰獙?duì)其做訪問限制，而list類就用class類封裝。

?

二.結(jié)點(diǎn)類實(shí)現(xiàn)

結(jié)點(diǎn)類實(shí)現(xiàn)比較簡單，不過我們需要注意：

（1）需要用到模板，方便以后使用不同的類型；

（2）結(jié)點(diǎn)成員變量包括，結(jié)點(diǎn)值、指向前一個(gè)結(jié)點(diǎn)的指針，指向后一個(gè)結(jié)點(diǎn)的指針；

（3）不需要析構(gòu)函數(shù)（沒有額外申請(qǐng)空間）；

（4）用struct來實(shí)現(xiàn)，對(duì)訪問不做限制

template<class T>                 //list的結(jié)點(diǎn)結(jié)構(gòu)，對(duì)訪問不做限制，所以用structstruct list_node{list_node<T>* _next;       //成員變量list_node<T>* _prev;T _data;list_node(const T& x = T())       //構(gòu)造函數(shù):_next(nullptr), _prev(nullptr), _data(x){}};

三.迭代器實(shí)現(xiàn)

list的迭代器實(shí)現(xiàn)是整個(gè)實(shí)現(xiàn)過程中最精彩的部分，尤其是模板里的多個(gè)參數(shù)，可謂是把規(guī)則用到了極致，涉及到的知識(shí)點(diǎn)也非常多，我們不得不感嘆STL大佬的實(shí)力。

1.實(shí)現(xiàn)前的問題

迭代器分為普通迭代器和const迭代器，之前的迭代器由于是直接用的原生指針，所以就算兩種迭代器分開實(shí)現(xiàn)，其代碼量夜很小。但是對(duì)于_list_iterator類要實(shí)現(xiàn)的普通的_list_iterator和const版本的_list_const_iterator，因?yàn)閷?duì)于兩個(gè)類中的部分函數(shù)有普通函數(shù)和const函數(shù)之分（如begin(?)和end(?)），其他并無區(qū)別。因?yàn)檫@兩個(gè)類的大部分代碼相似，那么怎么解決呢？

查看STL源碼，我們可以發(fā)現(xiàn)，用下面的方法非常不錯(cuò)：

迭代器模板用到了三個(gè)參數(shù)

template<class T, class Ref, class Ptr>

list在實(shí)例化時(shí)，通過不同的參數(shù)實(shí)例出兩個(gè)類，一個(gè)是普通的不帶const的T，T&，?T*，另一個(gè)是帶const的T，const?T&，?const?T*，其中Ref是引用，Ptr是指針，該類模板實(shí)例化了以下這兩個(gè)類模板：

typedef __list_iterator<T, T&, T*> iterator;   //非const 迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;     //const迭代器

這樣我們就解決了代碼冗余的問題（大佬不愧是大佬）。

2._list_iterator類的成員變量和構(gòu)造函數(shù)

成員變量只有結(jié)點(diǎn)node，構(gòu)造函數(shù)負(fù)責(zé)初始化結(jié)點(diǎn)

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* n)      //構(gòu)造函數(shù):_node(n){}};

3.*和->運(yùn)算符重載

Ref operator*()
{
return _node->_data;     //解引用之后，我們需要得到拷貝的值，所以返回引用
}Ptr operator->()
{
return &_node->_data;    //結(jié)構(gòu)體指針解引用，返回結(jié)點(diǎn)指針
}

注意：It->_data，（It是一個(gè)迭代器）我們平時(shí)這樣用沒問題，但是我們要知道這里其實(shí)省略了一個(gè)->,It->其實(shí)就是It.operator->()，其返回值是_data*類型，我們還需要It.operator->()->_data，但是為了可讀性，編譯器優(yōu)化了一個(gè)箭頭。

4.前置++和后置++的實(shí)現(xiàn)

self& operator++()            //都需要用到自身，所以是self
{
_node = _node->_next;
return *this;
}self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}

5.前置--和后置--

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

6.==和!=運(yùn)算符重載

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

四.list類的實(shí)現(xiàn)

1.list類和構(gòu)造函數(shù)

template<class T>class list                           //list類{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;                     //非const 迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;       //const迭代器//typedef __list_const_iterator<T> const_iterator;list(){_head = new node;                    //默認(rèn)構(gòu)造函數(shù)_head->_next = _head;_head->_prev = _head;}private:node* _head;  };

2.析構(gòu)

復(fù)用了后面的函數(shù)

        ~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}

3.拷貝構(gòu)造函數(shù)

        void empty_init()          //空初始化{_head = new node;_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}

4.賦值運(yùn)算符重載

（1）現(xiàn)代的賦值運(yùn)算符重載

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

在執(zhí)行賦值運(yùn)算符重載時(shí)，會(huì)調(diào)用拷貝構(gòu)造函數(shù)執(zhí)行深拷貝，然后再交換兩個(gè)鏈表頭節(jié)點(diǎn)的指針，把this要釋放的資源交給臨時(shí)對(duì)象，臨時(shí)對(duì)象出了swap的函數(shù)作用域就被this要釋放的資源也會(huì)被同時(shí)釋放。

5.迭代器

        iterator begin(){//iterator it(_head->_next);//return it;return iterator(_head->_next);     //匿名對(duì)象}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{//iterator it(_head->_next);//return it;return const_iterator(_head);}

6.insert()

先構(gòu)造一個(gè)結(jié)點(diǎn)，然后插入

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

7.erase()

刪除后，需要返回刪除位置的下一個(gè)結(jié)點(diǎn)

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

8.clear()

不能把哨兵衛(wèi)清理了，否則鏈表就不存在了

        void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}

9.頭插頭刪，尾插尾刪

這里直接復(fù)用insert()和erase()

        void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}

10.判空

bool empty()
{return end()==begin();
}

五.完整代碼

        #pragma once
#include<assert.h>
#include<iostream>namespace bit
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};// 1、迭代器要么就是原生指針// 2、迭代器要么就是自定義類型對(duì)原生指針的封裝，模擬指針的行為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* n):_node(n){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){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;//typedef __list_const_iterator<T> const_iterator;iterator begin(){//iterator it(_head->_next);//return it;return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{//iterator it(_head->_next);//return it;return const_iterator(_head);}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}template <class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}// lt2(lt1)/*list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}*/void swap(list<T>& tmp){std::swap(_head, tmp._head);}list(const list<T>& lt){empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}void push_back(const T& x){/*node* tail = _head->_prev;node* new_node = new node(x);tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node(x);prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;}iterator erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);}bool empty(){return end()==begin();}private:node* _head;};
}