28
\$\begingroup\$

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?

\$\endgroup\$
30
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is a bit confusing, isn't that std::iterator is deprecated in C++17? If so, than how this should be updated to workaround the future deprecation state? \$\endgroup\$ – Evgeny Bobkin Aug 29 '18 at 7:37
  • \$\begingroup\$ Yes, you are correct, std::iterator is being deprecated, but it was a class that just contained typedefs for its template arguments, so it suffices to simply write each of the required typedefs as members of the iterator class instead. \$\endgroup\$ – glampert Aug 30 '18 at 23:06
13
\$\begingroup\$

The requirements for a forward iterator are:

It is a refinement of:

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).
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.