Iterators

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.

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:

1#include <array>
2
3int main() {
4  std::array Nums{1, 2, 3};
5  auto Start{Nums.begin()};
6}

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:

1#include <array>
2#include <iostream>
3
4int main() {
5  std::array Nums{1, 2, 3};
6  auto Start{Nums.begin()};
7
8  std::cout << "First Object: " << *Start;
9}

1First Object: 1

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

1#include <array>
2#include <iostream>
3
4class Character {
5 public:
6  std::string GetName() { return "Anna"; }
7};
8
9int main() {
10  std::array<Character, 3> Party;
11  auto Start{Party.begin()};
12
13  std::cout << "First: " << Start->GetName();  
14}

1First: 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:

1#include <forward_list>
2#include <iostream>
3
4int main() {
5  std::forward_list Nums{1, 2, 3};
6  auto Start{Nums.begin()};
7  auto Second{++Nums.begin()};
8
9  std::cout << "First: " << *Start;
10  std::cout << "\nSecond: " << *(Second);
11  std::cout << "\nThird: " << *(++Second);  
12}

1First: 1
2Second: 2
3Third: 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:

1#include <list>
2#include <iostream>
3
4int main() {
5  std::list Nums{1, 2, 3};
6  auto Iterator{Nums.begin()};
7
8  std::cout << "First: " << *Iterator;
9  std::cout << "\nSecond: " << *(++Iterator);
10  std::cout << "\nFirst: " << *(--Iterator);  
11}

1First: 1
2Second: 2
3First: 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:

1#include <vector>
2#include <iostream>
3
4int main() {
5  std::vector Nums{1, 2, 3, 4, 5};
6
7  auto Iterator{Nums.begin()};
8  auto Fifth{Iterator + 4};
9
10  std::cout << "First: " << *Iterator;
11  std::cout << "\nFifth: " << *(Fifth);
12  std::cout << "\nThird: " << *(Fifth -= 2);  
13}

1First: 1
2Fifth: 5
3Third: 3

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:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector Nums{1, 2, 3, 4, 5};
6
7  std::cout << "Third: "
8    << *std::next(Nums.begin(), 2);
9}

1Third: 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)$ - 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)$ where $n$ 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:

1#include <iostream>
2#include <vector>
3#include <forward_list>
4
5template <typename T>
6void LogThirdElement(T Container) {
7  std::cout << "\nThird Element: " <<
8    *std::next(Container.begin(), 2);
9}
10
11int main() {
12  std::vector NumsArray{1, 2, 3, 4, 5};
13  std::vector NumsList{1, 2, 3, 4, 5};
14
15  LogThirdElement(NumsArray);
16  LogThirdElement(NumsList);
17}

1Third Element: 3
2Third Element: 3

Backwards Traversal using std::prev()

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

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector Nums{1, 2, 3, 4, 5};
6
7  auto First{Nums.begin()};
8  auto Third{std::next(First, 2)};
9  auto Second{std::prev(Third, 1)};
10
11  std::cout << "First: " << *First;
12  std::cout << "\nSecond: " << *Second;
13  std::cout << "\nThird: " << *Third;
14}

1First: 1
2Second: 2
3Third: 3

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

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list Nums{1, 2, 3, 4, 5};
6
7  auto First{Nums.begin()};
8  auto Third{std::next(First, 2)};
9  auto Second{std::prev(Third, 1)};  
10}

1error: 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:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector Nums{1, 2, 3, 4, 5};
6
7  auto First{Nums.begin()};
8  auto Third{std::next(First, 2)};
9  auto Second{std::next(Third, -1)};
10}

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:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list Nums{1, 2, 3, 4, 5};
6
7  auto First{Nums.begin()};
8  auto Third{std::next(First, 2)};
9  auto Second{std::next(Third, -1)};
10}

1error: negative advance of non-bidirectional iterator
2example.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:

1#include <array>
2#include <iostream>
3
4int main() {
5  std::array Nums{1, 2, 3};
6
7  auto Start{Nums.begin()};
8  auto End{Nums.end()};
9
10  for (auto It{Start}; It != End; ++It) {
11    std::cout << *It << ", ";
12  }
13}

11, 2, 3,

1#include <array>
2#include <iostream>
3
4int main() {
5  std::array Nums{1, 2, 3};
6  *Nums.end(); 
7}

1example.exe (process 60252) exited with code 3.
2error: cannot dereference out of range array iterator

1#include <array>
2#include <iostream>
3
4int main() {
5  std::array Nums{1, 2, 3};
6  std::cout << "Last: "
7    << *std::next(Nums.end(), -1);
8}

1Last: 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.

Implementing Ranges for Custom Types

Learn to implement iterators in custom types, and make them compatible with range-based techniques.

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:

1#include <iostream>
2#include <forward_list>
3
4int main() {
5  std::forward_list MyList { 1, 2, 3, 4, 5 };
6
7  for (int x : MyList) {
8    std::cout << x << ", ";
9  }
10}

11, 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:

1#include <array>
2#include <iostream>
3
4class Character {
5 public:
6  void SetName(){};
7  void GetName() const {};
8};
9
10int main() {
11  std::array<Character, 5> Collection;
12
13  // Pass by reference
14  for (Character& C : Collection) {
15    C.SetName();
16  }
17
18  // Pass by const reference
19  for (const Character& C : Collection) {
20    // Cannot call non-const function
21    C.SetName();
22  }
23}

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:

