Creating Custom Iterators using C++20 Concepts

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

View Full Course Free, Unlimited Access
Ryan McCombe
Updated 3 months ago

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  2 public: 3 std::arrayPlayer, 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:

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  2 public: 3 std::string Name; 4 >; 5 6 class Party  7 public: 8 Party(Player A, Player B, 9 Player C) : AA>, BB>, CC>> 10 11 Player A, B, C; 12 >;

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

1#include 2 
 
3 class Player /*. */>; 8 9 class Party  10 public: 11 Party(Player A, Player B, 12 Player C) : AA>, BB>, CC>> 13 14 Player A, B, C; 15 >; 16 17 int 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  2 public: 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 5 private: 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 2 
 
3 class Player /*. */>; 8 9 class Party  10 public: 11 Party(Player A, Player B, 12 Player C) : AA>, BB>, CC>> 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 
 
29 int 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. The 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 &'
  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(); > 2 catch (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 2 
 
3 class Player /*. */>; 8 9 class Party  10 public: 11 Party(Player A, Player B, 12 Player C) : AA>, BB>, CC>> 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 
 
47 int 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:

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:

Similar to class inheritance, we can imagine these iterator categories existing in a hierarchy. The more advanced iterators expand 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:

We’ve implemented all these aliases below:

1#include 2 
 
3 class Player /*. */>; 8 9 class Party  10 public: 11 Party(Player A, Player B, 12 Player C) : AA>, BB>, CC>> 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 
 
55 int 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> 2 void LogIfType(T2&& Iter) 3 if constexpr (std::same_as 4 T1, typename T2::value_type>)  5 std::cout  <(*Iter).Name; 6 > 7 > 8 9 int main() 10 Party Players 11 Player"Anna">, Player"Roderick">, 12 Player"Bob">>; 13 14 LogIfTypePlayer>(Players.begin()); 15 LogIfTypeParty>(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; 2 using element_type = Player; 3 using pointer = Player*; 4 using reference = Player&;

Could be written as:

1using value_type = Player; 2 using element_type = value_type; 3 using pointer = value_type*; 4 using 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_iteratorParty::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_iteratorParty::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;

But a default constructed Party::Iterator is useless?

A default constructed member of our Iterator type is not immediately useful - after all, we don’t know what Player it points to, or even which Party it is iterating.

But the concept doesn’t require a default-constructed iterator to be immediately useful - it just requires it to be an option. This option provides flexibility when creating code that works with those iterators.

For example, an algorithm might want to initialize an iterator, but only assign a value to it later in the process, perhaps from a nested scope:

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

By making our iterator default-constructible, we allow for that option.

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

1#include 2 
 
3 class Player /*. */>; 8 9 class Party  10 public: 11 Party(Player A, Player B, 12 Player C) : AA>, BB>, CC>> 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_iteratorIterator>); 60 Iterator begin() return Iterator(this, 0); > 61 Iterator end() return Iterator(this, 3); > 62 >; 63 
 
64 int main()/*. */>;

The -> Operator

Whilst not required by the concept, it is generally expected that iterators implement the -> operator, providing similar functionality to what it does when used with pointers.

Specifically, the -> operator provides a friendlier way to access members of the object being pointed at:

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

In this example, we could implement the -> operator by calling the * operator we already implemented. This returns a reference to the Player our iterator is pointing at:

1operator*()

We can then get the address of that Player using the & operator, and return it. So our -> iterator can look something like this:

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 2 #include 3 
 
4 class Player /*. */>; 9 
 
10 class Party /*. */>; 65 66 static_assert(std::ranges::forward_rangeParty>);

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 4 static_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: