我在尝试使用类似 STL 的内部迭代器创建双向链表时编写了以下代码。我现在只提供头文件，其中不相关的部分被暂时删除。

我的问题是...

1. STL 以特定方式使用迭代器 - 具体来说，您在 STL 容器中导航，从 .begin() 迭代器向上但不包括 .end() 迭代器。为此，.end() 迭代器必须位于容器末尾之后。鉴于我已经开始(这是主要问题)，我将如何实现这种语义？

2. 目前的界面中是否缺少任何东西(关于迭代器类和应该存在于其中的东西)？

代码如下:

template <typename T>
class Node
{
    T data;
    Node<T>* next;
    Node<T>* prev;
};

template <typename T>
class LinkedList
{
    public:

        class Iterator
        {
            public:

                Iterator() {}
                explicit Iterator(const Node<T>& init) { current = init; }

                //Dereference operator - return the current node's data.
                inline T& operator*() { return current->data; }

                //Prefix returns by reference.
                inline Iterator& operator++()   { current = current->next; return *this; } 
                inline Iterator& operator--()   { current = current->prev; return *this; }

                //Postfix returns non-reference and has int parameter to differentiate function signature.
                inline Iterator operator++(int) { Iterator res = *this; current = current->next; return res; }
                inline Iterator operator--(int) { Iterator res = *this; current = current->prev; return res; }

            private:

                Node<T>* current;
        };

        Iterator begin() { return Iterator(m_start); }
        Iterator end()   { return Iterator(m_end);   }

    private:
        Node<T>* m_start;
        Node<T>* m_end;
};

我知道我可能会或可能不会遇到++/-- 运算符的问题，但这并不特别困扰我，因为当我有足够的代码对此进行一些测试时，我会解决这些问题.如果您愿意，请随时提出提示 :)

最佳答案

1. end() 返回的迭代器必须是可递减的，否则您不能反向迭代列表。 您可以通过让 Iterator 存储两个指针来做到这一点:指向当前节点(结束时为 NULL)和指向前一个节点(允许您找到其中包含数据的最后一个节点，即使 current == NULL 。

   class Iterator
   {
       public:
   
           Iterator() {}
           explicit Iterator(Node<T>* curr, Node<T>* prev):
               current(curr), previous(prev) {}
   
           //Dereference operator - return the current node's data.
           inline T& operator*() { return current->data; }
   
           //Prefix returns by reference.
           inline Iterator& operator++()   
           { 
               previous = current;
               current = current->next; 
               return *this; 
           } 
           inline Iterator& operator--()   
           { 
               current = previous; 
               previous = current->previous;
               return *this; 
           }
   
           //Postfix should be implemented in terms of prefix operators
           inline Iterator operator++(int) { Iterator res = *this; ++*this; return res; }
           inline Iterator operator--(int) { Iterator res = *this; --*this; return res; }
   
       private:
   
           Node<T>* current;
           Node<T>* previous;
   };
   
   Iterator begin() { return Iterator(m_start, 0); }
   Iterator end()   { return Iterator(0, m_end);   }
   

   或者，您可以让您的列表包含一个标记节点，该节点指定列表的“尾数”。但是这个节点不应该有数据成员。这可以通过将 Node 类拆分为仅包含指向下一个和上一个节点的指针的非模板基类来实现。

   例如，GCC 的列表实现似乎存储了一个指向哨兵的指针，因此它的 next 指向列表中的第一项，而它的 prev 指向列表中的最后一项(如果列表为空，则两者都指向自身)。

2. 您缺少 operator->、operator== 和 operator!=，可以从中继承的分类 typedef std::iterator ，一个 const_iterator 实现(迭代器应该可以隐式转换为 const_iterator)。

关于c++ - 迭代器实现问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8548467/