Iterators

This lesson provides an in-depth look at iterators in C++, covering different types like forward, bidirectional, and random access iterators, and their practical uses.
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, Unlimited Access
Abstract art representing computer programming
Ryan McCombe
Ryan McCombe
Updated

Typically, we don’t want to write algorithms that only work with one specific type of container, such as a std::vector. We’d prefer to write algorithms that work across a wide range of containers.

For example, the goal might be to write an algorithm that works across different array implementations such as std::vector, std::array, or even array views such as std::span. But perhaps it could also work with containers that use a different data structure entirely, such as linked list implementations.

Rather than having to write various implementations of our algorithm to support different access patterns, we can use a technique called iterators.

Iterators are a type of object like any other - these types are designed to support traversal through containers in a standardized way.

Instead of writing algorithms that work with containers, we can write algorithms that work with iterators. Then, any container type can be compatible with our algorithms - the container class just needs to provide a couple of member functions that can return iterator objects.

Decoupling

This is a technique known as decoupling. Were we to write an algorithm that works only with a std::vector by, for example, requiring a std::vector as an argument, our type and our algorithm would be tightly coupled.

We generally want to avoid unnecessary coupling in this way, as it limits interoperability. Instead, if we can write an algorithm that works with iterators, it can work with any type that implements iterators.

The reverse is also true - if we create a new type, and add appropriate member functions that can create iterators, our type is instantly compatible with any iterator-based algorithms that already exist. This gives our new type a huge range of functionality, almost for free.

The begin() iterator

The most common way we’ll generate an iterator for working with a collection is through a method on that container class. By convention, this method is called begin() and returns an iterator representing the start of the collection:

#include <array>

int main() {
  std::array Nums{1, 2, 3};
  auto Start{Nums.begin()};
}

Dereferencing Iterators

Naturally, we need the ability to access the underlying object that our iterator is pointing at. Iterators typically overload the unary *, which lets us accomplish this using the same syntax we use when working with pointers:

#include <array>
#include <iostream>

int main() {
  std::array Nums{1, 2, 3};
  auto Start{Nums.begin()};

  std::cout << "First Object: " << *Start;
}
First Object: 1

It’s common for -> to be overloaded too, allowing us an easy way to access class members through an iterator:

#include <array>
#include <iostream>

class Character {
 public:
  std::string GetName() { return "Anna"; }
};

int main() {
  std::array<Character, 3> Party;
  auto Start{Party.begin()};

  std::cout << "First: " << Start->GetName();  
}
First: Anna

Iterator Categories

Just as containers can support different underlying access patterns, so do iterators. However, while we can have many different container types, iterators are grouped into much fewer categories. Typically, the iterators we use most often fall into three categories:

1. Forward Iterator

Forward iterators can advance through our collection one step at a time. This is done by overloading the ++ operators - both postfix and prefix - with similar behavior as when we use those operators on a type like int.

An example of a container whose iterators should support this pattern is the singly linked list. Each node in a singly linked list contains a pointer to the next node in the sequence, meaning we can only navigate in one direction.

The standard library’s implementation of a singly linked list is std::forward_list, which we cover in detail later in the chapter:

#include <forward_list>
#include <iostream>

int main() {
  std::forward_list Nums{1, 2, 3};
  auto Start{Nums.begin()};
  auto Second{++Nums.begin()};

  std::cout << "First: " << *Start;
  std::cout << "\nSecond: " << *(Second);
  std::cout << "\nThird: " << *(++Second);  
}
First: 1
Second: 2
Third: 3

2. Bidirectional Iterator

Bidirectional iterators allow us to advance through our collection one step at a time, in either direction. This is done by overloading the ++ operators for forward iteration, and the -- operators for reverse iteration.

An example of a container whose iterators should support this pattern is the doubly linked list. Each node in a doubly linked list includes pointers to both the next and previous node, allowing traversal in either direction.

The standard library’s implementation of a doubly linked list is std::list, which we cover in detail later in the chapter:

#include <list>
#include <iostream>