1#include <vector>
2#include <iostream>
3
4int main() {
5  std::vector Nums{1, 2, 3, 4, 5};
6  ptrdiff_t Distance{Nums.end() - Nums.begin()};
7  std::cout << "Distance: " << Distance;
8}

1Distance: 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():

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector Nums{1, 2, 3};
6  auto Iterator{Nums.begin()};
7  while (Iterator != Nums.end()) {
8    std::cout << (Nums.end() - Iterator)
9      << " object(s) remaining\n";
10    ++Iterator;
11  }
12}

13 object(s) remaining
22 object(s) remaining
31 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:

1#include <vector>
2#include <iostream>
3
4int main() {
5  std::vector Nums{1, 2, 3, 4, 5};
6
7  ptrdiff_t Distance{
8    std::distance(Nums.begin(), Nums.end())};
9
10  std::cout << "Distance: " << Distance;
11}

1Distance: 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)$.

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)$, where $n$ 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:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5void Log(int x) {
6  std::cout << "Number: " << x << '\n';
7}
8
9int main() {
10  std::vector Nums{1, 2, 3};
11  std::for_each(Nums.begin(), Nums.end(), Log);
12}

1Number: 1
2Number: 2
3Number: 3

Constant Iterators

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

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5void Increment(int& x) { ++x; }
6
7void Log(int x) {
8  std::cout << "Number: " << x << '\n';
9}
10
11int main() {
12  std::vector Nums{1, 2, 3};
13  std::for_each(
14    Nums.begin(), Nums.end(), Increment);
15
16  std::for_each(Nums.begin(), Nums.end(), Log);
17}

1Number: 2
2Number: 3
3Number: 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:

1#include <vector>
2#include <algorithm>
3
4void Increment(int& x) { ++x; }
5
6int main() {
7  std::vector Nums{1, 2, 3};
8  std::for_each(
9    Nums.cbegin(), Nums.cend(), Increment);
10}

1error 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:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5void Log(int x) {
6  std::cout << "Number: " << x << '\n';
7}
8
9int main() {
10  std::vector Nums{1, 2, 3};
11  std::for_each(
12    Nums.rbegin(), Nums.rend(), Log);
13}

1Number: 3
2Number: 2
3Number: 1

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:

1#include <vector>
2
3int main() {
4  std::vector Vec{1, 2, 3};
5  auto Iterator{Vec.begin()};
6  Vec.resize(100);
7  *Iterator;
8}

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:

1can't dereference invalidated vector iterator
2example.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:

1#include <vector>
2
3int main() {
4  std::vector<int>::iterator A;
5  std::vector<int>::const_iterator B;
6}

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

1#include <vector>
2
3int main() {
4  std::vector Nums{1, 2, 3};
5
6  decltype(Nums)::iterator A;
7  decltype(Nums)::const_iterator B;
8}

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

1#include <vector>
2
3int main() {
4  std::vector Nums{1, 2, 3};
5  using NumsIterator = decltype(Nums)::iterator;
6
7  NumsIterator A;
8}

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.

Concepts in C++20

Learn how to use C++20 concepts to constrain template parameters, improve error messages, and enhance code readability.

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:

1#include <iterator>
2#include <forward_list>
3#include <iostream>
4
5int main() {
6  std::forward_list NumbersList{1, 2, 3};
7
8  if constexpr (std::forward_iterator<
9    decltype(NumbersList)::iterator>
10  ) {
11    std::cout << "It's a forward iterator";
12  }
13
14  if constexpr (!std::random_access_iterator<
15    decltype(NumbersList)::iterator>
16  ) {
17    std::cout << " but not random access";
18  }
19}

1It'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:

1#include <forward_list>
2#include <iostream>
3
4template <typename T>
5void SomeAlgorithm(T& Container) {
6  static_assert(std::random_access_iterator<
7    typename T::iterator>,
8    "Only supports random access containers"
9  );
10
11  // ...
12}
13
14int main() {
15  std::forward_list NumbersList{1, 2, 3};
16  SomeAlgorithm(NumbersList);
17}

1main.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:

1#include <forward_list>
2#include <iostream>
3
4template <typename T>
5requires std::random_access_iterator<
6    typename T::iterator>
7void SomeAlgorithm(T& Container) {
8  // ...
9}
10
11int main() {
12  std::forward_list NumbersList{1, 2, 3};
13  SomeAlgorithm(NumbersList);
14}

1error: the associated constraints are not satisfied
2the 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:

1#include <iterator>
2
3template <typename T>
4concept RandomAccess = requires(T) {
5  requires std::random_access_iterator<
6    typename T::iterator>;
7};

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:

1#include <iterator>
2
3template <typename T>
4concept NotRandomAccess = requires(T) {
5  requires std::forward_iterator<
6    typename T::iterator>;
7  requires(!std::random_access_iterator<
8    typename T::iterator>);
9};

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:

1#include <iterator>
2#include <iostream>
3#include <vector>
4#include <forward_list>
5
Unchanged Code|Show
6concept RandomAccess = requires(T) {}
12
Unchanged Code|Show
13concept NotRandomAccess = requires(T) {}
21
22void SomeAlgo(RandomAccess auto Container) {
23  std::cout << "Random Access Variation\n";
24}
25
26void SomeAlgo(NotRandomAccess auto Container) {
27  std::cout << "Not Random Access Variation\n";
28}
29
30int main() {
31  std::vector NumbersArray{1, 2, 3};
32  SomeAlgo(NumbersArray);
33
34  std::forward_list NumbersList{1, 2, 3};
35  SomeAlgo(NumbersList);
36}

1Random Access Variation
2Not 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

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

ContinueView Course