Almost Everything About STL Iterators in C++

Containers are the most useful feature provided by the STL. Some of these containers are sequential, like <vector> and <array>.

Sequential containers are linearly ordered and indexed, which means you can use indices to traverse through the elements using a syntax like vec[i]. At this point, special “iterators” for these containers seems unnecessary.

But not all containers are sequential. Containers like <map> and <set> are associative in nature. They don’t have linear structure. They can’t be traversed using indexes. This is where iterators play their role.

Iterators provide a generic method for accessing and iterating through containers. They act like pointers for these containers.

Note that some containers like <stack> and <queue> don’t support iterators.

Iterators in Action

Every STL container that supports iterators provides these two things:

  1. Iterator types: These are the container-specific types which we use to declare our iterators. A container can support different types of iterators. For example, STL vector supports iterator, reverse_iterator, const_iterator.
  2. begin(), end(): These methods return an iterator to the beginning and end of the container. We need them to initialize our iterators.

The following code illustrates the use of iterator to traverse a vector.

Note how the v.end() doesn’t point to the last element. Instead it points to the past-the-last element, which is an imaginary element representing the end of container. The iterator v.end()-1 is the one pointing to the last element.

Now we move on to <map>, which is an associative container. Map stores elements in key-value pairs, with unique keys.

We can use [] operator to access or insert pairs in map. mp[key]=val inserts the (key,val) pair in container, and mp[key] gives us val.

You should not think of key as an index. Unlike vector indices, which run from 0 to v.size()-1, we don’t always know what keys are present in the map. So our [] operator is useless for traversal.

This is where iterators play their role, as the following code illustrates.

Reverse Iterators

Reverse iterators allow traversal of the container in reverse order. When using reverse_iterator, we use rbegin() and rend() instead of begin() and end(). Rest all is same.

Reverse iterators make reverse traversal easier. But that doesn’t means you can’t traverse in reverse using normal iterators. The following code shows how to traverse in reverse using normal iterators.

Note how we initialized the iterator to point at the last element. We avoided use of s.end()-1, which is only valid for random-access iterators. The iterators provided by <set> are only bidirectional, which means we can also use decrement (--) operator on iterators, apart from the evergreen increment (++) operator. Later in this post, we will see more on valid operations on different type of iterators.

Reverse iterators are only provided by containers that support random-access or bidirectional iterators. Containers like <forward_list>, <unordered_map> and <unordered_set> only provide forward iterators. They don’t support reverse ones.

Constant Iterators

Constant Iterators are used to limit the accessibility to the container.

All the STL containers that support iterators, also support const_iterator. Constant iterators are just like normal iterators, except it doesn’t allows change in the value it points to. This means the container item being accessed using a const_iterator is ready-only.

container::iterator is an iterator which points to an element in container having type T. Constant iterator is similar to this, except it points to T const.

So a vector<int>::const_iterator behaves as vector<int const>::iterator. There is a reason why I chose to write it as int const, and not const int. This improves understanding when dealing with constant iterators to pointers, which we will see later in this post.

Keep in mind that the constant iterator itself can be changed to point to some other container item. And it can also be used to modify the container by inserting or deleting at the position where it points.

Observe the following code.

Note that the element being accessed using a constant iterator can still be changed through some other iterator, but not through the constant one.

cbegin() and cend()

begin() and end() return normal iterators, which then can be used to initialize a const_iterator by automatic type conversion. But since C++11, we have our own cbegin() and cend() which return proper constant iterators.

They prove ideal in situation where we pass our container to a function, but want to limit the accessibility. Consider a function func which carries some operation on each element in the given range.

func(vec.cbegin(), vec.cend(), operatr());

In such situation we aren’t always sure if operatr modifies our container or not. In case it does, our normal iterators won’t object to the modification. But using cbegin()/cend() ensures that values in vec remains intact.

Constant Iterator Over a Container of Pointers

Now, this thing here is a little tricky.

We will take the example of vector<int *>, which is a container containing pointers to int. In this example, watch the terms “pointer” and “iterator”. The two are different.

As noted earlier, a constant iterator over vector<int *> behaves like a regular iterator over vector<int * const>.

So our constant iterator points to a int * const, and not to const int *. To make sense of these two types, read them in reverse.

int * const is a const pointer(*) to an int. So it is pointer which cannot be changed to point to something else. But we can change value of the data it points to. This pointer is what we get when we dereference our constant iterator.

const int * is a pointer(*) to an int that is const. So it is a pointer to int const, which is same as const int. We can change the pointer to point to something else. But we cannot change value of the data it points to.

This demonstrates that a constant iterator can only prevent change in the value it points to, which is a pointer in above code. We can’t make the pointer point to some other memory location, but we surely can change the value stored in the memory location.

Auto Keyword