int main() {
  std::list Nums{1, 2, 3};
  auto Iterator{Nums.begin()};

  std::cout << "First: " << *Iterator;
  std::cout << "\nSecond: " << *(++Iterator);
  std::cout << "\nFirst: " << *(--Iterator);  
}
First: 1
Second: 2
First: 1

3. Random Access Iterator

Random access iterators allow us to advance forward or back in any direction, and by any distance. This is done by overloading operators such as += and -. For example:

  • We can generate a new iterator 5 steps ahead of MyIterator using an expression like MyIterator + 5
  • We can reverse an iterator by 10 steps in place using an expression like MyIterator -= 10.

An example of a container whose iterators should support this pattern are arrays such as std::vector and std::array:

#include <vector>
#include <iostream>

int main() {
  std::vector Nums{1, 2, 3, 4, 5};

  auto Iterator{Nums.begin()};
  auto Fifth{Iterator + 4};

  std::cout << "First: " << *Iterator;
  std::cout << "\nFifth: " << *(Fifth);
  std::cout << "\nThird: " << *(Fifth -= 2);  
}
First: 1
Fifth: 5
Third: 3

Iterator Hierarchy

Similar to inheritance, we can imagine iterator categories existing in a form of hierarchy. The more advanced iterators have all the capabilities of the more basic iterators - they simply provide additional capabilities.

In other words, a bidirectional iterator implements all the operators required of the more basic forward iterator, so a bidirectional iterator is a forward iterator.

A random access iterator has all the capabilities of a bidirectional iterator, so a random access iterator is a bidirectional iterator. And, it is therefore also a forward iterator.

Container Traversal

The std::next() and std::prev() functions give us a generic way to navigate through our collections using iterators.

Forward Traversal using std::next()

To move forward through our container, we pass two arguments to std::next():

  1. An iterator representing the current position
  2. An offset - an integer representing how many steps we want to advance from the current position

The std::next() function will then return a new iterator, pointing at the requested location:

#include <iostream>
#include <vector>

int main() {
  std::vector Nums{1, 2, 3, 4, 5};

  std::cout << "Third: "
    << *std::next(Nums.begin(), 2);
}
Third: 3

Behind the scenes, std::next() adapts its approach depending on the capability of the iterator we provide.

For example, if we call std::next() with a random access iterator and an offset of 10, it can generate our new iterator in constant time - O(1)O(1) - using an expression like MyIterator + 10.

A simpler forward iterator doesn’t support this, but std::next() can still advance it by, for example, calling the ++ operator 10 times. This is a slower linear process - O(n)O(n) where nn is the offset - but it still gets us the desired result.

Below, we write a LogThirdElement template function that works with any container type that supports forward iterators:

#include <iostream>
#include <vector>
#include <forward_list>

template <typename T>
void LogThirdElement(T Container) {
  std::cout << "\nThird Element: " <<
    *std::next(Container.begin(), 2);
}

int main() {
  std::vector NumsArray{1, 2, 3, 4, 5};
  std::vector NumsList{1, 2, 3, 4, 5};

  LogThirdElement(NumsArray);
  LogThirdElement(NumsList);
}
Third Element: 3
Third Element: 3

Backwards Traversal using std::prev()

When using a bidirectional or random access operator, we traverse backward through our container using std::prev():

#include <iostream>
#include <vector>

int main() {
  std::vector Nums{1, 2, 3, 4, 5};

  auto First{Nums.begin()};
  auto Third{std::next(First, 2)};
  auto Second{std::prev(Third, 1)};

  std::cout << "First: " << *First;
  std::cout << "\nSecond: " << *Second;
  std::cout << "\nThird: " << *Third;
}
First: 1
Second: 2
Third: 3

If we attempt to use std::prev() with an iterator that only supports forward iteration, we should get a compilation error:

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list Nums{1, 2, 3, 4, 5};

  auto First{Nums.begin()};
  auto Third{std::next(First, 2)};
  auto Second{std::prev(Third, 1)};  
}
error: static_assert failed: 'prev requires bidirectional iterator'

