【C++】list容器迭代器的模拟实现

? ? ? ? list容器内部基本都是链表形式实现，这里的迭代器实现的逻辑需要注意C语言中指针的转换。

????????list容器如同数据结构中的队列，通常用链式结构进行存储。在这个容器中，我们可以模仿系统的逻辑，在头结点后设置一个“ 哨兵 ”，此结点前指头结点，后指尾结点，如下图：

? ? ? ? 为保可以装纳所有类型的数据，因此，这里我们需使用类模板，结点结构设置框架如下：

template<class T> //模板
struct ListNode
{
?? ?ListNode<T>* _next;? ?//指向前结点的指针
?? ?ListNode<T>* _last;? //指向后结点的指针
?? ?T _data;

? ??//因不确定数据类型，所以使用T类型的默认构造
?? ?ListNode(const T& x = T())
?? ??? ?:_next(nullptr)
?? ??? ?, _last(nullptr)
?? ??? ?, _data(x)
?? ?{ ?}
};

? ? ? ? 显然，迭代器也需使用类模板，这里要注意的是迭代器的构造函数，下面是模拟实现迭代器的构造函数，前置++(或--)，后置++(或--)，解引用操作，!=和==运算符重载的运用：

template<class T>
struct __list_iterator
{
?? ?typedef ListNode<T> Node; ?//类型结点
?? ?typedef __list_iterator<T> self; ?//类型迭代器
?? ?Node* _node; //结点

?? ?//构造函数

?? ?__list_iterator(Node* x)
?? ??? ?:_node(x)
?? ?{???}

?? ?// ++it，即后置++
?? ?self& operator++()
?? ?{
?? ??? ?_node = _node->_next;
?? ??? ?return *this;
?? ?}

?? ?// it++，即前置++
?? ?self operator++(int)
?? ?{
?? ??? ?self t(*this);

?? ??? ?_node = _node->_next;

?? ??? ?return t;
?? ?}

?? ?// --it，即后置--

?? ?self& operator--()
?? ?{
?? ??? ?_node = _node->_last;
?? ??? ?return *this;
?? ?}

?? ?// it--，即前置--

?? ?self operator--(int);
?? ?{
?? ??? ?self t(*this);
?? ??? ?_node = _node->_last;
?? ??? ?return t;
?? ?}

? ? //解引用，即访问结点中的数据

?? ?T& operator*()
?? ?{
?? ??? ?return _node->_data;
?? ?}

? ? //以下是运算符重载

?? ?bool operator!=(const self& s)
?? ?{
?? ??? ?return _node != s._node;
?? ?}

?? ?bool operator==(const self& s)
?? ?{
?? ??? ?return _node == s._node;
?? ?}
};

? ? ? ? 迭代器的目前其它初级功能实现与以上类似，这里就不在一一列举，后面会专门运用模拟迭代器的使用，这里先了解其语法和逻辑使用。