C++ Iterator

Introduction

C++ Iterator is an abstract notion which identifies an element of a sequence. A sequence could be anything that are connected and sequential, but not necessarily consecutive on the memory. C++ Iterator could be a raw pointer, or any data structure which satisfies the basics of a C++ Iterator. It has been widely used in C++ STL standard library, especially for the std containers and functions.

In this blog post, I would like to discuss about how to implement C++ Iterator using nested class inside a certain sequence container class for generic programming.

Examples

In this example, we would like to apply different sequence data structures, including std::list, std::array, std::vector, and a custom dummy vector class DummyVector, to the custom template function maximum and the std function std::max_element, which take in two Iterator instances and return an Iterator instance, to find out the maximum value in the sequence. Since std containers have already implemented the Iterators for us, we would just use DummyVector as an example for how to implement class-specific nested Iterator class while making it generic by satisfying the Iterator abstract notions.

According to the C++ standard, an iterator must provide the overloading for *, (prefix) ++, ==, and !=. For completeness, I also implemented (postfix) ++, (prefix) --, and (postfix) --, since some custom template function, such as our maximum function, might use these operators as well without following the exact C++ standard.

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
#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;
Iterator begin();
Iterator end();

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

auto lstMaxIter = maximum(lst.begin(), lst.end());
std::cout << *lstMaxIter << std::endl;
auto arrMaxIter = maximum(arr.begin(), arr.end());
std::cout << *arrMaxIter << std::endl;
auto vecMaxIter = maximum(vec.begin(), vec.end());
std::cout << *vecMaxIter << std::endl;
auto dummyVecMaxIter = maximum(dummyVec.begin(), dummyVec.end());
std::cout << *dummyVecMaxIter << std::endl;

lstMaxIter = std::max_element(lst.begin(), lst.end());
std::cout << *lstMaxIter << std::endl;
arrMaxIter = std::max_element(arr.begin(), arr.end());
std::cout << *arrMaxIter << std::endl;
vecMaxIter = std::max_element(vec.begin(), vec.end());
std::cout << *vecMaxIter << std::endl;
dummyVecMaxIter = std::max_element(dummyVec.begin(), dummyVec.end());
std::cout << *dummyVecMaxIter << std::endl;
}

To compile the program, please run the following command in the terminal.

1
$ g++ iterator.cpp -o iterator -std=c++11

The expected output of the program would be as follows.

1
2
3
4
5
6
7
8
9
$ ./iterator 
5
5
5
5
5
5
5
5

Conclusions

If we have a custom sequence container class, and we want to take the advantage of the existing C++ STL algorithm std template functions, we could just implement the Iterator for the custom sequence container class. This container class would then be compatible with all the C++ STL algorithm std template functions. This is an extremely good example of the C++ generic programming concept.

Author

Lei Mao

Posted on

03-15-2020

Updated on

11-17-2021

Licensed under


Comments