Bidirectional Travel Using Negative Offsets

We can also traverse backward using std::next() - we just need to provide a negative offset:

#include <iostream>
#include <vector>

int main() {
  std::vector Nums{1, 2, 3, 4, 5};

  auto First{Nums.begin()};
  auto Third{std::next(First, 2)};
  auto Second{std::next(Third, -1)};
}

This is primarily used when our offset is dynamic - that is, we don’t know which direction we’re moving, so we don’t know if we should use std::prev() or std::next().

If we do know we’re traversing backward at compile time, we should use std::prev() rather than std::next() with a negative offset. The std::prev() function makes our intent clearer and has additional compile-time checks to ensure our iterator is bidirectional.

If we use a negative offset with std::next(), and our iterator doesn’t support backward traversal, we have undefined behavior.

When compiling with debug flags, we may get a run-time assertion that alerts us if we trigger this scenario:

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list Nums{1, 2, 3, 4, 5};

  auto First{Nums.begin()};
  auto Third{std::next(First, 2)};
  auto Second{std::next(Third, -1)};
}
error: negative advance of non-bidirectional iterator
example.exe (process 50648) exited with code 3.

The end() Iterator

Container classes that implement iterators also provide the end() method, which represents the end of our container.

When advancing an iterator, we can compare it to what is returned by end() using the == or != operator.

If the == operator returns false (or != returns true) we know we haven’t yet reached the end of our collection, so we can continue advancing:

#include <array>
#include <iostream>

int main() {
  std::array Nums{1, 2, 3};

  auto Start{Nums.begin()};
  auto End{Nums.end()};

  for (auto It{Start}; It != End; ++It) {
    std::cout << *It << ", ";
  }
}
1, 2, 3,

The end() Iterator does not point at the last object

An important thing to note is that the end() iterator does not point at the last object in the collection. Rather, we can imagine it pointing at the end of the collection - a location after the last object. For this reason, the iterator is sometimes referred to as a past-the-end iterator.

Expecting it to point at an object, and attempting to dereference it, is a common mistake when people first start working with iterators. When we compile in debug mode, run-time checks will often alert us if we try to do this:

#include <array>
#include <iostream>

int main() {
  std::array Nums{1, 2, 3};
  *Nums.end(); 
}
example.exe (process 60252) exited with code 3.
error: cannot dereference out of range array iterator

If the iterator we’re working with is at least bidirectional, we can access the last element by moving one step back from the end() iterator:

#include <array>
#include <iostream>

int main() {
  std::array Nums{1, 2, 3};
  std::cout << "Last: "
    << *std::next(Nums.end(), -1);
}
Last: 3

Range-Based for Loops

The previous example using a for loop can be written more simply. If our container contains begin() and end() methods that work in the way we described above, they are considered a range.

This allows us to use various range-based techniques on our containers, which we’ll cover in more detail later.

We cover this in more detail later in the course, including how we can support this syntax using our custom types.

For now, we can note that all of the sequential containers in the standard library, such as std::vector and std::forward_list, are valid ranges, so are compatible with this syntax:

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list MyList { 1, 2, 3, 4, 5 };

  for (int x : MyList) {
    std::cout << x << ", ";
  }
}
1, 2, 3, 4, 5,

By default, our objects are copied into the body of our loop by value. This has the same implications as passing function arguments by value, which we covered earlier.

When our object is expensive to copy, and we have no need to copy it, we prefer to pass them by references or const references instead:

#include <array>
#include <iostream>

class Character {
 public:
  void SetName(){};
  void GetName() const {};
};

int main() {
  std::array<Character, 5> Collection;

  // Pass by reference
  for (Character& C : Collection) {
    C.SetName();
  }

  // Pass by const reference
  for (const Character& C : Collection) {
    // Cannot call non-const function
    C.SetName();
  }
}

Using std::distance()

A common requirement we’ll have when working with iterators is to understand how far apart they are. Below, we determine how far ahead our container's end() iterator is, relative to its begin().

For storing the difference between memory addresses, we typically use the ptrdiff_t type, which behaves like an integer:

#include <vector>
#include <iostream>

int main() {
  std::vector Nums{1, 2, 3, 4, 5};
  ptrdiff_t Distance{Nums.end() - Nums.begin()};
  std::cout << "Distance: " << Distance;
}
Distance: 5

With std::vector, this result is equivalent to what is returned by the size() method. But, size() is not available on all containers, and this technique can be used to determine the distance between any two iterators, not just the begin() and the end():

#include <iostream>
#include <vector>

int main() {
  std::vector Nums{1, 2, 3};
  auto Iterator{Nums.begin()};
  while (Iterator != Nums.end()) {
    std::cout << (Nums.end() - Iterator)
      << " object(s) remaining\n";
    ++Iterator;
  }
}
3 object(s) remaining
2 object(s) remaining
1 object(s) remaining

The ability to use arithmetic operators such as - on our iterators is only available when working with random access iterators. We can’t do this with forward iterators, for example.

However, it’s still possible to determine the distance between two forward iterators - we just need to use a different approach. For example, we could call the ++ operator in a loop, taking one step at a time until we reach our target. Then, we return the number of steps that were required.

Rather than needing to implement these algorithms ourselves, the standard library’s std::distance() function provides a generic solution that works across iterator types:

#include <vector>
#include <iostream>

int main() {
  std::vector Nums{1, 2, 3, 4, 5};

  ptrdiff_t Distance{
    std::distance(Nums.begin(), Nums.end())};

  std::cout << "Distance: " << Distance;
}
Distance: 5

Similar to std::next(), the std::distance() function chooses the most efficient method, based on the type of iterator we provide. Given a random access iterator, it can use the arithmetic approach to determine the answer in constant time - O(1)O(1).

With a forward iterator, it needs to follow the path from the first iterator to the second, generating the answer in linear time - O(n)O(n), where nn is the distance between the two iterators.

Standard Library Algorithms

When our type supports iterators, we have a huge range of iterator-based algorithms that we can use with them. For example, the standard library includes at least a hundred such algorithms, and we cover the most useful ones later in the course.

As an example, the std::for_each() algorithm, within the <algorithm> header is one of the simplest. We provide it with three arguments:

  1. A starting point, in the form of an iterator
  2. An ending point, in the form of an iterator
  3. A function to call

The std::for_each algorithm will then traverse between those two iterators, calling the function with every object it finds along the way:

#include <iostream>
#include <vector>
#include <algorithm>

void Log(int x) {
  std::cout << "Number: " << x << '\n';
}

int main() {
  std::vector Nums{1, 2, 3};
  std::for_each(Nums.begin(), Nums.end(), Log);
}
Number: 1
Number: 2
Number: 3

Constant Iterators

Just like a pointer or function, anyone holding an iterator to an object can modify the object through that iterator.

#include <iostream>
#include <vector>
#include <algorithm>

void Increment(int& x) { ++x; }

void Log(int x) {
  std::cout << "Number: " << x << '\n';
}

int main() {
  std::vector Nums{1, 2, 3};
  std::for_each(
    Nums.begin(), Nums.end(), Increment);

  std::for_each(Nums.begin(), Nums.end(), Log);
}
Number: 2
Number: 3
Number: 4

We can prevent this using const iterators if needed. Constant forms of iterators are generally available by pretending c to functions that create iterators.

For example, we would use cbegin() and cend() to generate const iterators.

Below, the compiler will throw an error when we attempt to modify the underlying object through a const reference.

Specifically, it prevents our objects from being passed to our Increment function by reference, as that function hasn’t been marked the reference as as const:

#include <vector>
#include <algorithm>

void Increment(int& x) { ++x; }

int main() {
  std::vector Nums{1, 2, 3};
  std::for_each(
    Nums.cbegin(), Nums.cend(), Increment);
}
error C2664: 'void (int &)': cannot convert argument 1 from 'const int' to 'int &'

Reverse Iterators

