Creating Custom Iterators using C++20 Concepts

Previously, we implemented iterators for our custom container simply by forwarding the iterators from the underlying type to which we were deferring storage.

Below, our custom type is using a std::array to store its objects, so we can just forward any calls to begin() and end() to that underlying array:

1class Party {
2public:
3  std::array<Player, 3> Array;
4  auto begin() { return Array.begin(); }
5  auto end() { return Array.end(); }
6};

In this lesson, we will instead see how we can add iterators to our custom container ourselves, building them from scratch. This has three advantages:

• It helps us learn more about iterators
• Often we’ll want to implement iterators in situations where we don’t have some other underlying container that can bear the burden
• Even if there is an underlying container that supports iterators, sometimes we’ll want our custom type’s iterators to behave differently

Let's get started!

Starting Point

Our starting point is below. We have a custom Party type that contains three Player objects, which we’re calling A, B, and C

1class Player {
2public:
3  std::string Name;
4};
5
6class Party {
7public:
8  Party(Player A, Player B,
9        Player C) : A{A}, B{B}, C{C}{}
10
11  Player A, B, C;
12};

Our main function instantiates a Party, and would like to be able to perform a range-based for loop to iterate over the Player objects it contains:

1#include <iostream>
2
Player Class (Unchanged)|Show
3class Player {/*...*/};
8
9class Party {
10public:
11  Party(Player A, Player B,
12        Player C) : A{A}, B{B}, C{C}{}
13
14  Player A, B, C;
15};
16
17int main(){
18  Party Party{
19    Player{"Anna"}, Player{"Roderick"},
20    Player{"Bob"}};
21
22  for (Player& P : Party) {
23    std::cout << P.Name << ", ";
24  }
25}

Scaffolding the Iterator

If we run the previous code, we’re likely to get a compilation error similar to:

1'begin': no matching overloaded function found

This is expected - we’re trying to use a range-based for loop with a Party object, and Party is not yet a range.

As we covered earlier, for a type to be a range, it needs to implement a begin() method which returns an iterator, and an end() method which returns a sentinel - which is often also an iterator.

Defining Ranges using Sentinels

An alternative way of defining ranges, and why we sometimes need to use them

In this case, we’re building a custom iterator, so we need to define a new custom type. When an iterator is designed to work with a specific container, it is common for that iterator type to be defined within the container’s class or struct:

1class Party {
2public:
3  struct Iterator {
4    // ...
5  };
6};

This has an effect similar to namespacing - our iterator type will be available through the scope resolution operator, as Party::Iterator

Let's build out some initial scaffolding for our iterator. It will need two data members - the Party object it is iterating, and the Player object it’s pointing at within that party.

We’ll represent the Player as an index, where 0 maps to the Player called A, 1 maps to B, and 2 maps to C

We’ll also need a constructor to initialize these members:

1struct Iterator {
2  Iterator(Party* ptr, size_t idx) :
3    Party(ptr), idx(idx){}
4
5private:
6  size_t idx;
7  Party* Party;
8};

Next, let's add begin() and end() methods to our Party that returns appropriate iterators. The begin() method returns an iterator with an idx of 0, - that is, pointing at the Player called A

The end() method will return an iterator with an idx of 3 - that is, pointing "past the end" of our container, in the same way we’ve seen with other container types.

Putting all this together, our code now looks like this:

1#include <iostream>
2
Player Class (Unchanged)|Show
3class Player {/*...*/};
8
9class Party {
10public:
11  Party(Player A, Player B,
12        Player C) : A{A}, B{B}, C{C}{}
13
14  Player A, B, C;
15
16  struct Iterator {
17    Iterator(Party* ptr, size_t idx) :
18      Party(ptr), idx(idx){}
19
20  private:
21    size_t idx;
22    Party* Party;
23  };
24
25  Iterator begin(){ return Iterator(this, 0); }
26  Iterator end(){ return Iterator(this, 3); }
27};
28
Main Function (Unchanged)|Show
29int main(){/*...*/};

