list 的模拟实现中，重难点在于迭代器功能的实现，因此本文只围绕 iterator 及 const_iterator 的设计进行介绍，其余如增删查改则不再赘述——在C语言的基础上，这些都非常简单。
与 string / vector 不同，list 的节点原生指针不能通过简单的 ++ / * 等实现迭代器，因此我们需要对节点指针进行封装，利用自定义类型支持运算符重载的性质，完成迭代器的设计。
为了与 STL中list 进行区分，我们在创建的命名空间内实现。
一、iterator 的实现
（双向带头循环）链表及其节点的结构设计：
push_back()：
void push_back(const T& x) { Node* newnode = new Node(x); Node* tail = _head->prev; tail->_next = newnode; newnode->_prev = tail; _head->_prev = newnode; newnode->_next = _head; }
我们很容易可以插入一组数据，但如果想遍历链表，同时对数据进行修改，则需要实现迭代器。
list 无法像 vector 一样简单地 ++/* 实现节点遍历，且原始指针也不支持对运算符重载，我们需要对 list节点的指针 进行封装。
template<class T> struct __list_iterator { typedef ListNode<T> Node; Node* _node;// 被封装的节点指针 // 迭代器的构造 __list_iterator(Node* node) :_node(node) {} };
struct __list_iterator { typedef __list_iterator<T> self; self operator++() { _node = _node->_next; return _node; } T& operator*() { return _node->_data; } };
实际上，编译器优化后，会直接用 _node 对等式左边的变量进行构造。
以此类推，后置++ / 前后置-- / != / == 等都很容易了。
二、const_iterator 及第二个模板参数的引入
const_iterator 不能通过对 iterator 加 const 实现：
const_iterator 是为了防止 list 节点的数据被修改；iterator 加 const 会让迭代器本身无法++/–，导致 const list 无法实现遍历——迭代器不能++/–
const_iterator 本身的功能很简单——防止 list 节点的数据被修改，我们只需要针对性的修改 * 重载，其余与普通迭代器没有区别。
const T& operator*() { return _node->_data; } // 普通迭代器 iterator: // T& operator*() —— 能对节点的数据进行修改
即：
template<class T> struct __list_const_iterator { // ... const T& operator*() { return _node->_data; } }; template<class T> class list { // ... typedef __list_const_iterator<T> const_iterator; }
仅有一个函数不同，而其余部分都一样（与 iterator 相比），这种做法不是很好。
因此，我们引入第二个模板参数。
template<class T, class Ref> struct __list_iterator { // ... Ref operator*() { return _node->_data; } } template<class T, class Ref> class list { typedef __list_iterator<T, T&> iterator; typedef __list_iterator<T, const T&> const_iterator; // ... }
- 用一个例子测试 const迭代器：
namespace MyList { void Print(const list<int>& lt) { for (auto& e : lt) { cout << e << " "; } cout << endl; } void test1() { list<int> lt; lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); Print(lt); } } int main() { test1(); return 0; }
三、箭头->重载
T* operator->() { return &(_node->_data); }
观察一下：it->_year ——> it.operator->()_year
此处 it.operator->() 的返回值是 Date* ，不应该写成 it->->_year 吗？
事实上，编译器在此处进行了优化，->-> 的写法反而错了
我们也可以引入第三个模板参数 Ptr ，这就就可以同时实现 T* 和 const T* 。
template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, Ref, Ptr> self; // ... }; template<class T> class list { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; // ... }
