在了解學(xué)習(xí)list實(shí)現(xiàn)之前我們首先了解一下關(guān)于迭代器的分類：

按功能分類：

正向迭代器? ? 反向迭代器

const正向迭代器? const反向迭代器

按性質(zhì)分類：

單向迭代器? ? ? 只能++? ? 例如單鏈表

?雙向迭代器? ? ?可++，也可--? ? ?例如雙鏈表 ，map和set

?隨機(jī)迭代器? ? ?可加加，可減減，可+，可減? 如順序表（vector string）,deque(雙端隊(duì)列)

這些都是由容器的底層實(shí)現(xiàn)。

可以看到庫中提供的list模板是帶頭雙向鏈表，故此我們實(shí)現(xiàn)它就大部分操作都是在數(shù)據(jù)結(jié)構(gòu)中實(shí)現(xiàn)雙鏈表時是一樣。

目錄

1.成員變量

節(jié)點(diǎn)類型的定義：

迭代器

重載前置++/--

重載后置++/--

重載*與->

重載!=與==

const迭代器

迭代器的優(yōu)化：

?成員函數(shù)

構(gòu)造函數(shù)

析構(gòu)函數(shù)

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

容量

size

修飾符?

insert()

erase ()

push_front()

pop_front()

push_back()

pop_back()

clear()

---

1.成員變量

template<class T>class mylist{typedef list_node<T>  Node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T,const T&,const T*> const_iterator;
private:Node* _head;size_t _size;
......
}

因?yàn)閷?shí)現(xiàn)的是鏈表，故此我們的成員變量是鏈表頭節(jié)點(diǎn)與鏈表的大小，這里我們還需要給出

節(jié)點(diǎn)類型的定義：

typedef list_node<T>  Node;
template<class T>struct list_node{//我們給一個缺省值為T的匿名對象list_node(const T& x = T()):data(x), _next(nullptr), _prev(nullptr){}T data;list_node<T>* _next;list_node<T>* _prev;};

迭代器

因?yàn)槲覀儗?shí)現(xiàn)的是鏈表，那么迭代器的操作也就是鏈表節(jié)點(diǎn)的操作，節(jié)點(diǎn)并非一般的數(shù)據(jù)類型，

故此我們這里需要封裝迭代器，迭代器本質(zhì)是節(jié)點(diǎn)的地址：

//迭代器//認(rèn)真思考的話，迭代器模擬的是一個雙鏈表節(jié)點(diǎn)的運(yùn)動，故我們封裝迭代器里面一定是節(jié)點(diǎn)，這里放入節(jié)點(diǎn)的地址//并且重載對應(yīng)的運(yùn)算符，封裝之后，我們在定義為iteratortemplate<class T>struct _list_iterator{//利用節(jié)點(diǎn)的指針實(shí)現(xiàn)迭代器typedef list_node<T>  Node;typedef _list_iterator<T> self;Node* _node;_list_iterator(Node* node):_node(node){}};

封裝之后，我們還需要重載對于迭代器的運(yùn)算符，這些重載都是在迭代器中的，我只是為了吧方法一個個體現(xiàn)出來，分開了。

重載前置++/--

       //重載加加self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}

重載后置++/--

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

重載*與->

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

重載!=與==

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

const迭代器

const迭代器對應(yīng)const對象,指的是內(nèi)容不能被修改，而非指針（迭代器）本身，因此我們不能直接const iterator去認(rèn)為是const迭代器,這樣反而不能對迭代器進(jìn)行++等操作，而需要我們?nèi)ブ匦露x
?定義const迭代器，即內(nèi)容是無法被修改，由于我們訪問內(nèi)容是通過解引用的方法故我們需要修改訪問的的這兩個操作符其引用返回為const，即內(nèi)容無法被修改了。

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){}//迭代器的運(yùn)算符重載self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->prev;return *this;}self& operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(int){self tmp(*this);_node = _node->prev;return tmp;}const T* operator->(){return &_node->data;}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迭代器與普通的迭代器區(qū)別也就在于訪問的內(nèi)容無法被修改，也就是修改*與->這兩個訪問內(nèi)容的操作符，重新實(shí)現(xiàn)較為麻煩，庫中實(shí)現(xiàn)是增加了兩個模板參數(shù)Ref,Ptr，利用我們傳的參數(shù)不一樣，從而決定用的是哪一個迭代器。

迭代器的優(yōu)化：

多出兩個模板參數(shù)之后，我們的*與->返回類型就是到時候傳入時候的類型，故這里我們直接用Ref與Ptr代替即可。

template<class T,class Ref,class Ptr>struct _list_iterator{//利用節(jié)點(diǎn)的指針實(shí)現(xiàn)迭代器typedef list_node<T>  Node;typedef _list_iterator<T,Ref,Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}
}

        Ptr operator->(){return _node->data;}Ref operator*(){return &_node->data;}

?在list中，對于模板迭代器我們傳參不一樣，決定了是const還是普通

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T,const T&,const T*> const_iterator;iterator begin(){//return iterator(_head->data);return _head->_next;}iterator end(){return _head;//哨兵位就是鏈表的結(jié)束標(biāo)志}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}

?成員函數(shù)

構(gòu)造函數(shù)

       //通過調(diào)用一個初始化鏈表的函數(shù)來實(shí)現(xiàn)構(gòu)造函數(shù)mylist(){empty_init();}

析構(gòu)函數(shù)

      //通過調(diào)用clear函數(shù)釋放鏈表的節(jié)點(diǎn)，在釋放哨兵位，即為析構(gòu)~mylist(){clear();delete _head;_head = nullptr;}

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

//拷貝構(gòu)造,將節(jié)點(diǎn)尾插入新的對象mylist(mylist<T>& p){empty_init(p);for (auto it : p){push_back(it);}}

容量

size

size_t size(){return _size;}

修飾符?

insert()

在基于實(shí)現(xiàn)insert，我們的其他對list的操作都可以調(diào)用insert，不需要都去對鏈表節(jié)點(diǎn)一個個操作，

其次我們設(shè)計(jì)insert的返回值及參數(shù)位置都是迭代器，直接用。

iterator insert(iterator pos, const T x)//插入也會使迭代器失效，原位置節(jié)點(diǎn)找不到了{(lán)Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;//鏈接節(jié)點(diǎn)prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;return iterator(newnode);}

erase ()

//刪除   這里刪除cur節(jié)點(diǎn)釋放掉，會導(dǎo)致迭代器失效,因此要返回下一節(jié)點(diǎn)的迭代器iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;_size--;return iterator(next);}

push_front()

void push_front(){insert(begin());}

pop_front()

//頭刪void pop_front(){erase(begin());}

push_back()

//尾插void push_back(const T& x){//Node* tail = _head->preav;//Node* newnode = new Node(x);連接節(jié)點(diǎn)//tail->_next = newnode;//newnode->_next = _head;//newnode->prev = tail;//tail->_prev = newnode;//tail = newnode;//return (tail);insert(end(), x);}

pop_back()

//尾刪void pop_back(){erase(end());}

clear()

//清數(shù)據(jù)void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

至此我們對list的簡單實(shí)現(xiàn)就完成了。