目录
list的逻辑结构
构造函数
拷贝构造函数
赋值运算符重载
返回迭代器的初始位置
返回迭代器的最终位置
元素的插入
头插
尾插
删除元素
头删
尾删
清空整个链表
析构函数
正向迭代器
反向迭代器
整体代码
上期我们学写了list的基本操作，本期我们将学习list的模拟实现。
list的逻辑结构
list是一个带头结点的双向循环链表。
构造函数
list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}这是一个无参的构造函数。
template<class inputiterator>list(inputiterator begin, inputiterator end){_head = new Node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}}这是用迭代器区间进行初始化的构造函数。
list(int n, const T& data = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;while (n != 0){push_back(data);n--;}}
初始化链表的n个节点，使它们的每个结点的数据为data的值。
拷贝构造函数
list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}这是拷贝构造函数的现代写法，通过使用迭代器区间构造函数构造了一个list的临时对象，然后交换了临时对象和当前对象的头结点指针，前提是得保证当前结点的头指针不为空，不然到时候调用析构函数时会将同一空间释放两次，导致出错。
赋值运算符重载
list<T>& operator= (const list<T>lt){std:swap(_head,lt._head);return *this;}先通过拷贝构造函数生成了一个临时对象，然后再交换了临时对象和当前对象的头结点指针。
返回迭代器的初始位置
iterator begin(){return iterator(_head->_next);}迭代器的初始位置就是头结点的下一位置。
返回迭代器的最终位置
iterator end(){return iterator(_head);}迭代器的最终位置为最后一个元素的下一位置，即头结点的位置。
元素的插入
iterator 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;return iterator(newnode);}表示在当前位置之前插入一个元素，但是当前位置必须为迭代器类型。
元素的插入会导致迭代器失效吗？
不会，因为插入元素之后会及时更改迭代器中节点指针的指向。
头插
void push_front(const T& x){insert(begin(), x);}在头节点之前插入元素，复用了插入函数。
尾插
void push_back(const T& x){insert(end(), x);}在最后一个元素的后面插入元素，复用了插入函数。
删除元素
iterator erase(iterator pos){//前提是不能删除掉头结点assert(pos != end());Node* prev =pos._node->_prev;Node* next = pos._node->_next;delete pos._node;pos._node = nullptr;prev->_next = next;next->_prev = prev;return iterator(next);}
删除某一位置之后，返回的是当前位置的下一位置的迭代器。
元素的删除会导致迭代器失效吗？
会，因为删除掉当前位置之后，当前迭代器的节点指针会被释放。迭代器的节点都被释放了，所以迭代器自然会失效。
头删
void pop_back(){erase(--end());}尾删
void pop_back(){erase(--end());}清空整个链表
void clear(){iterator it = begin();while (it != end()){erase(it);it++;}}
删除除头结点之外的所有节点。
析构函数
~list(){clear();delete _head;_head = nullptr;}析构函数会清空整个链表的信息，所以头结点指针也会被释放。
正向迭代器
正向迭代器，其实就是从前往后进行链表元素的遍历。
template<class T,class Ref,class Ptr>struct list_iterator{typedef ListNode<T> Node;typedef list_iterator<T, Ref, Ptr> self;//构造函数list_iterator<T,Ref,Ptr>(Node* node):_node(node){}//解引用操作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;}//赋值运算符重载，浅拷贝self& operator=(const self& iterator){_node = iterator._node;return *this;}//判断是否相等bool operator ==(const self& iterator) const{return _node == iterator._node;}bool operator !=(const self& iterator) const{return _node != iterator._node;}Node* _node;};
list的迭代器和vector的迭代器是不同的，vector的迭代器类型是指针类型，即内置类型。而list的迭代器类型是自定义类型。
反向迭代器
反向迭代器即从后往前进行链表元素的遍历。
namespace yjd {template<class iterator,class Ref,class Ptr>class reverse_iterator{public:typedef reverse_iterator<iterator, Ref, Ptr> self;//构造函数reverse_iterator(iterator it):_it(it){}//解引用操作Ref operator*(){iterator prev = _it;return *(--prev);}//->Ptr operator->(){iterator prev = _it;return &(--prev);}//++self& operator++(){_it--;return *this;}//--self& operator--(){_it++;return *this;}//判断是否相等bool operator!=(const self & rit) const{return _it != rit._it;}private:iterator _it;};}
正向迭代器和返现迭代器的开始和结束位置刚好是相对的。反向迭代器的本质仍然是正向迭代器。反向迭代器的++为正向迭代器的--。
虽然说返现迭代器的开始和结束如图如上图所示，但是我们真正在访问的时候并不是访问所示位置的元素，而是访问其前一个位置的元素，比如要访问rbgin位置的元素，则要让正向迭代器进行--访问最后一个位置的元素。
整体代码
list.h
#pragma once
#include<assert.h>
#include"reverse_iterator.h"
namespace yjd
{//节点类型template<class T>struct ListNode {ListNode* _next;ListNode* _prev;T _data;ListNode(const T& data=T()):_next(nullptr),_prev(nullptr),_data(data){}};//链表的迭代器类型template<class T,class Ref,class Ptr>struct list_iterator{typedef ListNode<T> Node;typedef list_iterator<T, Ref, Ptr> self;//构造函数list_iterator<T,Ref,Ptr>(Node* node):_node(node){}//解引用操作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;}//赋值运算符重载，浅拷贝self& operator=(const self& iterator){_node = iterator._node;return *this;}//判断是否相等bool operator ==(const self& iterator) const{return _node == iterator._node;}bool operator !=(const self& iterator) const{return _node != iterator._node;}Node* _node;};//链表类型template<class T>class list {typedef ListNode<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//构造函数list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//构造函数，迭代器区间进行构造template<class inputiterator>list(inputiterator begin, inputiterator end){_head = new Node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}}//拷贝构造list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}//赋值运算符重载list<T>& operator= (const list<T>lt){std:swap(_head,lt._head);return *this;}//构造函数n个datalist(int n, const T& data = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;while (n != 0){push_back(data);n--;}}//尾插//void push_back(const T& data)//{// Node* newnode = new Node(data);// Node* tail = _head->_prev;// tail->_next = newnode;// newnode->_prev = tail;// newnode->_next = _head;// _head->_prev = newnode;//}// //rbeginreverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}//rendreverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}//beginiterator begin(){return iterator(_head->_next);}//enditerator end(){return iterator(_head);}//beginconst_iterator begin() const{return const_iterator(_head->_next);}//endconst_iterator end() const{return const_iterator(_head);}//元素的插入,在pos位置之前插入元素iterator 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;return iterator(newnode);}//list的头插和尾插，可以复用insert,插入元素之后我们更改的是节点的指针，所以不会涉及到迭代器失效void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){insert(end(), x);}//链表删除某一位置元素，删除某一位置的元素，迭代器会失效吗？会失效，因为删除掉元素之后，会释放节点的指针，节点的指针都被释放了，迭代器自然也就没有意义了iterator erase(iterator pos){//前提是不能删除掉头结点assert(pos != end());Node* prev =pos._node->_prev;Node* next = pos._node->_next;delete pos._node;pos._node = nullptr;prev->_next = next;next->_prev = prev;return iterator(next);}//list的尾删头删void pop_back(){erase(--end());}void pop_front(){erase(begin());}//list整个的删除，这个删除是删除所有的有效的节点void clear(){iterator it = begin();while (it != end()){erase(it);it++;}}//析构函数~list(){clear();delete _head;_head = nullptr;}private:Node* _head;};}reverse_iterator.h
#pragma oncenamespace yjd {template<class iterator,class Ref,class Ptr>class reverse_iterator{public:typedef reverse_iterator<iterator, Ref, Ptr> self;//构造函数reverse_iterator(iterator it):_it(it){}//解引用操作Ref operator*(){iterator prev = _it;return *(--prev);}//->Ptr operator->(){iterator prev = _it;return &(--prev);}//++self& operator++(){_it--;return *this;}//--self& operator--(){_it++;return *this;}//判断是否相等bool operator!=(const self & rit) const{return _it != rit._it;}private:iterator _it;};}以上便是list模拟实现的所有知识点。
本期内容到此结束^_^