list的再认识：
在之前List的介绍与使用中，我们知道list容器是一个带头双向循环链表，那么我们在模拟实现中，能不能先证明一下List是否是一个双向循环链表呢？
我们参考一下stl中list的源码：
我们看到，在源码中，list中有一个__list_node的节点，我们将这个链表的节点定义打开发现定义两个指针next，prev.
再来看一下它的空初始化：
通过观察源码中list的初始化，确实是一个双向循环链表。
接下来。我们就来自己实现一下里面的接口函数。
注意：在模拟实现中，我们采取用与与源码中相同的命名风格。
为防止与库里面的list重复，我们模拟实现将定义在自己的命名空间中。
初始化与定义节点：
首先，我们需要定义三个类，并用摸版进行封装：分别是list，list的节点，以及迭代器：
list节点：
template<class T> struct list_node { T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& x=T()) :_data(x) ,_next(nullptr) ,_prev(nullptr) {} };
list:
template<class T> class list { typedef list_node<T> Node; public: //空初始化： void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } //无参构造： list() { empty_init(); } void push_Back(const T& x) { Node* tail = _head->_prev; Node* newnode = new Node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; } private: Node* _head; };
这里我们写的是无参构造，以及实现了一个尾插接口：
尾插双向链表实现已经再简单不过了：
现在我们测试一下：
现在还不能进行遍历，因此我们自己要实现一个迭代器：
迭代器实现：
那么这个迭代器我们要作为怎么实现呢？
我们可以先回顾一下，在vector中，我们实现迭代器就是实现原生指针。
在vector中，给it解引用就可以访问到里面的数据，但是链表不行，因为链表中空间不是连续的。
那么应该怎么实现呢？其实这个就和我们之前的日期类一样，在日期类中我们用运算符重载与封装实现了对日期类的++操作。而我们的迭代器也使这样实现的。
这里我们需要实现迭代器的！=，*与++操作：
我们先看一下库里面的操作：
构造：
看一下库里面的操作：
库里面用了一个节点的指针进行构造，这是因为：单参数的构造函数支持隐式类型转换。
所以我们的构造就可以这样写：
__list_iterator(Node* node) :_node(node) { }
++
实现迭代器++，就是指针往后走的过程，注意返回的是迭代器。我们可以将迭代器重命名一下：
typedef __list_iterator<T> self;
实现代码：
self& operator++() { _node = _node->_next; return *this; }
解引用：*
返回节点里面的数据即可：
T& operator*() { return _node->_data; }
！=
两个迭代器进行比较，实质两个指针比较。
//两个迭代器进行比较，两个指针比较 bool operator!=(const self& s) { return _node != s._node; }
基本框架搭建：
这样基本上迭代器的基本架子就完成了：
typedef __list_iterator<T> iterator; iterator begin() { return _head->_next; } iterator end() { return _head; }
在list中定义一下迭代器。迭代器开始位置就是返回哨兵位头节点的下一个位置，结束位置就是返回哨兵位的地址。
测试一下：
void test_list1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { //*it += 20; cout << *it << " "; ++it; } cout << endl; }
测试结果：
有了迭代器就有范围for：
for (auto e : lt) { cout << e << " "; } cout << endl;
总结：其实会发现就是在模拟指针，但他的底层细节很大。所以迭代器体现了封装的强势之处。封装屏蔽底层差异和实现细节，提供统一的访问修改遍历方式。这样我们就不用关注他的底层是什么.
举个例子：
set<int> s; s.insert(1); s.insert(3); s.insert(2); s.insert(4); set<int>::iterator sit = s.begin(); while (sit != s.end()) { cout << *sit << " "; ++sit; } cout << endl; }
这里的set就是树，我们也可以依然用这个迭代器进行遍历。
–
实现迭代器++，就是指针往前走的过程，注意返回的是迭代器。
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; }
->
在讲->重载之前，先看一下这个示例：
struct AA { AA(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} int _a1; int _a2; }; list<AA> lt; lt.push_back(AA(1, 1)); lt.push_back(AA(2, 2)); lt.push_back(AA(3, 3)); list<AA>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << endl; ++it; } cout << endl;
在这里就访问不了，因为自定义类型不支持类型。
这里我们回顾一下之前的知识，对与内置类型的指针，我们可以采用*来进行解引用。对于自定义类型的指针，我们要用->来进行解引用。
int* p = new int; *p = 1; AA* ptr = new AA; ptr->_a1 = 1;
实现->
T* operator->() { return &_node->_data; }
==
两个迭代器进行比较，就是两个指针比较
bool operator==(const self& s) { return _node == s._node; }
const迭代器
在实现const迭代器之前，首先要知道一点，const迭代器是一个完全不一样的类，所以不能将非const迭代器前加const就变成const迭代器。
因此我们可以list类中在定义一个const迭代器：
typedef __list_const_iterator<T> const_iterator;
const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; }
在单独实现一个const迭代器的类：
template<class T> struct __list_const_iterator { .... }
const迭代器基本的功能与非const迭代器相似，只有在解引用时不同：
// *it = 10 const T& operator*() { return _node->_data; } // it->a1 = 10 const T* operator->() { return &_node->_data; }
测试一下：
void print_list(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { //*it = 10; cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list4() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); print_list(lt); }
但是这样实现，还是太冗余了，因为非const和const只有返回值不同，那么还有优化的空间吗？
我们看一下库里面的实现:
库里面定义只定义了同一个类模版的迭代器，只是这两个迭代器之间的摸版参数不同，实例化的参数不同，就是完全不一样的类型。也就是说把能靠模版实现的就写一份，让编译器搞。
所以我们可以将我们的迭代器进行进一步优化：
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; .... }
// T T& T* // T cosnt T& const T* template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; /*typedef __list_iterator<T> self;*/ typedef __list_iterator<T, Ref, Ptr> self; Node* _node; ... }
到这里，我们的迭代器就全部实现完了。
拓展：
在刚才的测试函数中，有一个print_list函数，但是这个测试函数里面的数据我们给定的是int,那我要是其他类型的呢，这个函数又该如何修改呢？
其实很简单：我们加一个摸版参数即可：
template<typename T> void print_list(const list<T>& lt) { typename list<T>::const_iterator it = lt.begin(); while (it != lt.end()) { //*it = 10; cout << *it << " "; ++it; } cout << endl; }
测试一下：
注意：这里我们没有用class这个摸版参数，这是因为：
list是一个未实例化的类模板，编译器不能去他里面去找
编译器就无法确定：list::const_iterator是内嵌类型，还是静态成员变量
前面加一个typename就是告诉编译器，这里是一个类型，等list实例化后再去类里面去取
拓展2：
如果要是将刚才的类在改造一下呢？
比如：
我要打印以下内容：
vector<string> v; v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); v.push_back("222222222222222222222"); v.push_back("222222222222222222222");
这个函数对于我们的printf_list就不适用了，因为我们的print_list就只适用于链表。
这里我们就可以写一个容器（container）的打印函数：
template<typename Container> void print_Container(const Container& con) { typename Container::const_iterator it = con.begin(); while (it != con.end()) { cout << *it << " "; ++it; } cout << endl; }
测试结果：
总结一下：
摸版实现了泛型编程，而泛型编程的本质，就是本来我们干的活，交给了编译器。
相关函数接口：
有了迭代器的实现，我们就可以实现一下链表的相关接口：
Insert：
Insert:在pos位置之前插入：
iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* newnode = new Node(x); Node* prev = cur->_prev; // prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return iterator(newnode); }
Insert迭代器不会产生失效的问题，因为没有扩容。
erase:
在指定位置删除：
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); }
注意：erase的迭代器会失效，所以我们加个返回值。
实现了insert和erase后，我们就可以服用来实现头插，头删，尾插，尾删。
push_front与pop_fronr
具体实现：
头插：
//头插 void push_front(const T& x) { insert(begin(), x); }
头删：
//头删 void pop_front() { erase(begin()); }
push_back与pop_back
具体实现：
尾插：
void push_back(const T& x) { insert(end(), x); }
尾删：
//尾删 void pop_back() { erase(--end()); }
size:
为了方便计算大小，我们还可以再实现一个函数：
size_t size() { return _size; }
clear与析构：
clear：清理空间，我们可以采取迭代器访问的方式，逐个将节点释放。
//清理空间： void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
析构：我们可以先清理空间，在将头节点释放即可。
//析构 ~list() { clear(); delete _head; _head = nullptr; }
拷贝构造：
我们可以采用范围for来进行拷贝构造：
//拷贝构造： // lt2(lt1) //list(const list<T>& lt) list(list<T>& lt) { empty_init(); for (auto e : lt) { push_back(e); } }
赋值重载：
传统写法：
list<int>& operator=(const list<int>& lt) { if (this != <) { clear(); for (auto e : lt) { push_back(e); } } return *this; }
现代写法：
void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } // lt3 = lt1 list<int>& operator=(list<int> lt) { swap(lt); return *this; }
对比vector与list
