Iterators: What Must Be Done?

Whenever I need to implement a custom iterator type in C++ I immediately remember nothing about what the standard has to say about the requirements for each iterator category, so here is a collation of cppreference links and examples describing what must be done to implement a custom iterator type.

Iterator

All iterator types must be CopyConstructible, CopyAssignable, Destructible, and Swappable; have the member types required by std::iterator_traits; and support the following expressions.

struct iterator {
  using difference_type = std::ptrdiff_t;
  using value_type = ?;
  using pointer = value_type*;
  using reference = value_type&;
  using iterator_category = ?;

  iterator(const iterator& rhs);
  iterator(iterator&& rhs);
  iterator& operator=(const iterator& rhs);
  iterator& operator=(iterator&& rhs);
  void swap(iterator& iter);

  reference operator*();

  iterator& operator++();
};

void swap(iterator& lhs, iterator& rhs);

InputIterator

In addition to the Iterator requirements, an InputIterator must also be EqualityComparable and support the following expressions.

struct input_iterator {
  using difference_type = std::ptrdiff_t;
  using value_type = ?;
  using pointer = value_type*;
  using reference = value_type&;
  using iterator_category = std::input_iterator_tag;

  input_iterator(const input_iterator& rhs);
  input_iterator(input_iterator&& rhs);
  input_iterator& operator=(const input_iterator& rhs);
  input_iterator& operator=(input_iterator&& rhs);
  void swap(input_iterator& iter);

  bool operator==(const input_iterator& rhs);
  bool operator!=(const input_iterator& rhs);

  reference operator*();
  pointer operator->();

  input_iterator& operator++();
  input_iterator& operator++(int);
};

void swap(input_iterator& lhs, input_iterator& rhs);

OutputIterator

In addition to the Iterator requirements, an OutputIterator must also be a class type or a pointer type and support the following expressions.

struct output_iterator {
  using difference_type = std::ptrdiff_t;
  using value_type = ?;
  using pointer = value_type*;
  using reference = value_type&;
  using iterator_category = std::output_iterator_tag;

  output_iterator(const output_iterator& rhs);
  output_iterator(output_iterator&& rhs);
  output_iterator& operator=(const output_iterator& rhs);
  output_iterator& operator=(output_iterator&& rhs);
  void swap(output_iterator& iter);

  reference operator*();

  output_iterator& operator++();
  output_iterator operator++(int);
};

void swap(output_iterator& lhs, output_iterator& rhs);

ForwardIterator

In addition to the InputIterator requirements, a ForwardIterator must also be DefaultConstructible; support multiple iteration passes; std::iterator_traits<forward_iterator>::reference must be exactly T& satisfies OutputIterator or exactly const T& otherwise; and support the following expressions.

struct forward_iterator {
  using difference_type = std::ptrdiff_t;
  using value_type = ?;
  using pointer = value_type*;
  using reference = value_type&;
  using iterator_category = std::forward_iterator_tag;

  forward_iterator();
  forward_iterator(const forward_iterator& rhs);
  forward_iterator(forward_iterator&& rhs);
  forward_iterator& operator=(const forward_iterator& rhs);
  forward_iterator& operator=(forward_iterator&& rhs);
  void swap(forward_iterator& iter);

  bool operator==(const forward_iterator& rhs);
  bool operator!=(const forward_iterator& rhs);

  reference operator*();
  pointer operator->();

  forward_iterator& operator++();
  forward_iterator operator++(int);
};

void swap(forward_iterator& lhs, forward_iterator& rhs);

BidirectionalIterator

In addition to the ForwardIterator requirements, a BidirectionalIterator must also support the following expressions.

struct bidirectional_iterator {
  using difference_type = std::ptrdiff_t;
  using value_type = ?;
  using pointer = value_type*;
  using reference = value_type&;
  using iterator_category = std::bidirectional_iterator_tag;

  bidirectional_iterator();
  bidirectional_iterator(const bidirectional_iterator& rhs);
  bidirectional_iterator(bidirectional_iterator&& rhs);
  bidirectional_iterator& operator=(const bidirectional_iterator& rhs);
  bidirectional_iterator& operator=(bidirectional_iterator&& rhs);
  void swap(bidirectional_iterator& iter);

  bool operator==(const bidirectional_iterator& rhs);
  bool operator!=(const bidirectional_iterator& rhs);

  reference operator*();
  pointer operator->();

  bidirectional_iterator& operator++();
  bidirectional_iterator operator++(int);
  bidirectional_iterator& operator--();
  bidirectional_iterator operator--(int);
};

void swap(bidirectional_iterator& lhs, bidirectional_iterator& rhs);

RandomAccessIterator

In addition to the BidirectionalIterator requirements, a RandomAccessIterator must support the following expressions.

struct random_access_iterator {
  using difference_type = std::ptrdiff_t;
  using value_type = ?;
  using pointer = value_type*;
  using reference = value_type&;
  using iterator_category = std::random_access_iterator_tag;

  random_access_iterator();
  random_access_iterator(const random_access_iterator& rhs);
  random_access_iterator(random_access_iterator&& rhs);
  random_access_iterator& operator=(const random_access_iterator& rhs);
  random_access_iterator& operator=(random_access_iterator&& rhs);
  void swap(random_access_iterator& iter);

  bool operator==(const random_access_iterator& rhs);
  bool operator!=(const random_access_iterator& rhs);
  bool operator<(const random_access_iterator& rhs);
  bool operator<=(const random_access_iterator& rhs);
  bool operator>(const random_access_iterator& rhs);
  bool operator>=(const random_access_iterator& rhs);

  reference operator*();
  pointer operator->();
  reference operator[](difference_type n);

  random_access_iterator& operator++();
  random_access_iterator operator++(int);
  random_access_iterator& operator+=(difference_type n);
  random_access_iterator operator+(difference_type n);
  random_access_iterator& operator--();
  random_access_iterator operator--(int);
  random_access_iterator& operator-=(difference_type n);
  random_access_iterator operator-(difference_type n);
};

void swap(random_access_iterator& lhs, random_access_iterator& rhs);

Summary

There they are, code snippets to get started implementing custom iterator types in C++. I will find these useful in future, I hope you do too. If there are any mistakes or glaring omissions please let know.