An iterator is an elaborated pointer. Like a pointer, it points to objects of the same type in memory at different times. All iterators are dereferenceable, except for the output iterator that is dereferenceable only for a set of types. Dereferenceable means the value pointed to by the pointer or iterator can be obtained using the indirection operator, *. An integer can be added to some iterators in the same way, and for the same purpose, the integer would be added to a pointer.
The questions for this article are: What are these iterators? Which of these iterators are used with the C++ vector? How are these iterators used with the C++ vector? This article answers all these questions in a simplified way. At the end of this article, when all these questions would have been answered, C++ vector iterators will be intuitive and natural (for the reader).
Article Content
- Summary of C++ Iterators
- Vector Construction and Access
- Range Access
- Insert Iterators
- Move Iterator
- Conclusion
Summary of C++ Iterators
Input Iterator
The idea of input iterator is for a program to receive input value. Unlike the output iterator, the input iterator is always dereferenceable. For two input iterators, a and b, “a == b” does not imply “++a == ++b”.
Output Iterator
The idea of output iterator is for a program to release output value. Unlike the input iterator, the output iterator is not always dereferenceable. It is dereferenceable only for a set of types.
Forward Iterator
The forward iterator can scan the vector from the beginning to the end, one by one (incrementing). It has all the requirements of the input iterator, plus additional requirements. It can substitute an input iterator. For two forward iterators, a and b, “a == b” implies “++a == ++b”.
Bidirectional Iterator
The Bidirectional Iterator can scan the vector from the beginning to the end, one by one. From the end to the beginning, one by one (decrementing). It has all the requirements of the forward iterator, plus additional requirements. It can substitute a forward iterator. For two bidirectional iterators, a and b,
“a == b” implies “++a == ++b”
and
“–a == –b” implies “a == b”.
Random Access Iterator
The Random Access iterator has all the requirements of the bidirectional iterator, plus additional requirements. It can substitute a bidirectional iterator. The random access iterator comes with the advantage that if it is currently pointing to the first element and the fourth element is required, it would skip the second and third elements and point to the fourth element. The reverse skipping downward is true.
Reverse Iterator
Note that C++ does not have a normal reverse iterator as it has a forward iterator. So, there is an adaptor called a Reverse Iterator. There is more good news: the reverse iterator meets all the requirements of a Bidirectional Iterator.
Constant Iterator
If an iterator is said to be a const iterator, the element it points to cannot be modified.
Vector Construction and Access
Containers in C++ are: class array, deque, forward_list, list, vector, map, set, unordered_map, and unordered_set. The vector is a container. Certain function templates in the C++ standard library operate with iterators directly or indirectly. C++ containers, as well as the vector, use these functions. These functions can be made available to the C++ program with either of the following inclusion directives:
or
The inclusion of any of the other containers will also make available these function templates. A function template is for a function that can operate with different data types. The vector uses iterators through these function templates. Some of the function templates and their relationship to the vector are as follows:
Construction
Template Function:
auto means the return type is determined at evaluation of the function. c is the object of class C.
An example of a vector object constructed with this implicitly is:
Here the object, c, is empty.
Template Function:
Here, E* is an iterator that points to the first element of the list or container. Its use with the vector implicitly, would be with:
vector<char>::const_iterator it = vtr.begin();
The template function is more applicable to the beginning () statement (the second statement).
Access
Template Function:
This returns the size of the container. Vector example:
int N = vtr.size();
cout << N << endl;
The output is 5.
Template Function:
Returns true if the list is empty or false otherwise. Vector example:
bool bl = vtr.empty();
cout << bl << endl;
The output is 0 for false.
Range Access
There are other template functions, which use iterators that the vector uses for its range problems. A range is a consecutive set of container elements.
Template Function:
This returns an iterator pointing to the first element in the list. auto here means, the return value is determined at evaluation. Example for vector:
vector<char>::iterator it = vtr.begin();
cout << *it << '\n';
The output is A. The iterator returned here is a random access iterator. A constant random access iterator could have been returned – see later.
Function Template:
Returns a constant iterator pointing to the last element of the list. Vector code:
vector<char>::const_iterator it = vtr.end();
--it;
cout << *it << ' ';
--it;
cout << *it << endl;
The output is “E D”. A constant iterator can be incremented or decremented, but the value it points to cannot be changed. A normal random access iterator could have been returned – see later.
Function Template:
Returns the last value in the list. rbegin() points to the last element of the list and not beyond the last element of the list, like end() does. Vector example:
vector<char>::reverse_iterator it = vtr.rbegin();
cout << *it << ' ';
++it;
cout << *it << endl;
The output is: E D. With the reverse iterator, ++ has the opposite effect for the bidirectional iterator.
Function Template:
Points just before the first element of the list. Vector example:
vector<char>::reverse_iterator it = vtr.rend();
--it;
cout << *it << ' ';
--it;
cout << *it << endl;
Output is A B. With the reverse iterator, — has the opposite effect for ++ of the bidirectional iterator.
There are other template functions under this heading – see later.
Insert Iterators
reverse_iterator is an iterator adaptor, not really an iterator. The insert iterator is also an iterator adaptor. It satisfies all the requirements of the output iterator, plus its own requirements. It exists in three forms in C++: the back_inserter, the front_inserter, and the inserter. Each of these has its own constructor.
back_inserter:
Inserts at the back!
Important prototypes:
back_insert_iterator& operator=(typename Container::value_type&& value);
Vector example:
The vector does not have any insert member function that inserts at the back. However, the push_back(t) member function can be seen like that.
front_inserter
Inserts at the front!
Important prototypes:
front_insert_iterator& operator=(typename Container::value_type&& value);
Vector example:
The vector does not have any insert member function that inserts at the front. The vector does not also have the push_front(t) member function.
The good news is that the vector has insert member functions that can insert anywhere, in the beginning, within, or the end of the vector.
inserter
This iterator would insert at the beginning, within, or the end of the vector.
Important prototypes:
insert_iterator& operator=(typename Container::value_type&& value);
Vector example:
vector<char>::iterator it = vtr.begin();
it = it + 2;
vtr.insert(it, 'c');
for (int i=0; i<vtr.size(); i++)
cout << vtr[i] << ", ";
cout <<endl;
The output is:
The vector insert expression is:
It inserts the element just before the pointer (it) it is pointing to.
Move Iterator
The move_iterator is also an iterator adaptor. The following program is similar to the example that is in the C++ specification:
#include <list>
#include <vector>
using namespace std;
int main()
{
list<char> chs{'A', 'B', 'C', 'D', 'E'};
vector<char> vtr(make_move_iterator(chs.begin()), make_move_iterator(chs.end()));
cout << "Original list Content:" << endl;
for (auto it = chs.begin(); it != chs.end(); it++)
cout << *it << ", ";
cout << endl << endl;
cout << "Vector Content:" << endl;
for (int i=0; i<vtr.size(); i++)
cout << vtr[i] << ", ";
cout << endl;
return 0;
}
The output is:
Original list Content:
A, B, C, D, E,
Vector Content:
A, B, C, D, E,
This iterator converts a source value to an rvalue before placing it at the destination.
Conclusion
The main iterators in C++ are Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, and Random-Access Iterator. The C++ standard library has some function templates that use these iterators. The vector uses these iterators through the function templates. The vector has some different names for some of these iterators. There are also iterator adaptors, which are: reverse_iterator, iterator adaptor, and move_iterator. Some variants of iterators also exist. It suffices to include in a program to have all these features. After understanding the role of these iterators, adaptors, and the function templates that use them, using iterators with vectors becomes intuitive.
