C++ STL中list迭代器的实现

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;
    // ...
}