Iterators and Ranges

Earlier in the course, we introduced the idea of iterators, which generalize the process of traversing through a container.

Rather than writing a function that works with a specific type of container, we can instead write it to work with iterators.

Below, our function template has no notion of containers - it simply advances an iterator until an endpoint:

1#include <iostream>
2
3void Log(auto Iterator, auto End) {
4  while (Iterator != End) {
5    std::cout << *(Iterator++) << ", ";
6  }
7}

Such an algorithm can work with any container that provides iterators.

Containers typically make iterators available through begin() and end() methods:

1#include <vector>
2#include <forward_list>
3#include <iostream>
4
Unchanged Code|Show
5void Log(auto Iterator, auto End) {/*...*/}
11
12int main() {
13  std::forward_list List{1, 2, 3};
14  std::cout << "std::forward_list<int>:\n";
15  Log(List.begin(), List.end());
16
17  std::vector Vector{1, 2, 3};
18  std::cout << "\n\nstd::vector<int>:\n";
19  Log(Vector.begin(), Vector.end());
20}

1std::forward_list<int>:
21, 2, 3,
3
4std::vector<int>:
51, 2, 3,

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 chapter builds on our knowledge of iterators, to unlock even more capabilities.

What is a Range?

All of the standard library sequential containers we’ve introduced so far, such as std::vector and std::forward_list are examples of ranges.

The concept of a range was introduced in C++20, and is built on the foundations created by iterators.

Similar to iterators, a range establishes a convention on how a type must work for it to be considered a range.

Specifically, a range is any type that has a begin() method that returns an iterator, and an end() method that lets us determine when the range ends.

If a type decides to implement that specification, then the type is a range, and can then be used with range-based techniques.

Much of this chapter will be dedicated to exploring those techniques.

Range-Based For Loops

One of the main techniques that we can apply when working with ranges is the range-based for loop, which we’ve seen a few times in the past.

If a type is a range, then we can use the range-based for-loop syntax to iterate over it:

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

11, 2, 3,

In the next lesson, we’ll see how can update a custom type that we create to satisfy the range requirements, thereby becoming compatible with range-based for loops.

Passing by (const) Reference

Similar to functions, our objects are passed into the body of our loop by value, meaning they are copied.

If our type is expensive to copy, we will likely want to pass them by reference instead.

Additionally, if we’re not planning to modify the object within the body, we can mark those references as const:

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

11, 2, 3,

Range Categories

In the introduction to iterators, we covered how not all iterators have the same capabilities. They are broken down into categories, for example:

• A forward iterator can only move forward through the collection, one object at a time
• A bidirectional iterator can move forward and backward through the collection, one object at a time
• A random access iterator can move forward and backward, and by any distance

Given ranges are built upon iterators, it’s perhaps not surprising that ranges are also separated into categories, based on the capability of the iterator they are based upon.

For example:

• A forward range, such as a std::forward_list, only supports traversal in one direction, one step at a time.
• A bidirectional range, such as a std::list, supports traversal in either direction, one step at a time
• A random-access range, such as a std::vector, allows access to freely jump to any object in the range

Similar to iterator categories, we can imagine ranges existing in a hierarchy, where a more powerful range also meets the requirements of a less powerful range.

For example, a bidirectional range implements all the requirements of a forward range, so it is a forward range.

A random-access range implements all the requirements of a bidirectional range, so it is a bidirectional range. And therefore, it is also a forward range.

Range Concepts

Concepts are available to determine if a type is a valid range.

Concepts in C++20

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

These are available within std::ranges namespace, after including the <ranges> header. For example:

• std::ranges::forward_range determines whether a type is a forward range.
• std::ranges::bidirectional_range determines whether a type is a bidirectional range
• std::ranges::random_access_range determines whether a type is a random access range

Below, we use this to investigate the types our template was instantiated with:

1#include <vector>
2#include <list>
3#include <forward_list>
4#include <ranges>
5#include <iostream>
6
7template <typename T>
8void Log(T Range) {
9  if constexpr (std::ranges::forward_range<T>) {
10    std::cout << " - Forward Range\n";
11  }
12
13  if constexpr (
14    std::ranges::bidirectional_range<T>
15  ) {
16    std::cout << " - Bidirectional Range\n";
17  }
18
19  if constexpr (
20    std::ranges::random_access_range<T>
21  ) {
22    std::cout << " - Random Access Range\n";
23  }
24}
25
26int main() {
27  std::cout << "std::forward_list<int>:\n";
28  Log(std::forward_list{1, 2, 3});
29
30  std::cout << "\nstd::list<int>:\n";
31  Log(std::list{1, 2, 3});
32
33  std::cout << "\nstd::vector<int>:\n";
34  Log(std::vector{1, 2, 3});
35}

1std::forward_list<int>:
2 - Forward Range
3
4std::list<int>:
5 - Forward Range
6 - Bidirectional Range
7
8std::vector<int>:
9 - Forward Range
10 - Bidirectional Range
11 - Random Access Range

In this example, we use it to create a template that requires a type to be at least a bidirectional range:

1#include <forward_list>
2#include <ranges>
3#include <iostream>
4
5void LogLast(
6  std::ranges::bidirectional_range auto R
7) {
8  std::cout << *(std::next(R.end(), -1));
9}
10
11int main() {
12  LogLast(std::forward_list{1, 2, 3});
13}

1error C2672: 'LogLast': no matching overloaded function found
2the associated constraints are not satisfied
3the concept 'std::ranges::bidirectional_range<std::forward_list<int>>' evaluated to false

Summary

In this lesson, we explored iterators and ranges, demonstrating how they enable flexible traversal through various container types

Key Takeaways:

• Iterators provide a generalized way to traverse containers, independent of the container type.
• Functions that work on iterators can operate on any container type that supports iterators, enhancing code reusability.
• Standard containers like std::vector and std::forward_list offer begin() and end() methods, making them compatible with iterators.
• The concept of ranges, introduced in C++20, is foundational for types that have begin() and end() methods.
• Range-based for loops offer a convenient way to iterate over elements in a range.
• Passing objects by (const) reference in range-based for loops can optimize performance, especially for expensive-to-copy objects.
• Ranges are categorized based on the capabilities of their underlying iterators, such as forward, bidirectional, and random-access ranges.
• C++20's range concepts in the std::ranges namespace help determine the category of a range.

Next Lesson

Implementing Ranges for Custom Types

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

ContinueView Course