Implementing a Minimal Iterator

Our main function hasn’t changed, but it can now find the begin() and end() methods of our Party container.

As such, it can create iterators from the type we defined, but that type is missing some required operators. Our compilation error is likely to include messages like the following:

1unary '++': 'Party::Iterator' does not define this operator
2binary '!=': 'Party::Iterator' does not define this operator
3cannot convert from 'Party::Iterator' to 'Player &'

To summarise:

1. The loop is not able to advance our iterator through the collection, because the iterator doesn’t have the unary ++ operator
2. The loop isn’t able to determine whether it should continue, because we haven’t implemented the binary != operator. The loop will continue as long as Iterator != Party.end(), so our iterator objects must be able to compare themselves to the sentinel type returned from Party.end()
3. The loop is not able to get a reference to the Player our iterator is pointing at, through the dereferencing operator *.

So, we need to implement all three of these capabilities.

1. The ++ Operator

In this case, we only need the prefix variation of the ++ operator:

1Iterator& operator++(){
2  idx++;
3  return *this;
4}

We’ll implement the postfix ++ operator later in this lesson.

2. The == Operator

Whilst we specifically need the != operator, as of C++20, explicitly defining this operator is unnecessary.

If we instead define the == operator, the compiler can handle the != operator for us automatically. We cover this in more detail later in the course:

The Spaceship Operator and Expression Rewriting

A guide to simplifying our comparison operators using C++20 features

For the == operator, we can consider two iterators equal if they are iterating over the same Party, and are pointing at the same Player within that Party - ie, they have the same idx:

1bool operator==(const Iterator& b) const{
2  return Party == b.Party && idx == b.idx;
3}

If we’re writing code to be compiled to specifications before C++20, we should additionally implement the != operator manually:

1bool operator!=(const Iterator& b) const{
2  return !(*this == b);
3}

3. The * operator

The * operator is how our iterator generates a reference to the object it is pointing at.

The implementation of this operator is going to vary greatly based on how the associated container stores its data.

Within our contrived example, we can just use three if statements, that map the idx values of 0, 1, and 2 to their respective player within the Party we’re iterating.

1Player& operator*() const{
2  if (idx == 0) return Party->A;
3  if (idx == 1) return Party->B;
4  if (idx == 2) return Party->C;
5
6  throw std::out_of_range{
7    "Parties can only have 3 players"};
8}

We’ve additionally thrown an exception, in case an iterator is ever dereferenced with any other idx value. Below, we try to dereference the past-the-end iterator, which will have an idx of 3:

1try { *Party.end(); }
2catch (std::exception& e) {
3  std::cout << e.what();
4}

1Parties can only have 3 players

With all these operators implemented, our code now looks like this:

1#include <iostream>
2
Player Class (Unchanged)|Show
3class Player {/*...*/};
8
9class Party {
10public:
11  Party(Player A, Player B,
12        Player C) : A{A}, B{B}, C{C}{}
13
14  Player A, B, C;
15
16  struct Iterator {
17    Iterator(Party* ptr, size_t idx) :
18      Party(ptr), idx(idx){}
19
20    Player& operator*() const{
21      if (idx == 0) return Party->A;
22      if (idx == 1) return Party->B;
23      if (idx == 2) return Party->C;
24
25      throw std::out_of_range{
26        "Parties can only have 3 players"};
27    }
28
29    Iterator& operator++(){
30      idx++;
31      return *this;
32    }
33
34    bool operator==(const Iterator& b) const{
35      return Party == b.Party && idx == b.idx;
36    }
37
38  private:
39    size_t idx;
40    Party* Party;
41  };
42
43  Iterator begin(){ return Iterator(this, 0); }
44  Iterator end(){ return Iterator(this, 3); }
45};
46
Main Function (Unchanged)|Show
47int main(){/*...*/};

Additionally, it compiles and runs as we expect:

