Custom iterator for a linked list class

Question

I have made a LinkedList class. This is a singly-linked-list and I want to make a forward_iterator for this class without using Boost. I have made the code and I want to know whether I have implemented it correctly. The source I referred to make this code is here.

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

Iterator Code :

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

};

Is the above implementation correct? If not, then what changes should I make? Also, does anything else need to be implemented?

Answer 1

Your iterator is missing a few important details:

• You should provide the pre- and post-increment operators (++it and it++). Currently, you only have the pre-increment version.

• It might also be good to provide the -> operator, since some people prefer the it->something syntax over the (*it).something one.

• The comparison and dereference operators should be const. Remember Const Correctness.

• The copy constructor is just performing a memberwise copy of the underlying data, so you don't need to provide one and can let the compiler default it.

• The Standard Library containers always provide two flavors of iterators, the iterator type, pointing to mutable data, and the const_iterator type, pointing to immutable data. It is easy to adapt your class to support both by providing a conversion operator and inheriting from std::iterator (see the following example).

• Decide which course of action should be taken when incrementing and dereferencing an invalid iterator. E.g.: list.end()++;. Should it trigger an assertion? Throw an exception? Do nothing as it is now? I would at least assert to help the debugging process. You might find exceptions more appropriate in your context.

The above points applied to your code:

#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;

Note: In the example, I've assumed that the end of your list or an invalid iterator are marked by a null pointer. You'll need to change that if you are using some other method, such as a dummy sentry node.

Answer 2

The requirements for a forward iterator are:

• Forward Iterator

It is a refinement of:

• Input Iterator
• Output Iterator
• Trivial Iterator
• Equity Comparable
• Default Constructable
• Assignable

If you read through all those specs you must define these:

• Preincrement
• Postincrement
• Dereference (Read/Write)
• Default Constructable
• Copy Constructable
• Assignment operator
• swap
• Postincrement and de-reference
• Postincrement and assignment
• Member accesses (-> when de-referencing returns an object with members).
• Comparable with == and !=

You must also define these types:

• Value type
• Distance type

You are missing:

• The types.
• Postincrement
• Default Constructable (This gives you the equivalent of end of any list).
• swap
• Member accesses (-> when de-referencing returns an object with members).