【C++: list的模拟实现】
目录
1 list的简单回顾
2 类中成员变量的声明
3 __list_iterator 中运算符重载
4 list中的迭代器
5 list中增删查改以及clear
6 const迭代器
6.1 __list_iterator的重新实现
6.2 list类的巧妙修改
7 构造函数&&拷贝构造&&赋值运算符重载
8 反向迭代器
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
struct ListNode
{ListNode* _prev;ListNode* _next;T _val;ListNode(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}
}; 接下来大家想想我们就能够把结点直接定义到list类中吗？
这样貌似不行呀，大家想想：我们使用list的迭代器时是这样使用的：
list 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中重载++,所以这里又得再重新将结点指针封装到另一个类里，我们不妨把这个类叫做__list_iterator，在__list_iterator这个类中重载++运算符，这样it就变成了__list_iterator类型的，再进行++操作时就能够正确跳转到下一位地址，这就是类型的力量。在list类中返回一个迭代器返回的就是__list_iterator类型的。
template
struct __list_iterator
{typedef ListNode Node;typedef __list_iterator iterator;Node* _node;__list_iterator( Node* n):_node(n){}
} list类中：
template
class list
{
public:typedef ListNode Node;typedef __list_iterator iterator;list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}
private:Node* _head;//头结点
} 3 __list_iterator 中运算符重载
T& operator*(){return _node->_val;}//++ititerator& operator++(){_node = _node->_next;return *this;}//it++iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}//--ititerator& 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(_head, 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(_head->_prev);}void push_front(const T& x){insert(_head->_next, x);}void pop_front(){erase(_head->_next);}//在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的重新实现
templatestruct __list_iterator{typedef ListNode Node;typedef __list_iterator self;Node* _node;__list_iterator( Node* n):_node(n){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}//++itself& operator++(){_node = _node->_next;return *this;}//it++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//--itself& 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;}}; 大家或许又有了疑问了？这里的Ptr又是什么鬼呢？
其实这里的Ptr专门是为了给->运算符重载准备的，因为使用->运算符也得区分是否是const迭代器。
6.2 list类的巧妙修改
里面的增删查改不需要变动，需要增加一个const迭代器：
templateclass list{public:typedef ListNode Node;typedef __list_iterator iterator;typedef __list_iterator const_iterator;//第一个不要加constlist(){_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的实现类似，都是需要构造函数来帮助实现，所以我们还得再写一个构造函数：
templatelist(InputIterator first, InputIterator last){_head = new Node();_head->_next = _head;_head->_prev = _head;while (first != last){push_back(*first);++first;}} 拷贝构造现代写法：
list(const list& ls){_head = new Node();_head->_next = _head;_head->_prev = _head;list tmp(ls.begin(), ls.end());std::swap(_head, tmp._head);} 赋值运算符重载传统写法：
//list2=list1 传统写法list operator=(const list& ls){if (&ls != this){clear();for (auto& e : ls){push_back(e);}}return *this;} 赋值运算符重载现代写法：
//现代写法list operator=(list 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就可以// 适配出哪个容器的反向迭代器。复用的体现template class reverse_iterator{typedef reverse_iterator 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_reverse_iterator;//这个要放在前面typedef reverse_iterator 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就可以// 适配出哪个容器的反向迭代器。复用的体现template //不用3个模板参数class reverse_iterator{typedef reverse_iterator self;typedef typename Iterator::refence Ref;//可以typedef后直接用Ref和Ptrtypedef 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声明一下，等到对象实例化出来后再去找，不这样声明的话就编译不过。
需要源码的老铁可以在博主的码云中获得：https://gitee.com/monday-sky/text_cpp/commit/ea3b9b2a66531794d92ba71c730414f6f25f0814
https://gitee.com/monday-sky/text_cpp/commit/ea3b9b2a66531794d92ba71c730414f6f25f0814