链表类的自定义迭代器

template <class T>
struct node
{
    T data;
    node *next;
};

template <class T>
class LinkedList
{
    private :
    node<T> *start;
    unsigned int numElements;
    // Assume all functions are implemented
};

class iterator : public std::iterator<std::forward_iterator_tag,node<T>*>
{
    node<T>* itr;

    public :

    iterator (node<T>* temp) : itr(temp) {}
    iterator (const iterator& myitr) : itr(myitr.itr) {}
    iterator& operator++ 
    {
        itr = itr->next;
        return *this;

    }
    bool operator== (const iterator& rhs) 
    {
        return itr == rhs.itr;

    }
    bool operator!= (const iterator& rhs) 
    {
        return itr != rhs.itr;

    }
    T& operator*()
    {
        return itr->data;
    }

};

#1 楼

您的迭代器缺少一些重要的细节：


您应该提供前后递增运算符（++it和it++）。当前，您只有预递增版本。


提供->运算符也可能很好，因为有些人喜欢it->something语法而不是(*it).something语法。


比较和解引用运算符应为const。请记住常量正确性。


复制构造函数只是对基础数据执行成员复制，因此您无需提供一个副本即可让编译器默认它。


Standard Library容器始终提供两种迭代器，即指向可变数据的iterator类型和指向不可变数据的const_iterator类型。通过提供转换操作符并继承std::iterator（请参见下面的示例），很容易使您的类同时支持（请参见以下示例）。


确定在递增和取消引用时应采取哪种操作方式无效的迭代器。例如：list.end()++;。它应该触发一个断言吗？抛出异常？什么都不做，就像现在一样？我至少会断言来帮助调试过程。您可能会发现在上下文中更合适的异常。


以上几点适用于您的代码：

#include <cassert>      // assert
#include <cstddef>      // ptrdiff_t
#include <iterator>     // iterator
#include <type_traits>  // remove_cv
#include <utility>      // swap

template
<
    class Type,
    class UnqualifiedType = std::remove_cv_t<Type>
>
class ForwardIterator 
    : public std::iterator<std::forward_iterator_tag,
                           UnqualifiedType,
                           std::ptrdiff_t,
                           Type*,
                           Type&>
{
    node<UnqualifiedType>* itr;

    explicit ForwardIterator(node<UnqualifiedType>* nd) 
        : itr(nd) 
    { 
    }

public:

    ForwardIterator()   // Default construct gives end.
        : itr(nullptr) 
    { 
    }

    void swap(ForwardIterator& other) noexcept
    {
        using std::swap;
        swap(itr, other.iter);
    }

    ForwardIterator& operator++ () // Pre-increment
    {
        assert(itr != nullptr && "Out-of-bounds iterator increment!");
        itr = itr->next;
        return *this;
    }

    ForwardIterator operator++ (int) // Post-increment
    {
        assert(itr != nullptr && "Out-of-bounds iterator increment!");
        ForwardIterator tmp(*this);
        itr = itr->next;
        return tmp; 
    }

    // two-way comparison: v.begin() == v.cbegin() and vice versa
    template<class OtherType>
    bool operator == (const ForwardIterator<OtherType>& rhs) const
    {
        return itr == rhs.itr;
    }
    
    template<class OtherType>
    bool operator != (const ForwardIterator<OtherType>& rhs) const
    {
        return itr != rhs.itr;
    }

    Type& operator* () const
    {
        assert(itr != nullptr && "Invalid iterator dereference!");
        return itr->data;
    }

    Type& operator-> () const
    {
        assert(itr != nullptr && "Invalid iterator dereference!");
        return itr->data;
    }

    // One way conversion: iterator -> const_iterator
    operator ForwardIterator<const Type>() const
    {
        return ForwardIterator<const Type>(itr);
    }
};

// `iterator` and `const_iterator` used by your class:
typedef ForwardIterator<T> iterator;
typedef ForwardIterator<const T> const_iterator;

注意：在示例中，我假设列表的末尾或无效的迭代器都由空指针标记。如果您使用其他方法（例如虚拟哨兵节点），则需要进行更改。

#2 楼

正向迭代器的要求是：


正向迭代器

它是对：



Input Iterator的改进。
Output Iterator
Trivial Iterator
股票可比
默认可构造
可分配

如果阅读所有这些规范，则必须定义以下这些： br />

预增量
后增量
取消引用（读/写）
默认可构造
复制可构造
赋值运算符
交换
后增量和取消引用
后增量和分配
成员访问（->当取消引用返回带有成员的对象时）。
与==和！=

还必须定义以下类型：


值类型
您丢失了：


类型。
后递增
默认可构造的（这使您等效于任何列表的结尾）。
成员访问（->取消访问时，引用返回带有成员的对象）。

评论

---

\ $ \ begingroup \ $
sgi链接不再可用。
\ $ \ endgroup \ $
– Kamiccolo
18年1月16日在13:22

---

\ $ \ begingroup \ $
SGI现在在这里托管：martinbroadhurst.com/stl
\ $ \ endgroup \ $
–马丁·约克
19年2月14日在21:01

---

\ $ \ begingroup \ $
但是您可以在这里查询所有这些术语：en.cppreference.com/w/cpp（或通过阅读标准）。
\ $ \ endgroup \ $
–马丁·约克
19年2月14日在21:04

---