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.

• Evgeny Bobkin: 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?
• glampert: 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.

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).

• Kamiccolo: sgi links are no longer available.
• Loki Astari: SGI now hosted here: martinbroadhurst.com/stl
• Loki Astari: But you can look up all these terms here: en.cppreference.com/w/cpp (or by reading the standard).