Many containers also support the idea of reverse iterators, typically available using functions called rbegin() and rend(). As we might expect, these traverse our collection in the opposite order:

#include <iostream>
#include <vector>
#include <algorithm>

void Log(int x) {
  std::cout << "Number: " << x << '\n';
}

int main() {
  std::vector Nums{1, 2, 3};
  std::for_each(
    Nums.rbegin(), Nums.rend(), Log);
}
Number: 3
Number: 2
Number: 1

Reverse Constant Iterators

Containers that support reverse and constant iterators also tend to support a combination of both. We can iterate through our collection in reverse order using constant iterators generated from functions usually called crbegin() and crend()

Iterator Invalidation

We can save iterators to variables like any other type of object, however, this has implications when our underlying container is changed.

For example, if we save a copy of a container’s begin() operator, and then perform some action that prompts our container to move, our saved object is no longer valid. This is referred to as iterator invalidation:

#include <vector>

int main() {
  std::vector Vec{1, 2, 3};
  auto Iterator{Vec.begin()};
  Vec.resize(100);
  *Iterator;
}

This program will result in undefined behavior. With compiler debug flags enabled, additional checks may be in effect that can detect and alerts us if our program attempts to use an invalidated iterator:

can't dereference invalidated vector iterator
example.exe (process 42572) exited with code 3.

As a general rule, it’s often better to regenerate iterators when they’re needed, as it’s rarely an expensive operation. If we do need to save iterators, we need to be mindful when using container actions that would invalidate them.

With experience, we will often be able to intuit which actions invalidate iterators, but we can also check the documentation to be sure.

Standard library references, such as cppreference.com's std::vector reference, include a section on iterator invalidation, documenting what methods can invalidate that container’s iterators.

Iterator Types

Iterators are objects like any other - they have a specific type. However, it’s somewhat uncommon that we explicitly use these types in our code. When we need to refer to the specific iterator type a container uses, the class generally makes it available using the iterator member type.

Below, define variables for storing the iterator and const iterator type used by a std::vector of int objects:

#include <vector>

int main() {
  std::vector<int>::iterator A;
  std::vector<int>::const_iterator B;
}

Often, the container we want to iterate will already be defined, so we use the decltype() specifier to similar effect:

#include <vector>

int main() {
  std::vector Nums{1, 2, 3};

  decltype(Nums)::iterator A;
  decltype(Nums)::const_iterator B;
}

Remember, we can implement using statements to give types like these friendlier aliases:

#include <vector>

int main() {
  std::vector Nums{1, 2, 3};
  using NumsIterator = decltype(Nums)::iterator;

  NumsIterator A;
}

Iterators with C++20 Concepts

Most commonly, we’ll be using iterators within templates, so we don’t specify any type at all. Instead, we’ll typically be specifying the requirements of the time, in terms of type traits or, more recently, C++20 concepts.

The iterator concepts we commonly use are within the <iterator> header. Most notably:

  • Forward iterators implement the concept std::forward_iterator
  • Bidirectional iterators implement the concept std::bidirectional_iterator
  • Random access iterators implement the concept std::random_access_iterator

Below, we show how to determine which category of iterator we’re dealing with using these concepts:

#include <iterator>
#include <forward_list>
#include <iostream>

int main() {
  std::forward_list NumbersList{1, 2, 3};

  if constexpr (std::forward_iterator<
    decltype(NumbersList)::iterator>
  ) {
    std::cout << "It's a forward iterator";
  }

  if constexpr (!std::random_access_iterator<
    decltype(NumbersList)::iterator>
  ) {
    std::cout << " but not random access";
  }
}
It's a forward iterator but not random access

In the following example, we create a template function that requires the container we provide to use a random access iterator.

In this case, we need to include the typename keyword, to clarify that the iterator member of the template type T is expected to be a type name, rather than any other form of static member:

#include <forward_list>
#include <iostream>

template <typename T>
void SomeAlgorithm(T& Container) {
  static_assert(std::random_access_iterator<
    typename T::iterator>,
    "Only supports random access containers"
  );

  // ...
}

