C++: implementing const_iterator and non-const iterator without code duplication

C++ 11

C++ 11

Over the last couple of weeks I’ve been working on a custom data structure that provides iterators (both const and “regular” non-const) that adhere to the STL C++ ’11 standards. Having these iterators would make my life easier, as it allows me to use standard STL algorithms (like std::find) on my data structures. However, implementing this data structure and the appropriate iterators made my life miserable for a few hours. Especially the implementation the two iterators without duplicating code wasn’t as straight-forward as I hoped. Here’s how I did it – it might help you (and me, when I want to do this again in the future)

Most things are best explained by example – see below. Note that this will only work when using the C++11 standard (formerly known as C++0x). If you’re using G++ from the GNU Compiler Collection (GCC), the option to use is: -std=gnu++0x. Also note that this is not a "Iterators for Dummies" – I assume you’ve seen an iterator implementation before.

The example code snippet shows a template class MyDataStructure<ValueType> (storing elements of type ValueType). This class contains a nested template class const_noconst_iterator<bool>, which implements both the const iterator and the regular (non-const) iterator.

The crux lies in lines 16 and 22: depending on whether the boolean template parameter is_const_iterator is true or false, these lines define two different types of pointers to MyDataStructure and two different types of references to ValueType.

  • if is_const_iterator == true
    • DataStructurePointerType is defined as a const MyDataStructure*
    • ValueReferenceType is defined as a const ValueType&
  • if is_const_iterator == false
    • DataStructurePointerType is defined as a MyDataStructure*
    • ValueReferenceType is defined as a ValueType&

These typedefs are subsequently used to determine the parameter and return types of a number of methods in the iterator – effectively instantiating both a const and a regular iterator. Any questions? Drop a comment and I might reply.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
 * Our data structure (e.g., a linked list)
 */
template <class ValueType>;
class MyDataStructure {
  /**
   * Inner class that describes a const_iterator and 'regular' iterator at the same time, depending
   * on the bool template parameter (default: true - a const_iterator)
   */
  template<bool is_const_iterator = true>
  class const_noconst_iterator : public std::iterator<std::bidirectional_iterator_tag, ValueType> {
    /**
     * For const_iterator:   define DataStructurePointerType to be a   const MyDataStructure*
     * For regular iterator: define DataStructurePointerType to be a   MyDataStructure*
     */
    typedef typename std::conditional<is_const_iterator, const MyDataStructure*, MyDataStructure*>::type DataStructurePointerType;
 
    /**
     * For const_iterator:   define ValueReferenceType to be a   const ValueType&
     * For regular iterator: define ValueReferenceType to be a   ValueType&
     */
    typedef typename std::conditional<is_const_iterator, const ValueType&, ValueType&>::type ValueReferenceType;
 
    /**
     * Regular constructor: set up your iterator.
     */
    const_noconst_iterator(DataStructurePointerType pointer_to_datastructure) : _datastructure(pointer_to_datastructure) {
      // You might want to do something here, but not necessarily
    }
 
    /**
     * Copy constructor. Allows for implicit conversion from a regular iterator to a const_iterator
     */
    const_noconst_iterator(const const_noconst_iterator<false>& other) : _datastructure(other._datastructure) {
      // Copy constructor. Depending on your iterator, you might want to add something here.
    }
 
    /**
     * Equals comparison operator
     */
    bool operator== (const const_noconst_iterator& other) const {
      // Up to you to define
    }
 
    /**
     * Not-equals comparison operator
     * @see operator==(const const_noconst_iterator&) const
     */
    bool operator!= (const const_noconst_iterator& other) const {
      return !(*this == other);
    }
 
    /**
     * Dereference operator
     * @return the value of the element this iterator is currently pointing at
     */
    ValueReferenceType operator*() {
      // Up to you to define: get a reference to an element in your data structure
    }
 
    /**
     * Prefix decrement operator (e.g., --it)
     */
    const_noconst_iterator &operator--(){
      // Up to you to define: move iterator backwards
    }
 
    /**
     * Postfix decrement operator (e.g., it--)
     */
    const_noconst_iterator operator--(int){
      // Use operator--()
      const const_noconst_iterator old(*this);
      --(*this);
      return old;
    }
 
    /**
     * Prefix increment operator (e.g., ++it)
     */
    const_noconst_iterator &operator++(){
      // Up to you to define: move iterator forwards
    }
 
    /**
     * Postfix increment operator (e.g., it++)
     */
    const_noconst_iterator operator++(int){
      // Use operator++()
      const const_noconst_iterator old(*this);
      ++(*this);
      return old;
    }
 
    /**
     * Make const_noconst_iterator<true> a friend class of const_noconst_iterator<false> so
     * the copy constructor can access the private member variables.
     */
    friend class const_noconst_iterator<true>;
 
  private:
    DataStructurePointerType _list; // store a reference to MyDataStructure
 
  } // end of nested class const_noconst_iterator
 
  /**
   * Shorthand for a regular iterator (non-const) type for MyDataStructure.
   */
  typedef const_noconst_iterator<false> iterator;
 
  /**
   * Shorthand for a constant iterator (const_iterator) type for a MyDataStructure.
   */
  typedef const_noconst_iterator<true> const_iterator;
 
  // (...)
} // end of class MyDataStructure