Iterators and Ranges

This lesson offers an in-depth look at iterators and ranges, emphasizing their roles in container traversal
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
3D Character Concept Art
Ryan McCombe
Ryan McCombe
Edited

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:

#include <iostream>

void Log(auto Iterator, auto End) {
  while (Iterator != End) {
    std::cout << *(Iterator++) << ", ";
  }
}

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

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

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

void Log(auto Iterator, auto End) {/*...*/} int main() { std::forward_list List{1, 2, 3}; std::cout << "std::forward_list<int>:\n"; Log(List.begin(), List.end()); std::vector Vector{1, 2, 3}; std::cout << "\n\nstd::vector<int>:\n"; Log(Vector.begin(), Vector.end()); }
std::forward_list<int>:
1, 2, 3,

std::vector<int>:
1, 2, 3,

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:

#include <vector>
#include <iostream>

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

  for (int x : Vector) {
    std::cout << x << ", ";
  }
}
1, 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:

#include <vector>
#include <iostream>

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

  for (const int& x : Vector) {
    std::cout << x << ", ";
  }
}
1, 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.

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:

#include <vector>
#include <list>
#include <forward_list>
#include <ranges>
#include <iostream>

template <typename T>
void Log(T Range) {
  if constexpr (std::ranges::forward_range<T>) {
    std::cout << " - Forward Range\n";
  }

  if constexpr (
    std::ranges::bidirectional_range<T>
  ) {
    std::cout << " - Bidirectional Range\n";
  }

  if constexpr (
    std::ranges::random_access_range<T>
  ) {
    std::cout << " - Random Access Range\n";
  }
}

int main() {
  std::cout << "std::forward_list<int>:\n";
  Log(std::forward_list{1, 2, 3});

  std::cout << "\nstd::list<int>:\n";
  Log(std::list{1, 2, 3});

  std::cout << "\nstd::vector<int>:\n";
  Log(std::vector{1, 2, 3});
}
std::forward_list<int>:
 - Forward Range

std::list<int>:
 - Forward Range
 - Bidirectional Range

std::vector<int>:
 - Forward Range
 - Bidirectional Range
 - Random Access Range

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

#include <forward_list>
#include <ranges>
#include <iostream>

void LogLast(
  std::ranges::bidirectional_range auto R
) {
  std::cout << *(std::next(R.end(), -1));
}

int main() {
  LogLast(std::forward_list{1, 2, 3});
}
error C2672: 'LogLast': no matching overloaded function found
the associated constraints are not satisfied
the 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.

Was this lesson useful?

Edit History

  • Refreshed Content

  • First Published

Ryan McCombe
Ryan McCombe
Edited
Lesson Contents

Iterators and Ranges

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

7a.jpg
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
7a.jpg
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

This course includes:

  • 114 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Next Lesson

Implementing Ranges for Custom Types

Learn to implement iterators in custom types, and make them compatible with range-based techniques.
3D Character Concept Art
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved