1 list的简单回顾
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。
通过上面的信息我们不难得出list是一个带头双向循环链表，是不能够用库中的sort（库中sort要求必须是随机迭代器）,要排序的话只有用自己里的sort（这里实现用的是归并排序，但我们一般不会在链表中排序）至于list的其他接口大家可以去官方库中查阅，这里就不在多讲了。接下来就进入重点list的模拟实现（博主的模拟实现是参照stlSGI版本3.0）
2 类中成员变量的声明
首先我们肯定要定义一个类来完成结点的构建：
template<class T> struct ListNode { ListNode<T>* _prev; ListNode<T>* _next; T _val; ListNode(const T& val = T()) :_prev(nullptr) , _next(nullptr) , _val(val) {} };
接下来大家想想我们就能够把结点直接定义到list类中吗？
这样貌似不行呀，大家想想：我们使用list的迭代器时是这样使用的：
list<int> ls; ls.push_back(1); ls.push_back(2); ls.push_back(3); ls.push_back(4); auto it=ls.begin(); while(it!=ls.end()) { cout<<*it<<" "; ++it; }
如果我们直接将原生指针封装在list中而不做其他的事，那么实现++运算符重载时应该怎么办？
string和vector能够直接用原生指针的原因是他们的物理空间地址是连续的，++能够直接访问到下一位的地址，但是双向链表的物理空间地址并不是连续的，所以直接++有可能是非法访问的.
而这里的it是迭代器类型的，我们不可能直接在list中重载++,那我们能在ListNode这个类里面重载++运算符吗？
这样做好像也是行不通的，假设我们这样重载，那么迭代器类型是ListNode*类型，但是我们并没有重载ListNode*的++运算符重载。
所以这里又得再重新将结点指针封装到另一个类里，我们不妨把这个类叫做__list_iterator，在__list_iterator这个类中重载++运算符，这样it就变成了__list_iterator类型的，再进行++操作时就能够正确跳转到下一位地址，这就是类型的力量。在list类中返回一个迭代器返回的就是__list_iterator类型的。
template<class T> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T> iterator; Node* _node; __list_iterator( Node* n) :_node(n) {} }
list类中
template<class T> class list { public: typedef ListNode<T> Node; typedef __list_iterator<T> iterator; list() { _head = new Node(); _head->_next = _head; _head->_prev = _head; } private: Node* _head;//头结点 }
3 __list_iterator 中运算符重载
T& operator*() { return _node->_val; } //++it iterator& operator++() { _node = _node->_next; return *this; } //it++ iterator operator++(int) { iterator tmp(*this); _node = _node->_next; return tmp; } //--it iterator& operator--() { _node = _node->_prev; return *this; } //it-- iterator operator--(int) { iterator tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const iterator& it)const { return _node != it._node; } bool operator==(const iterator& it)const { return _node == it._node; }
有了上面的理解这里实现起来就容易多了。
4 list中的迭代器
iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); }
5 list中增删查改以及clear
void clear() { /*iterator it = begin(); while (it != end()) { iterator del = it++; delete del._node; } _head->_next = _head; _head->_prev = _head;*/ iterator it = begin(); while (it != end()) { erase(it++); } } void push_back(const T& x) { Node* tail = _head->_prev; Node* newNode = new Node(x); tail->_next = newNode; newNode->_prev = tail; _head->_prev = newNode; newNode->_next = _head; //insert(end(), x); } void pop_back() { assert(_head->_prev!=_head); Node* tail = _head->_prev; Node* prev = tail->_prev; prev->_next = _head; _head->_prev = prev; delete tail; //erase(--end()); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } //在pos前插入数据，返回新节点的迭代器，pos并不会失效 iterator insert(iterator pos, const T& val) { Node* cur = pos._node; Node* prev = pos._node->_prev; Node* newNode = new Node(val); prev->_next = newNode; newNode->_prev = prev; newNode->_next = cur; cur->_prev = newNode; return iterator(newNode); } //删除pos位置，返回删除后的下一位迭代器，pos肯定失效了 iterator erase(iterator pos) { assert(pos != end()); Node* prev = pos._node->_prev; Node* next = pos._node->_next; delete pos._node; prev->_next = next; next->_prev = prev; return iterator(next); }
这些都是我们之前双向带头循环链表玩过的，很简单，这里就不在多说了。
6 const迭代器
普通方法是我们自己再重新造一个const_iterator类，基本内容不变，只不过重载*时返回的是const T&,返回迭代器返回的是const_iterator。但是这样是不是代码写的有点儿挫了，两份几乎相同的代码重复出现，于是我们的C++大佬便想出了一个好办法，使用多个模板参数处理。（大佬就是大佬）
6.1 __list_iterator的重新实现
template<class T,class Ref,class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T,Ref,Ptr> self; Node* _node; __list_iterator( Node* n) :_node(n) {} Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } //++it self& operator++() { _node = _node->_next; return *this; } //it++ self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } //--it self& operator--() { _node = _node->_prev; return *this; } //it-- self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self& it)const { return _node != it._node; } bool operator==(const self& it)const { return _node == it._node; } };
这里面值得大家注意的问题是：const迭代器是指的是本身是不可修改的吗？
答案肯定是否定的，const迭代器只是说明指向的内容是不可修改的，但是迭代器自己本身是必须要可修改的，因为迭代器还得自己++来遍历。
大家或许又有了疑问了？这里的Ptr又是什么鬼呢？
其实这里的Ptr专门是为了给->运算符重载准备的，因为使用->运算符也得区分是否为const迭代器。但是编译器在这里进行了优化，按照我们的理解这里应该是要写两个->,但是为了代码的可读性更高编译器就进行了优化，将两个->优化成了一个。
6.2 list类的巧妙修改
里面的增删查改不需要变动，需要增加一个const迭代器：
template<class T> class list { public: typedef ListNode<T> Node; typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator;//第一个不要加const list() { _head = new Node(); _head->_next = _head; _head->_prev = _head; } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin()const { return const_iterator(_head->_next); } const_iterator end()const { return const_iterator(_head); } private: Node* _head; }
这样我们调用const对象时就能够去调用const 迭代器。
7 构造函数&&拷贝构造&&赋值运算符重载
构造函数：
list() { _head = new Node(); _head->_next = _head; _head->_prev = _head; }
拷贝构造传统写法：
//list2(list1) 深拷贝：传统写法 list(size_t n, const T& val=T()) { _head = new Node(); _head->_next = _head; _head->_prev = _head; for (size_t i = 0; i < n; i++) { push_back(val); } }
拷贝构造现代写法与vector的实现类似，都是需要构造函数来帮助实现，所以我们还得再写一个构造函数：
template<class InputIterator> list(InputIterator first, InputIterator last) { _head = new Node(); _head->_next = _head; _head->_prev = _head; while (first != last) { push_back(*first); ++first; } }
拷贝构造现代写法：
list(const list<T>& ls) { _head = new Node(); _head->_next = _head; _head->_prev = _head; list<T> tmp(ls.begin(), ls.end()); std::swap(_head, tmp._head); }
赋值运算符重载传统写法：
//list2=list1 传统写法 list<T> operator=(const list<T>& ls) { if (&ls != this) { clear(); for (auto& e : ls) { push_back(e); } } return *this; }
赋值运算符重载现代写法：
//现代写法 list<T> operator=(list<T> ls) { std::swap(_head, ls._head); return *this; }
但是大家发现了没有，当这样使用list2(2,2) 会优先选择list(InputIterator first, InputIterator last)，并不会选择list(size_t n, const T& val=T())。这样不就搞错了吗？处理方法是再重载一个拷贝构造：
list(int n, const T& val = T()) { _head = new Node(); _head->_next = _head; _head->_prev = _head; for (int i = 0; i < n; i++) { push_back(val); } }
这样当有现成的就不会再去调用模板了。
8 反向迭代器
有了上面的铺垫实现反向迭代器大家或许就会直接再生成一个__reverse_list_iterator就好了，但是同样的，这样写代码太冗余了，C++大佬就想出了另外一个巧妙的方法：再封装一层，封装一层反向迭代器类，类的成员变量为刚才我们实现的正向迭代器。这样封装又没有什么好处呢？答案是有的，这样处理不仅list可以用，像我们之前实现的string和vector也都可以用。（这就是那些C++大佬NB之处）
定义一个reverse_iterator类：
namespace grm { // Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以 // 适配出哪个容器的反向迭代器。复用的体现 template <class Iterator, class Ref, class Ptr> class reverse_iterator { typedef reverse_iterator<Iterator, Ref, Ptr> self; public: reverse_iterator(Iterator it) :_it(it) {} Ref operator*() { //return *_it; Iterator prev = _it; return *--prev; } Ptr operator->() { return &operator*(); } self& operator++() { --_it; return *this; } self& operator--() { ++_it; return *this; } bool operator!= (const self& rit) const { return _it != rit._it; } private: Iterator _it; }; }
在list类中多typedef 一下:
typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//这个要放在前面 typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
再增加一些成员函数：
reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin()const { return const_reverse_iterator(end()); } const_reverse_iterator rend()const { return const_reverse_iterator(begin()); }
不知道大家注意到了没有C++大佬在设计反向迭代器时遵循了一种对称美，正向迭代器的begin()等于反向迭代器的rend(),正向迭代器的end()等于反向迭代器的rbegin(),正是由于这样设计所以在反向迭代器运算符*的重载设计是这样的：
Ref operator*() { //return *_it; Iterator prev = _it; return *--prev; }
我们取得的数据是它的前一位数据。
但是如果只用一个模板参数又应该怎么处理呢？
在__list_iterator中又要typedef 一下：
typedef Ref refence;//不用3个模板参数时将实例化后的参数类型能够通过Iterator类域取得 typedef Ptr pointer;//但是像vector&&string的迭代器为原生指针的就不行，因为无法在原生指针中定义内嵌类型
reverse_iterator中：
namespace grm { // Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以 // 适配出哪个容器的反向迭代器。复用的体现 template <class Iterator>//不用3个模板参数 class reverse_iterator { typedef reverse_iterator<Iterator> self; typedef typename Iterator::refence Ref;//可以typedef后直接用Ref和Ptr typedef typename Iterator::pointer Ptr; public: reverse_iterator(Iterator it) :_it(it) {} typename Iterator::refence operator*()//也可以不用typedef { Iterator prev = _it; return *--prev; } typename Iterator::pointer operator->() { return &operator*(); } self& operator++() { --_it; return *this; } self& operator--() { ++_it; return *this; } bool operator!= (const self& rit) const { return _it != rit._it; } private: Iterator _it; }; }
由于在模板里还没有实例化出对象出来，所以要用typename声明一下，等到对象实例化出来后再去找，不这样声明的话就编译不过。
