C++ Const Iterator

   blog 12 minutes read (About 1769 words)  visits

Introduction

Iterator is a key concept for C++ STL. When we implement a custom container for C++, we will also have to implement the iterator class for the custom container. In my previous blog post “C++ Iterator”, I discussed about how to implement C++ iterator using nested class inside a certain sequence container class for generic programming. Since C++14, a new const iterator class has been introduced, which is usually returned from the cbegin and cend container methods. In this blog post, I would like to discuss what C++ const iterator is and how to implement const iterator from scratch.

Constant Iterator

C++ iterator was introduced in C++11. Essentially, it is a pointer wrapper and dereferencing the iterator returns the object in the container by reference T&. If we forgot to cast a const to the returned reference, we might modify the objects in the container unintentionally. For example,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>
#include <iterator>
 
int main() 
{
    std::vector<int> v = { 3, 1, 4 };
    // vi is not a const iterator.
    // vi cannot even iterate since it is const.
    const auto vi = std::begin(v);
    std::cout << *vi << std::endl; 
    *vi = 8;
    std::cout << *vi << std::endl; 
}

Since C++14, a new const iterator class was introduced and the user cannot modify the container via const iterator. This time, dereferencing the const iterator returns the object in the container by const reference const T& and we cannot modify the objects in the container accidentally.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>
#include <iterator>
 
int main() 
{
    std::vector<int> v = { 3, 1, 4 };
    // vi is not a const iterator.
    auto vi = std::cbegin(v);
    std::cout << *vi << std::endl; 
    // Compile time error.
    // *vi = 8;
    std::cout << *vi << std::endl; 
}

Constant Iterator Implementation for Custom Container

Implementation With Code Duplication

The implementation of iterator and const iterator class are extremely similar, except that dereferencing returns T& for iterator and const T& for const iterator. We can just copy and paste most of the code for the iterator for implementing the const iterator. The drawback is there will be “code duplications”.

const_iterator_code_duplication.cpp
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
#include <algorithm>
#include <array>
#include <iostream>
#include <list>
#include <vector>

// Custom data structure with iterators
// For some additional implementations for Vector
// /blog/CPP-Const-Overloading/
template <typename T>
class DummyVector
{
public:
    // Default constructors
    DummyVector();
    // Constructors which take more than zero arguments
    explicit DummyVector(size_t size);
    explicit DummyVector(std::initializer_list<T> lst);

    // Iterator basics
    class Iterator;
    class ConstIterator;
    Iterator begin();
    Iterator end();
    ConstIterator cbegin();
    ConstIterator cend();

private:
    size_t mSize;
    T* mBuffer;
};

// However, the best practice for template classes and functions is to put the
// definition and the declaration together. Mainly, there are two reasons
// 1. Compiler needs to know all the definition for any templates during compile
// time
// 2. Namescope is trivial to write and confusing
template <typename T>
DummyVector<T>::DummyVector() : mSize{0}, mBuffer{nullptr}
{
}

template <typename T>
DummyVector<T>::DummyVector(size_t size) : mSize{size}, mBuffer{new T[size]}
{
    for (int i = 0; i < mSize; i++)
    {
        mBuffer[i] = 0;
    }
}

template <typename T>
DummyVector<T>::DummyVector(std::initializer_list<T> lst)
    : mSize{lst.size()}, mBuffer{new T[lst.size()]}
{
    std::copy(lst.begin(), lst.end(), this->mBuffer);
}

// Iterator is an abstract notion
template <typename T>
class DummyVector<T>::Iterator
{
public:
    // Constructor
    Iterator(T* ptr);
    // Compulsory methods
    // Prefix
    Iterator& operator++();
    Iterator& operator--();
    // Postfix
    // Returns the value before update
    // Impossible to return by reference
    // Return by value instead
    Iterator operator++(int);
    Iterator operator--(int);
    T& operator*();
    bool operator==(const Iterator& iter);
    bool operator!=(const Iterator& iter);

private:
    T* mPtr;
};

template <typename T>
DummyVector<T>::Iterator::Iterator(T* ptr) : mPtr{ptr}
{
}

// Prefix overloading
// If T::X is a dependent typename, then we need to prefix it by typename to
// tell the compiler to parse it in a certain way.
template <typename T>
typename DummyVector<T>::Iterator& DummyVector<T>::Iterator::operator++()
{
    this->mPtr++;
    return *this;
}
// Prefix overloading
template <typename T>
typename DummyVector<T>::Iterator& DummyVector<T>::Iterator::operator--()
{
    this->mPtr--;
    return *this;
}

// Postfix overloading
template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::Iterator::operator++(int)
{
    DummyVector<T>::Iterator temp = *this;
    this->mPtr++;
    return temp;
}
// Postfix overloading
template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::Iterator::operator--(int)
{
    DummyVector<T>::Iterator temp = *this;
    this->mPtr--;
    return temp;
}

template <typename T>
T& DummyVector<T>::Iterator::operator*()
{
    return *this->mPtr;
}

template <typename T>
bool DummyVector<T>::Iterator::operator==(const Iterator& iter)
{
    return this->mPtr == iter.mPtr;
}

template <typename T>
bool DummyVector<T>::Iterator::operator!=(const Iterator& iter)
{
    return this->mPtr != iter.mPtr;
}

template <typename T>
class DummyVector<T>::ConstIterator
{
public:
    // Constructor
    ConstIterator(T* ptr);
    // Compulsory methods
    // Prefix
    ConstIterator& operator++();
    ConstIterator& operator--();
    // Postfix
    // Returns the value before update
    // Impossible to return by reference
    // Return by value instead
    ConstIterator operator++(int);
    ConstIterator operator--(int);
    // Return by const reference
    // So that the container cannot be modified
    const T& operator*();
    bool operator==(const ConstIterator& iter);
    bool operator!=(const ConstIterator& iter);

private:
    T* mPtr;
};

template <typename T>
DummyVector<T>::ConstIterator::ConstIterator(T* ptr) : mPtr{ptr}
{
}

// Prefix overloading
// If T::X is a dependent typename, then we need to prefix it by typename to
// tell the compiler to parse it in a certain way.
template <typename T>
typename DummyVector<T>::ConstIterator&
DummyVector<T>::ConstIterator::operator++()
{
    this->mPtr++;
    return *this;
}
// Prefix overloading
template <typename T>
typename DummyVector<T>::ConstIterator&
DummyVector<T>::ConstIterator::operator--()
{
    this->mPtr--;
    return *this;
}

// Postfix overloading
template <typename T>
typename DummyVector<T>::ConstIterator
DummyVector<T>::ConstIterator::operator++(int)
{
    DummyVector<T>::ConstIterator temp = *this;
    this->mPtr++;
    return temp;
}
// Postfix overloading
template <typename T>
typename DummyVector<T>::ConstIterator
DummyVector<T>::ConstIterator::operator--(int)
{
    DummyVector<T>::ConstIterator temp = *this;
    this->mPtr--;
    return temp;
}

template <typename T>
const T& DummyVector<T>::ConstIterator::operator*()
{
    return *this->mPtr;
}

template <typename T>
bool DummyVector<T>::ConstIterator::operator==(const ConstIterator& iter)
{
    return this->mPtr == iter.mPtr;
}

template <typename T>
bool DummyVector<T>::ConstIterator::operator!=(const ConstIterator& iter)
{
    return this->mPtr != iter.mPtr;
}

template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::begin()
{
    return DummyVector<T>::Iterator{this->mBuffer};
}

template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::end()
{
    return DummyVector<T>::Iterator{this->mBuffer + this->mSize};
}

template <typename T>
typename DummyVector<T>::ConstIterator DummyVector<T>::cbegin()
{
    return DummyVector<T>::ConstIterator{this->mBuffer};
}

template <typename T>
typename DummyVector<T>::ConstIterator DummyVector<T>::cend()
{
    return DummyVector<T>::ConstIterator{this->mBuffer + this->mSize};
}

// Template function for iterators
template <typename Iter>
Iter maximum(Iter first, Iter last)
{
    Iter max = first;
    for (Iter iter = first; iter != last; iter++)
    {
        if (*max < *iter)
        {
            max = iter;
        }
    }
    return max;
}