int main() {
  std::forward_list NumbersList{1, 2, 3};
  SomeAlgorithm(NumbersList);
}
main.cpp(6,17): error C2338: static_assert failed: 'Only supports random access containers'

We can equivalently implement the previous constraint using the C++20 requires syntax:

#include <forward_list>
#include <iostream>

template <typename T>
requires std::random_access_iterator<
    typename T::iterator>
void SomeAlgorithm(T& Container) {
  // ...
}

int main() {
  std::forward_list NumbersList{1, 2, 3};
  SomeAlgorithm(NumbersList);
}
error: the associated constraints are not satisfied
the concept std::random_access_iterator evaluated to false

Creating Custom Concepts

If we’re going to commonly use patterns like the previous example, it can be worth creating our own named concept, to keep our code more descriptive.

Below, we implement the above requirement as a standalone concept called RandomAccess. Specifically, RandomAccess requires that a type define an iterator member type, and for that type to be a random access iterator:

#include <iterator>

template <typename T>
concept RandomAccess = requires(T) {
  requires std::random_access_iterator<
    typename T::iterator>;
};

Below, we create a concept that requires the iterator member type to be a forward iterator, but not the more capable random access iterator.

Remember, a random access iterator implements all the requirements of more basic iterators, including a forward iterator. Therefore, if we want to ensure our container’s iterator is at least a forward iterator, but not a random access iterator, we need to check both:

#include <iterator>

template <typename T>
concept NotRandomAccess = requires(T) {
  requires std::forward_iterator<
    typename T::iterator>;
  requires(!std::random_access_iterator<
    typename T::iterator>);
};

Using these concepts, we can now provide two variations of an algorithm. If the container passed to the algorithm supports random access, we have an implementation that takes advantage of those capabilities to complete faster.

If the container doesn’t support random access, perhaps we can still complete the task using just the forward iterator capabilities, even if it might run slightly slower:

#include <iterator>
#include <iostream>
#include <vector>
#include <forward_list>

concept RandomAccess = requires(T) {}
concept NotRandomAccess = requires(T) {} void SomeAlgo(RandomAccess auto Container) { std::cout << "Random Access Variation\n"; } void SomeAlgo(NotRandomAccess auto Container) { std::cout << "Not Random Access Variation\n"; } int main() { std::vector NumbersArray{1, 2, 3}; SomeAlgo(NumbersArray); std::forward_list NumbersList{1, 2, 3}; SomeAlgo(NumbersList); }
Random Access Variation
Not Random Access Variation

Summary

In this lesson, we explored the diverse world of iterators, understanding how they enable flexible and efficient manipulation of different container types.

We delved into various iterator categories, their unique characteristics, and how they integrate algorithms, allowing us to write more versatile code.

Key Takeaways:

  • Iterators are objects that allow standardized traversal and manipulation of containers, such as std::vector, std::list, and std::array.
  • We learned about different iterator categories, including forward, bidirectional, and random access iterators, each offering varying levels of functionality.
  • The lesson covered essential iterator operations like dereferencing using the * operator, traversal using std::next() and std::prev(), and comparisons using std::distance()
  • We discussed the importance of the begin() and end() methods, emphasizing that end() does not point to the last element but to a position past the last element.
  • We also explored how standard library algorithms, such as std::for_each(), are designed to work with iterators.
  • How iterators can become invalidated by container actions
  • We saw various ways of using C++20 concepts to work with iterators

Was this lesson useful?

Next Lesson

Linked Lists using std::forward_list

This lesson provides an in-depth exploration of std::forward_list, covering creation, management, and advanced list operations
Abstract art representing computer programming
Ryan McCombe
Ryan McCombe
Updated
A computer programmer
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, Unlimited Access
Arrays and Linked Lists
Next Lesson

Linked Lists using std::forward_list

This lesson provides an in-depth exploration of std::forward_list, covering creation, management, and advanced list operations
Abstract art representing computer programming
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved