前言：
最近学习了c++list的实现，这让我对迭代器的理解又上升了一个新的高度，注意：代码里的list是放在一个叫zgw的命名空间里边，但是在实现list的代码中没有加namespace，这里给个注意，以后复习时能看懂。
list的节点：
我们首先需要搞出一个list的节点，来存储数据，以及节点的下一个指针，和节点的上一个指针，STL库里边这样设计的，所以我们这样设计：
template< class T>
struct ListNode
{
struct ListNode<T>* _next;
struct ListNode<T>* _prev;
T _data;
ListNode(const T& data = T()) //这里给的是匿名对象
:_next(nullptr),
_prev(nullptr),
_data(data) {};
};设计这个节点应该是没有什么难度的。
包装list类：
template<class T>
class list
{
typedef ListNode<T> node;
public:
list() :_head(new node())
{
_head->_next = _head;
_head->_prev = _head;
}
private:
node* _head;
};为了让我们的list更加具有可读性，我们将，ListNode<T>重命名为node。然后我们要给一个list的无参构造，相信到现在都能看得懂。
迭代器的设计：
前方高能！！！
然后就是上强度的地方，我们需要设计list的迭代器。我们先分析一下list指针与vector的指针又什么区别呢？
首先我们list存的是ListNode<T>节点的指针，每一个新的节点都是new出来的，而且是通过指针将他们链接起来，他在物理层面上就不是连续的。
所以当我们解引用就不是一个内置类型，或者是已经设计好的自定义类型，它就没有了重载运算符，因为我们的节点就是我们自己定义的自定义类型。就算是迭代器也必要支持重载运算符。
我们举一个例子
vector的例子，当我们要搞一个存储int数据的vector容器。
void Test4()
{
vector<int> v1 = { 1,2,3,4 };
vector<int>::iterator it1 = v1.begin();
cout << *it1 << endl;
}这里我们是存储int内置类型，当我们解引迭代器时，实际是解引用int类型的指针，然后也支持流插入，所以可以直接打印第一个元素。
我后我们再想我们如果要用vector存储一个我们自己搞的一个类型，是否还支持流插入呢？
class aa
{
aa(int a=10,int b=20):
_a(a),_b(b)
{}
private:
int _a;
int _b;
};
void Test4()
{
vector<aa> v1 ;
aa a1;
v1.push_back(a1);
vector<aa>::iterator it1 = v1.begin();
cout << *it1 << endl;
}上面这个代码会不会报错呢？当然肯定会的，为什么呢？
就是因为我们没有重载流插入。
所以通过这个例子我们应该明白了，我们ListNode本生就是一个我们自己设计的类型，所以当我们在list返回ListNode指针再解引用时肯定是不行的，因为我们没有为ListNode设计重载运算符，但是我们在这有一个新的思路我们能不能再设计一个类，当做list的迭代器，这个类迭代器存ListNode类型的指针。
在第一次听到这个设计我也是很懵逼的，都是再通过我看了两遍教学课程，再加上自己研究了一个下午，终于是领悟了其中的原理，所以想好好理解还是得自己研究。
设计的源码：
namespace zgw
{
//结构体定义
template< class T>
struct ListNode
{
struct ListNode<T>* _next;
struct ListNode<T>* _prev;
T _data;
ListNode(const T& data = T())
:_next(nullptr),
_prev(nullptr),
_data(data) {};
};
template <class T,class Ref,class Ptr>//我们设计三个参数的模板迭代器，以便我们返回对应的指针
struct ListIterator //和引用（在这里的我们需要设计const_iterator,以及
{ //iterator两种类型的迭代器，然后我们再通过typedef
typedef ListNode<T> node; //封装一下，提高可读性
typedef ListIterator<T,Ref,Ptr> Self;
ListIterator(node*head) :
_node(head)
{};
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self re(_node);
_node = _node->_next;
return re;
}
bool operator==(const Self&node)
{
return _node == node._node;
}
bool operator!=(const Self& node)
{
return _node != node._node;
}
node* _node;
};
//封装链表,这只是一个头节点，当我们返回begin()，和end()时，
//我们其实返回的是一个ListNode<T>类型的指针
template<class T>
class list
{
typedef ListNode<T> node;
public:
typedef ListIterator<T,T&,T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
list() :_head(new node()) //当我们需要什么类型的迭代器就传对应的typedef
{
_head->_next = _head;
_head->_prev = _head;
}
const_iterator cbegin()
{
return const_iterator(_head->_next);
}
const_iterator cend()
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
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;
}
iterator insert(iterator pos,const T&data)
{
node* cur = pos._node;
node* newnode = new node(data);
node* prev = cur->_prev;
newnode->_next = cur;
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
return iterator(newnode);
}
iterator erase(iterator pos)
{
assert(pos != end()._node);
node* cur = pos._node;
node* prev=cur->_prev;
node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
void pop_back()
{
assert(_head != begin()._node);
node* tail= end()._node->_prev;
node* _head = end()._node;
tail->_prev->_next = _head;
_head->_prev = tail->_prev;
delete tail;
}
void pop_front()
{
erase(begin());
}
void push_front(const T&data)
{
insert(begin(), data);
}
private:
node* _head;
};
}