int main()
{
    // STL containers
    std::list<int> lst{1, 2, 3, 4, 5};
    std::array<float, 5> arr{1, 2, 3, 4, 5};
    std::vector<float> vec{1, 2, 3, 4, 5};
    // Custom container
    DummyVector<double> dummyVec{1, 2, 3, 4, 5};

    // Ordinary iterator from custom container
    auto lstIter = lst.begin();
    while (lstIter != lst.end())
    {
        *lstIter = 0;
        lstIter++;
    }
    auto lstMaxIter = maximum(lst.begin(), lst.end());
    std::cout << *lstMaxIter << std::endl;

    // Const iterator from STL container
    auto lstConstIter = lst.cbegin();
    while (lstConstIter != lst.cend())
    {
        // Cannot assign
        // *lstConstIter = 5;
        lstConstIter++;
    }
    auto lstMaxConstIter = maximum(lst.cbegin(), lst.cend());
    std::cout << *lstMaxConstIter << std::endl;

    // Ordinary iterator from custom container
    auto dummyVecIter = dummyVec.begin();
    while (dummyVecIter != dummyVec.end())
    {
        *dummyVecIter = 0;
        dummyVecIter++;
    }
    auto dummyVecMaxIter = maximum(dummyVec.begin(), dummyVec.end());
    std::cout << *dummyVecMaxIter << std::endl;

    // Const iterator from custom container
    auto dummyVecConstIter = dummyVec.cbegin();
    while (dummyVecConstIter != dummyVec.cend())
    {
        // Cannot assign
        // *dummyVecConstIter = 5;
        dummyVecConstIter++;
    }
    auto dummyVecMaxConstIter = maximum(dummyVec.cbegin(), dummyVec.cend());
    std::cout << *dummyVecMaxConstIter << std::endl;
}
1
2
3
4
5
6
$ g++ const_iterator_code_duplication.cpp -o const_iterator_code_duplication -std=c++11
$ ./const_iterator_code_duplication 
0
0
0
0

It works. But it has lots of “code duplications” between the Iterator implementation and the ConstIterator implementation.

Implementation Without Code Duplication

With std::enable_if, it is possible to reduce the code duplication in the const iterator implementation by metaprogramming.

const_iterator.cpp
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#include <algorithm>
#include <array>
#include <iostream>
#include <list>
#include <vector>

// Custom data structure with iterators
// For some additional implementations for Vector
// /blog/CPP-Const-Overloading/
template <typename T>
class DummyVector
{
public:
    // Default constructors
    DummyVector();
    // Constructors which take more than zero arguments
    explicit DummyVector(size_t size);
    explicit DummyVector(std::initializer_list<T> lst);

    // Iterator basics
    template <bool Const>
    class Iterator;
    Iterator<false> begin();
    Iterator<false> end();
    Iterator<true> cbegin();
    Iterator<true> cend();

private:
    size_t mSize;
    T* mBuffer;
};

// However, the best practice for template classes and functions is to put the
// definition and the declaration together. Mainly, there are two reasons
// 1. Compiler needs to know all the definition for any templates during compile
// time
// 2. Namescope is trivial to write and confusing
template <typename T>
DummyVector<T>::DummyVector() : mSize{0}, mBuffer{nullptr}
{
}

template <typename T>
DummyVector<T>::DummyVector(size_t size) : mSize{size}, mBuffer{new T[size]}
{
    for (int i = 0; i < mSize; i++)
    {
        mBuffer[i] = 0;
    }
}

template <typename T>
DummyVector<T>::DummyVector(std::initializer_list<T> lst)
    : mSize{lst.size()}, mBuffer{new T[lst.size()]}
{
    std::copy(lst.begin(), lst.end(), this->mBuffer);
}

// Iterator is an abstract notion
template <typename T>
template <bool Const>
class DummyVector<T>::Iterator
{
public:
    // Constructor
    Iterator(T* ptr);
    // Compulsory methods
    // Prefix
    Iterator& operator++();
    Iterator& operator--();
    // Postfix
    // Returns the value before update
    // Impossible to return by reference
    // Return by value instead
    Iterator operator++(int);
    Iterator operator--(int);
    template <bool Q = Const>
    typename std::enable_if<Q, const T&>::type operator*();
    template <bool Q = Const>
    typename std::enable_if<!Q, T&>::type operator*();
    bool operator==(const Iterator& iter);
    bool operator!=(const Iterator& iter);

private:
    T* mPtr;
};

template <typename T>
template <bool Const>
DummyVector<T>::Iterator<Const>::Iterator(T* ptr) : mPtr{ptr}
{
}

// Prefix overloading
// If T::X is a dependent typename, then we need to prefix it by typename to
// tell the compiler to parse it in a certain way.
template <typename T>
template <bool Const>
typename DummyVector<T>::template Iterator<Const>&
DummyVector<T>::Iterator<Const>::operator++()
{
    this->mPtr++;
    return *this;
}
// Prefix overloading
template <typename T>
template <bool Const>
typename DummyVector<T>::template Iterator<Const>&
DummyVector<T>::Iterator<Const>::operator--()
{
    this->mPtr--;
    return *this;
}

// Postfix overloading
template <typename T>
template <bool Const>
typename DummyVector<T>::template Iterator<Const>
DummyVector<T>::Iterator<Const>::operator++(int)
{
    DummyVector<T>::Iterator<Const> temp = *this;
    this->mPtr++;
    return temp;
}
// Postfix overloading
template <typename T>
template <bool Const>
typename DummyVector<T>::template Iterator<Const>
DummyVector<T>::Iterator<Const>::operator--(int)
{
    DummyVector<T>::Iterator<Const> temp = *this;
    this->mPtr--;
    return temp;
}

template <typename T>
template <bool Const>
template <bool Q>
typename std::enable_if<!Q, T&>::type
DummyVector<T>::Iterator<Const>::operator*()
{
    return *this->mPtr;
}

template <typename T>
template <bool Const>
template <bool Q>
typename std::enable_if<Q, const T&>::type
DummyVector<T>::Iterator<Const>::operator*()
{
    return *this->mPtr;
}

template <typename T>
template <bool Const>
bool DummyVector<T>::Iterator<Const>::operator==(const Iterator& iter)
{
    return this->mPtr == iter.mPtr;
}

template <typename T>
template <bool Const>
bool DummyVector<T>::Iterator<Const>::operator!=(const Iterator& iter)
{
    return this->mPtr != iter.mPtr;
}

template <typename T>
typename DummyVector<T>::template Iterator<false> DummyVector<T>::begin()
{
    return DummyVector<T>::Iterator<false>{this->mBuffer};
}

template <typename T>
typename DummyVector<T>::template Iterator<false> DummyVector<T>::end()
{
    return DummyVector<T>::Iterator<false>{this->mBuffer + this->mSize};
}

template <typename T>
typename DummyVector<T>::template Iterator<true> DummyVector<T>::cbegin()
{
    return DummyVector<T>::Iterator<true>{this->mBuffer};
}

template <typename T>
typename DummyVector<T>::template Iterator<true> DummyVector<T>::cend()
{
    return DummyVector<T>::Iterator<true>{this->mBuffer + this->mSize};
}

// Template function for iterators
template <typename Iter>
Iter maximum(Iter first, Iter last)
{
    Iter max = first;
    for (Iter iter = first; iter != last; iter++)
    {
        if (*max < *iter)
        {
            max = iter;
        }
    }
    return max;
}

int main()
{
    // STL containers
    std::list<int> lst{1, 2, 3, 4, 5};
    std::array<float, 5> arr{1, 2, 3, 4, 5};
    std::vector<float> vec{1, 2, 3, 4, 5};
    // Custom container
    DummyVector<double> dummyVec{1, 2, 3, 4, 5};

    // Ordinary iterator from custom container
    auto lstIter = lst.begin();
    while (lstIter != lst.end())
    {
        *lstIter = 0;
        lstIter++;
    }
    auto lstMaxIter = maximum(lst.begin(), lst.end());
    std::cout << *lstMaxIter << std::endl;

    // Const iterator from STL container
    auto lstConstIter = lst.cbegin();
    while (lstConstIter != lst.cend())
    {
        // Cannot assign
        // *lstConstIter = 5;
        lstConstIter++;
    }
    auto lstMaxConstIter = maximum(lst.cbegin(), lst.cend());
    std::cout << *lstMaxConstIter << std::endl;

    // Ordinary iterator from custom container
    auto dummyVecIter = dummyVec.begin();
    while (dummyVecIter != dummyVec.end())
    {
        *dummyVecIter = 0;
        dummyVecIter++;
    }
    auto dummyVecMaxIter = maximum(dummyVec.begin(), dummyVec.end());
    std::cout << *dummyVecMaxIter << std::endl;

    // Const iterator from custom container
    auto dummyVecConstIter = dummyVec.cbegin();
    while (dummyVecConstIter != dummyVec.cend())
    {
        // Cannot assign
        // *dummyVecConstIter = 5;
        dummyVecConstIter++;
    }
    auto dummyVecMaxConstIter = maximum(dummyVec.cbegin(), dummyVec.cend());
    std::cout << *dummyVecMaxConstIter << std::endl;
}
1
2
3
4
5
6
$ g++ const_iterator.cpp -o const_iterator -std=c++11
$ ./const_iterator
0
0
0
0

References

C++ Const Iterator

https://leimao.github.io/blog/CPP-Const-Iterator/

Author

Lei Mao

Posted on

03-18-2022

Updated on

03-18-2022

Licensed under

 

Like this article? Support the author with

Comments

  Follow   Sponsor

Advertisement


Catalogue

×