C++

C++ Vector Iterators

The main iterators in C++ are Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator. Reverse Iterator is not really an iterator; it is an iterator adaptor. There are some variants to iterators, like a constant iterator.

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

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:

#include <iterator>

or

#include <vector>

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:

template<class C> constexpr auto data(C& c) -> decltype(c.data());

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:

vector <char> vtr;

Here the object, c, is empty.

Template Function:

template<class E> constexpr const E* data(initializer_list<E> il) noexcept;

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> vtr{'A', 'B', 'C', 'D', 'E'};
vector<char>::const_iterator it = vtr.begin();

The template function is more applicable to the beginning () statement (the second statement).

Access

Template Function:

template<class C> constexpr auto size(const C& c) -> decltype(c.size());

This returns the size of the container. Vector example:

vector <char> vtr{'A', 'B', 'C', 'D', 'E'};
int N = vtr.size();
cout << N << endl;

The output is 5.

Template Function:

template<class E> [[nodiscard]] constexpr bool empty(initializer_list<E> il) noexcept;

Returns true if the list is empty or false otherwise. Vector example:

vector <char> vtr{'A', 'B', 'C', 'D', 'E'};
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:

template<class C> constexpr auto begin(C& c) -> decltype(c.begin());

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> vtr{'A', 'B', 'C', 'D', 'E'};
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:

template<class C> constexpr auto end(const C& c) -> decltype(c.end());

Returns a constant iterator pointing to the last element of the list. Vector code:

vector <char> vtr{'A', 'B', 'C', 'D', 'E'};
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:

template<class E> constexpr reverse_iterator<const E*> rbegin(initializer_list<E> il);

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> vtr{'A', 'B', 'C', 'D', 'E'};
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:

template<class E> constexpr reverse_iterator<const E*> rend(initializer_list<E> il);

Points just before the first element of the list. Vector example:

vector <char> vtr{'A', 'B', 'C', 'D', 'E'};
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:

explicit back_insert_iterator(Container& x);
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:

explicit front_insert_iterator(Container& x);
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(Container& x, typename Container::iterator i);
insert_iterator& operator=(typename Container::value_type&& value);

Vector example:

vector <char> vtr{'A', 'B', 'C', 'D', 'E'};
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:

A, B, c, C, D, E,

The vector insert expression is:

vtr.insert(it, 'c');

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 <iostream>
#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.

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.