It’s super tedious to declare iterators with lengthy type names like std::map<int,int>::reverse_iterator it = m.rbegin();. Now compare this with auto it = m.rbegin(). Much easier!!

Since C++11, we can use auto keyword to specify that the type of variable will be deduced automatically from its initializer. When using auto, you must initialize the variable at the time of declaration.

Since the type is deduced automatically, automatic type conversions don’t take place when using auto. So, if you need a constant iterator, use cbegin()/cend(), instead of begin()/end().

Operations on Iterators

STL iterators can be classified  in three categories on the basis of operations they support:

  1. Forward Iterators
  2. Bidirectional Iterators
  3. Random Access Iterators

1. Forward Iterators

Forward iterators allow traversal only in forward direction, that is from begin() to end(). It doesn’t allow traversal in reverse direction. So, these iterators don’t support rbegin() and rend().

These containers only support forward iterators: <forward_list><unordered_map><unordered_set>.

The operations supported by forward iterators are:

  • Increment: it++, ++it
  • Equality comparisons: it1 == it2, it1 != it2
  • Dereferencing: *it, it->first

2. Bidirectional Iterators

Bidirectional iterators extend the capabilities of forward iterators by allowing traversal in both forward and reverse directions. It adds support for rbegin() and rend().

In addition to all the operations on forward iterators, it also allows decrement of iterator (it--, --it).

STL containers that support bidirectional iterators: <list>, <map>, <set>.

3. Random Access Iterators

Forward and bidirectional iterators only allow increment/decrement by one step. Random access can be used to randomly access iterator to any element in the container.

It supports all the functionality of bidirectional iterators, plus these:

  • Addition of iterator and integer: it + n gives nth iterator from it in forward direction. It can also be written as n + it, or we can use compount assignment like it += n
  • Difference of iterator and integer: it - n gives nth iterator from it in reverse direction. Compound assignment can also be used: it -= n
  • Difference of two bidirectional iterators: it1 - it2 gives an integer representing distance between the container elements they point to.
  • Inequality Comparisons of two bidirectional iterators: it1 > it2, it1 < it2, it1 >= it2, it1 <= it2. These can be used to determine relative order of two iterators (elements).

STL containers which support random access iterators: <array>, <vector>, <deque>.

Common Errors

Here is a list of some common errors I have seen people (myself included) running into when dealing with STL. And a lot of it has to do with iterators.

1. Mixing Iterators of Different Types

Two iterators of different types don’t mix well. At least, not without type conversion. You cannot compare or assign an iterator of one type to other.

vector<int>::iterator is different than vector<int>::reverse_iterator, even if both point to same element.

vector<int>::iterator is not same as vector<char>::iterator. They point to different types.

map<int, char>::iterator and map<int, int>::iterator are not same types either.

However, constant iterators work well with regular iterators because of automatic type conversion.

2. Not All Containers Can be Modified Using Iterators

<set> and <map> are basically binary search trees (BST). A BST stores the values of the container in sorted manner. This order is essential to the functioning of these containers, as it decides the time complexity of various operations performed on the container.

In such a situation, changing the value of an element in-place will break the ordered structure of the container. This will render the container useless. So these containers don’t allow change in their values.

Take note that the elements of map are ordered by their first elements. So we are free to modify the second value in the pair.

3. Invalid Operations

As mentioned earlier in this post, different operators support different types of operations. Just to remind you again:

  • Only random access iterators support addition, difference and inequality comparisons (<, >, <=, >=). So these aren’t supported by forward and bidirectional iterators.
  • Forward iterators don’t support decrement operation.

4. Bound Checking

Iterators as such don’t provide checked access to container elements. This means it is possible for an iterator to exceed the end of the container, without compiler throwing an exception. This can result in segmentation fault and undefined behaviors.

Fortunately, random access containers provide the bound-checked function .at(). It can be used for both access and modification much like [] operator. So, is same as vec[i], except it throws an out_of_range exception when i is greater than or equal to v.size().

5. Iterator Invalidation

When we change a container’s structure by some operations, the container elements are moved to a new location. But after this change, our iterator still points to an old location and hence gives us junk data. This is called iterators invalidation.

Insertion and deletion of elements are the most common cause of this. See the code below.

Above code gives no compiler errors or even warnings. But might lead to undefined behavior.

Another such example involves a function, which returns an iterator pointing to a container element local to the function. So, the caller object gets an iterators pointing to a non-existent object.

Unfortunately, C++ doesn’t provides us with any runtime check which throws an exception on iterator invalidation. The best we can do is to properly look into what objects we are using and try to avoid such usage of iterators.

So that was all I had to say in this post. Leave a comment if you have any relevant questions.

One thought to “Almost Everything About STL Iterators in C++”

  1. Keep it up man. Good Job. Your graph theory was also very good. You should consider writing more such helpful posts.

Leave a Reply

Your email address will not be published. Required fields are marked *