1Anna, Roderick, Bob,

However, our iterator is not yet fully complete. Whilst it is sufficient for use in a range-based for loop, it won’t work in many other iterator-based contexts.

There are some more things we need to add before it is a fully-fledged iterator type.

Container Access Patterns

We’ve discussed how iterators provide a generalized way of traversing through containers. This allows us to write algorithms and other code that can interact with containers, without necessarily knowing the type of those containers.

However, we’ve also seen that not all containers support the same forms of traversal. For example:

• A singly linked list, such as std::forward_list is designed only to support traversal in a single direction. From each element, we can only access the next element in the sequence.
• A doubly linked list, such as std::list can support traversal in both directions. We can move either forward or backward as needed
• Containers such as std::vector and std::deque support a pattern called random access. We can freely jump to whatever part of the container we wish, typically using the subscript operator []

This presents a problem as, by design, generic code using iterators does not inherently know what access pattern the underlying container supports.

Perhaps our algorithm requires random access, but the container doesn’t support it. Perhaps the algorithm has two implementations - an efficient variation that requires random access, but a slower variation that only requires forward traversal.

We manage this by categorizing the iterators associated with our container.

Iterator Categories

The main way we communicate the access patterns our iterator supports is by imagining them as fitting within one of several categories. For example:

• A std::forward_iterator supports traversal in a single direction. This is the type of iterator returned by containers such as a std::forward_list
• A std::bidirectional_iterator supports traversal in either direction. This is the type of iterator returned by containers such as a std::list
• A std::random_access_iterator supports access to any arbitrary collection member. This is the type of iterator returned by containers such as a std::deque
• A std::contiguous_iterator supports the same access pattern as a random access iterator, with the additional requirement that elements adjacent in the container are also adjacent in memory. This is the type of iterator returned by array containers such as std::vector

Similar to class inheritance, we can imagine these iterator categories existing in a hierarchy. The more advanced iterators are expanding on their more basic ancestors.

So, for example, a bidirectional iterator has all the capabilities of a forward iterator, so it effectively is a forward iterator. Any code that expects a forward iterator would also work when given a bidirectional iterator.

For the same reason, a random access iterator is both a forward iterator and a bidirectional iterator, and a contiguous iterator is all of the above.

Iterator Tags and Type Aliases

There are two main ways we categorize our iterator. The first way is by ensuring our iterator satisfies a C++20 concept. The standard library identifiers we listed above, such as std::forward_iterator are all concepts. Later in this lesson, we ensure our iterator satisfies this concept.

The second way we categorize our iterator is through a "tag". This takes the form of defining an iterator_category type within our iterator, by aliasing a standard library type. The standard library tags have the same identifiers as their respective concept, with the addition of a _tag suffix:

1struct Iterator {
2  using iterator_category =
3    std::forward_iterator_tag;
4
5  // ...
6};

This gives any other code an easy, compile-time way to determine what type of iterator it’s dealing with. It just needs to check the Iterator::iterator_category member.

It’s also common to add several more using statements to our iterators, to provide easy access to other information that is commonly required when writing templates that use iterators.

The other standard aliases are:

• value_type: The type of object our iterator is pointing at - Player, in this case
• element_type: Another alias for value_type - again this is Player in this case
• reference: The reference form of value_type - Player&, in this case
• pointer: The pointer form of value_type - Player* in this case
• difference_type: The type used for pointer arithmetic - in most cases, this can be set to std::ptrdiff_t

We’ve implemented all these aliases below:

1#include <iostream>
2
Player Class (Unchanged)|Show
3class Player {/*...*/};
8
9class Party {
10public:
11  Party(Player A, Player B,
12        Player C) : A{A}, B{B}, C{C}{}
13
14  Player A, B, C;
15
16  struct Iterator {
17    using iterator_category =
18    std::forward_iterator_tag;
19    using value_type = Player;
20    using element_type = Player;
21    using pointer = Player*;
22    using reference = Player&;
23    using difference_type = std::ptrdiff_t;
24
25    Iterator(Party* ptr, size_t idx) :
26      Party(ptr), idx(idx){}
27
28    Player& operator*() const{
29      if (idx == 0) return Party->A;
30      if (idx == 1) return Party->B;
31      if (idx == 2) return Party->C;
32
33      throw std::out_of_range{
34        "Parties can only have 3 players"};
35    }
36
37    Iterator& operator++(){
38      idx++;
39      return *this;
40    }
41
42    bool operator==(const Iterator& b) const{
43      return Party == b.Party && idx == b.idx;
44    }
45
46  private:
47    size_t idx;
48    Party* Party;
49  };
50
51  Iterator begin(){ return Iterator(this, 0); }
52  Iterator end(){ return Iterator(this, 3); }
53};
54
Main Function (Unchanged)|Show
55int main(){/*...*/};

This allows other ours and other code to easily work with our iterators at compile time. Below, we use the new value_type alias to easily determine what our iterator type points at:

1template <typename T1, typename T2>
2void LogIfType(T2&& Iter){
3  if constexpr (std::same_as<
4    T1, typename T2::value_type>) {
5    std::cout << (*Iter).Name;
6  }
7}
8
9int main(){
10  Party Players{
11    Player{"Anna"}, Player{"Roderick"},
12    Player{"Bob"}};
13
14  LogIfType<Player>(Players.begin());
15  LogIfType<Party>(Players.begin());
16}

1Anna

We can also use those aliases within our iterator struct if preferred. For example, the following code:

1using value_type = Player;
2using element_type = Player;
3using pointer = Player*;
4using reference = Player&;

Could be written as:

1using value_type = Player;
2using element_type = value_type;
3using pointer = value_type*;
4using reference = value_type&;

And a method such as:

1Player& operator*() const{
2  // ...
3}

Could be written as:

1reference operator*() const{
2  // ...
3}

Iterator Concepts

C++20 introduced concepts, which we covered in a dedicated lesson:

Concepts in C++20

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

For algorithms and other code written from C++20 onwards, concepts tend to be the main way we identify the category of iterator. For example, a type is a forward iterator if it satisfies the std::forward_iterator concept. If it does, an expression like the following will return true:

1std::forward_iterator<Party::Iterator>

The easiest way to determine if our type meets the requirements is to statically assert that the previous expression returns true:

1static_assert(
2  std::forward_iterator<Party::Iterator>
3);

When we add this assertion, we’re likely to find our iterator does not currently satisfy the concept. Our compiler should hopefully generate helpful feedback telling us why.

As of the C++23 specification, there are two reasons our iterator does not yet satisfy the concept:

std::incremental is false because Iterator++ is not supported

Our iterator implements the prefix ++ operator, but we also need to overload the postfix ++ variation.

When our type already implements the prefix ++ operator, there tends to be a repeatable pattern in implementing the postfix variation.

It involves copying the current object to a temporary variable, incrementing the current object using the prefix operator, and then returning the copy. It looks like this:

1Iterator operator++(int){
2  Iterator tmp = *this;
3  ++(*this);
4  return tmp;
5}

If this is not clear, we introduced the unary increment operators, and how to overload them in more detail earlier in the course:

The this Pointer

Learn about the this pointer in C++ programming, focusing on its application in identifying callers, chaining functions, and overloading operators.

std::default_initializable is false

The std::incremental concept also requires our iterator to be default-constructible. Because our iterator has a user-defined constructor, the default constructor has been deleted. We can re-add it easily:

1Iterator() = default;

1Party::Iterator SomeIterator;
2// ...
3if (SomeBoolean){
4  SomeIterator = SomeParty.begin();
5}

With the additions of the static_assert, postfix ++ operator, and default constructor, our forward iterator is complete. It looks like this:

1#include <iostream>
2
Player Class (Unchanged)|Show
3class Player {/*...*/};
8
9class Party {
10public:
11  Party(Player A, Player B,
12        Player C) : A{A}, B{B}, C{C}{}
13
14  Player A, B, C;
15
16  struct Iterator {
17    using iterator_category =
18    std::forward_iterator_tag;
19    using element_type = Player;
20    using value_type = Player;
21    using pointer = Player*;
22    using reference = Player&;
23    using difference_type = std::ptrdiff_t;
24
25    Iterator() = default; 
26
27    Iterator(Party* ptr, size_t idx) :
28      Party(ptr), idx(idx){}
29
30    Player& operator*() const{
31      if (idx == 0) return Party->A;
32      if (idx == 1) return Party->B;
33      if (idx == 2) return Party->C;
34
35      throw std::out_of_range{
36        "Parties can only have 3 players"};
37    }
38
39    Iterator& operator++(){
40      idx++;
41      return *this;
42    }
43
44    Iterator operator++(int){
45      Iterator tmp = *this;
46      ++(*this);
47      return tmp;
48    }
49
50    bool operator==(const Iterator& b) const{
51      return Party == b.Party && idx == b.idx;
52    }
53
54  private:
55    size_t idx;
56    Party* Party;
57  };
58
59  static_assert(std::forward_iterator<Iterator>);
60  Iterator begin(){ return Iterator(this, 0); }
61  Iterator end(){ return Iterator(this, 3); }
62};
63
Main Function (Unchanged)|Show
64int main(){/*...*/};

1Party::Iterator A{Party.begin()};
2
3// Without -> Operator:
4(*A).Name;
5
6// With -> Operator:
7A->Name;

1operator*()

1Player* operator->() const{
2  return &operator*();
3}

Range Concepts

Because our type has a begin() method that returns a forward iterator, and an end() method that returns a sentinel, our type is also a range.

Specifically, it is a forward range, and we can additionally add a static assertion for this if we wish:

1#include <iostream>
2#include <ranges>
3
Player Class (Unchanged)|Show
4class Player {/*...*/};
9
Party Class (Unchanged)|Show
10class Party {/*...*/};
65
66static_assert(std::ranges::forward_range<Party>);

We covered range concepts in more detail at the start of this chapter:

Iterators and Ranges

This lesson offers an in-depth look at iterators and ranges, emphasizing their roles in container traversal

Expanding the Forward Iterator

We may want to adapt our forward iterator to a more capable form, such as a bidirectional iterator or random access iterator. This simply involves updating the iterator_category tag and adding the additional operators that the category requires.

For example, a std::bidirectional_iterator requires us to implement the unary -- operators, to allow our iterator to move to the previous element;

1auto LastElement { --Container.end() };

The std::random_access_iterator requires us to implement the subscript operator [], as well as binary arithmetic operators such as - and +. These allow our iterator to move freely around the container:

1Container.begin() + 5;

We can ensure we meet the requirements, or find out what our type is missing, in the same way we did for std::forward_iterator. That is, we pass our type to the concept we want to implement, and statically assert that we’re meeting the requirements:

1static_assert(std::bidirectional_iterator
2  <Party::Iterator>);
3
4static_assert(std::random_access_iterator
5  <Party::Iterator>);

Summary

In this lesson, we explored the process of creating custom iterators for our types, leveraging C++20 concepts. The key things we learned included:

• Implementing a custom iterator for a user-defined type.
• Differentiating between iterator categories like forward, bidirectional, and random access iterators.
• Utilizing iterator tags and type aliases for defining iterator properties.
• Implementing essential iterator operations such as ++, ==, *, and ->.
• Understanding and using C++20 concepts like std::forward_iterator to ensure our types satisfy the requirements.
• Adapting a forward iterator to more advanced types like bidirectional or random access iterators.

Next Lesson

Iterator and Range-Based Algorithms

An introduction to iterator and range-based algorithms, using examples from the standard library

ContinueView Course