How to avoid code duplication implementing const and non-const iterators?

Solution 1:

[The best answer was, unfortunately, deleted by a moderator because it was a link-only answer. I understand why link-only answers are discouraged; deleting it, however, has robbed future seekers of very useful information. The link has remained stable for more than seven years and continues to work at the time of this writing.]

I strongly recommend the original Dr. Dobb's Journal article by Matt Austern entitled "The Standard Librarian: Defining Iterators and Const Iterators", January 2001. Should that link go bad, now that Dr. Dobb's has ceased operating, it's also available here.

To prevent this replacement answer from being deleted, I will summarize the solution.

The idea is to implement the iterator once as a template that takes an extra template parameter, a boolean that says whether or not this is the const version. Anywhere in the implementation where the const and non-const versions differ, you use a template mechanism to select the correct code. Matt Austern's mechanism was called choose. It looked like this:

template <bool flag, class IsTrue, class IsFalse>
struct choose;

template <class IsTrue, class IsFalse>
struct choose<true, IsTrue, IsFalse> {
   typedef IsTrue type;
};

template <class IsTrue, class IsFalse>
struct choose<false, IsTrue, IsFalse> {
   typedef IsFalse type;
};

If you had separate implementations for const and non-const iterators, then the const implementation would include typedefs like this:

typedef const T &reference;
typedef const T *pointer;

and the non-const implementation would have:

typedef T &reference;
typedef T *pointer;

But with choose, you can have a single implementation that selects based on the extra template parameter:

typedef typename choose<is_const, const T &, T &>::type reference;
typedef typename choose<is_const, const T *, T *>::type pointer;

By using the typedefs for the underlying types, all the iterator methods can have an identical implementation. See Matt Austern's complete example.

Solution 2:

Since C++11/14 you can avoid such little helpers an deduce the constness directly from a boolean template.

constness.h:

#ifndef ITERATOR_H
#define ITERATOR_H
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <iterator>

struct dummy_struct {
  int hello = 1;
  int world = 2;
  dummy_struct() : hello{ 0 }, world{ 1 }{ }
};

template< class T >
class iterable {
  public:
    template< bool Const = false >
    class my_iterator {
      public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        /* deduce const qualifier from bool Const parameter */
        using reference = typename std::conditional_t< Const, T const &, T & >;
        using pointer = typename std::conditional_t< Const, T const *, T * >;

      protected:
        pointer i;

      public:
        my_iterator( T* _i ) : i{ reinterpret_cast< pointer >( _i ) } { }

        /* SFINAE enables the const dereference operator or the non 
           const variant
           depending on bool Const parameter */          
        template< bool _Const = Const >
        std::enable_if_t< _Const, reference >
        operator*() const {
          std::cout << "Const operator*: ";
          return *i;
        }

        template< bool _Const = Const >
        std::enable_if_t< !_Const, reference >
        operator*() {
          std::cout << "Non-Const operator*: ";
          return *i; 
        }

        my_iterator & operator++() {
          ++i;
          return *this;
        }
        bool operator!=( my_iterator const & _other ) const {
          return i != _other.i;
        }

        bool operator==( my_iterator const & _other ) const {
          return !( *this != _other );
        }   
    };  



  private:
    T* __begin;
    T* __end; 
  public:
    explicit iterable( T* _begin, std::size_t _count ): __begin{ _begin }, __end{ _begin + _count } { std::cout << "End: " << __end << "\n"; }

    auto begin()  const { return my_iterator< false >{ __begin }; }
    auto end()    const { return my_iterator< false >{ __end }; }

    auto cbegin() const { return my_iterator< true >{ __begin }; }
    auto cend()   const { return my_iterator< true >{ __end }; }
};
#endif

This can be used with something like that:

#include <iostream>
#include <array>
#include "constness.h"

int main() {

  dummy_struct * data = new dummy_struct[ 5 ];
  for( int i = 0; i < 5; ++i ) {
    data[i].hello = i;
    data[i].world = i+1;
  } 
  iterable< dummy_struct > i( data, 5 );

  using iter = typename iterable< dummy_struct >::my_iterator< false >;
  using citer = typename iterable< dummy_struct >::my_iterator< true >;

  for( iter it = i.begin(); it != i.end(); ++it  ) {
    std::cout << "Hello: " << (*it).hello << "\n"
              << "World: " << (*it).world << "\n";
  }

  for( citer it = i.cbegin(); it != i.cend(); ++it  ) {
    std::cout << "Hello: " << (*it).hello << "\n"
              << "World: " << (*it).world << "\n";
  }
  delete[] data;

}

Solution 3:

STL uses inheritance

template<class _Myvec>
    class _Vector_iterator
        : public _Vector_const_iterator<_Myvec>

Solution 4:

In addition to the suggestion that you might templatize the constness and non-constness, you could also reduce the amount of work by taking a look at Boost.Iterator tutorial - which also mentions the same solution.