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

Question

I'm implementing a custom container with an STL-like interface. I have to provide a regular iterator and a const iterator. Most of the code for the two versions of the iterators is identical . How can I avoid this duplication?

For example, my container class is Foo, and I'm implementating FooIterator and FooConstIterator. Both of the iterators have to provide methods like operator++() which are identical.

My question is similar to How do I remove code duplication between similar const and non-const member functions?, but the answer to that one is specific to const and non-const methods, especially accessors. I don't see how that might generalize to the iterator problem.

Should I have FooIterator derive from FooConstIterator and extend it with additional non-const methods? That either leads to virtual methods or method hiding, which seem inappropriate here.

Perhaps FooIterator should contain a FooConstIterator. Although that approach does reduce implementation duplication, it seems to re-introduce a lot of boilerplate method definitions.

Is there clever template technique for generating the two iterators from a single definition? Or perhaps there's a way to--shudder--use the preprocessor to stamp out these nearly identical classes.

I've tried looking at my local STL implementation to see how it handle this. There are so many helper classes that I'm having trouble grokking the design, but it looks like the functionality is simply duplicated.

In previous projects, my custom container was built on top of a standard STL container, so I didn't have to provide my own iterators. That's not an option in this case.

Anissaanita

Answer 1

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.

Anissaanita

But in STL, iterator classes are defined as a member classes of containers, so std::vector<int>::iterator is valid. Matt Austern's code defines the slist_iterator class to be an outside class of slist. – Mesarch

@user8385554: I think the idea is that Matt Austern's slist container would have typedefs for iterator and const_iterator to make the iterators available as though they were member types. – Anissaanita

@L.F.: The question was asked in 2010, before std::conditional_t was a thing. – Anissaanita

The original answer was also 2010, but it was link-only and the link eventually rotted. This recreated answer was 2016, but retains the context of the original question. It's true that std::conditional was a thing by 2016, but it wasn't yet implemented in all of the major compilers at that point. – Anissaanita

Funny, the last link is down. – Stephniestepladder

All your links are now dead, unfortunately. The Dr. Dobbs site does have some Jan '01 articles, but not this one, and the login is now broken anyway. – Hasheem

The two collaboration.cmc.ec.gc.ca links are dead ("The requested URL was not found on this server."), but the DrDobbs link is working now! It looks complementary though, as it mentions the choose template but not how to build it... – Ecumenical

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

}

Disagreeable

In C++ 11 you have to use typename std::conditional<B, T, F>::type because the helper type std::conditional_t is introduced in C++14. – Seafarer

Answer 3

STL uses inheritance

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

Koressa

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

Corell

Answer 5

You can use CRTP and a common base to "inject" methods (but you still have to duplicate ctors in current C++), or just use the preprocessor (no shuddering required; handles ctors easily):

struct Container {

#define G(This) \
This operator++(int) { This copy (*this); ++*this; return copy; }
// example of postfix++ delegating to ++prefix

  struct iterator : std::iterator<...> {
    iterator& operator++();
    G(iterator)
  };
  struct const_iterator : std::iterator<...> {
    const_iterator& operator++();
    G(const_iterator)
  };

#undef G
// G is "nicely" scoped and treated as an implementation detail
};

Use std::iterator, the typedefs it gives you, and any other typedefs you might provide to make the macro straight-forward.

Imam

Answer 6

Arthor O'Dwyer is answering this in detail in his blog post: https://quuxplusone.github.io/blog/2018/12/01/const-iterator-antipatterns/

In essence,

template<bool IsConst>
class MyIterator {
    int *d_;
public:
    MyIterator(const MyIterator&) = default;  // REDUNDANT BUT GOOD STYLE

    template<bool IsConst_ = IsConst, class = std::enable_if_t<IsConst_>>
    MyIterator(const MyIterator<false>& rhs) : d_(rhs.d_) {}  // OK
};
using Iterator = MyIterator<false>;
using ConstIterator = MyIterator<true>;
};

Also, add static_assert(std::is_trivially_copy_constructible_v<ConstIterator>); to your code, to make sure your iterators stay trivially copy constructible:

Conclusion: If you are implementing your own container iterators — or any other pair of types with this “one-way implicit converting” behavior, such as the Networking TS’s const_buffers_type and mutable_buffers_type — then you should use one of the patterns above to implement converting constructors without accidentally disabling trivial copyability.

Mickeymicki