Defining Ranges using Sentinels

In earlier lessons, we saw how any container with appropriate begin() and end() methods is a range.

The range starts at the memory address denoted by the begin() iterator and ends at the memory address denoted by the end() iterator.

There is an alternative way to define a range. We establish the starting point as an iterator as before, but rather than defining the ending as a specific memory address, we instead define it using a sentinel.

We’ll cover this pattern in this lesson, and explain the reasons why we would need to use it.

Limitations of End Iterators

Using an iterator to define where a range ends doesn’t give us all the flexibility of traditional loops.

When the end of a range is defined by an iterator, we need to know where that iterator should point to in advance. That’s not always possible - sometimes our end condition is only uncovered in the process of running the algorithm.

For example, imagine we wanted our range of numbers to end at the first negative number. We don’t necessarily know where that is in advance, so we can’t provide an iterator to it unless we first run a different algorithm to figure out where that iterator should point to.

With a traditional for loop, this would have been an easy problem to solve. We could write whatever expression we desire as our continue clause:

1#include <iostream>
2#include <vector>
3
4int main(){
5  std::vector R{1, 4, 3, 8, -2, 5};
6
7  for (
8    auto it = R.begin();
9    *it >= 0; 
10    ++it
11  ) {
12    std::cout << *it << ", ";
13  }
14}

11, 4, 3, 8,

Let’s see how we can empower ranges to have the same capability, by introducing sentinels.

What Are Sentinels?

A sentinel is a fairly generic concept within programming. It simply means something that can signal an algorithm to end.

We were already familiar with this concept when we were writing loops. For example, we saw a similar behavior when we first introduced iterators within a basic for loop. With loops, we just approach it from the opposite direction - we defined when we wanted the loop to continue, rather than when we wanted it to stop:

1#include <iostream>
2#include <vector>
3
4int main(){
5  std::vector R{1, 4, 3, 8, -2, 5};
6
7  for (
8    auto it = R.begin();
9    it != R.end(); // Continue if true 
10    ++it
11  ) {
12    std::cout << *it << ", ";
13  }
14}

11, 4, 3, 8, -2, 5,

For reasons we covered earlier in this chapter, we want to move away from for loops. They’re quite verbose and don’t generalize well.

Using the iterator-sentinel form of a range, we can get the same behavior using a range-based algorithm, like std::ranges::for_each():

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

11, 4, 3, 8, -2, 5,

In this case, rather than providing our range as a single value, we’ve provided it as two values - an iterator where the range starts, and a sentinel that will signal when the range ends.

Within the context of C++ ranges, sentinels are objects that can be compared to iterators, using the equality (==) operator. If the operator returns true, that’s the signal for the algorithm to stop.

1std::ranges::for_each(R.begin(), R.end(), Log);
2std::        for_each(R.begin(), R.end(), Log);

Iterators as Sentinels

It is somewhat common for the sentinel to be an iterator. That was the case in our previous example - specifically, the iterator that was returned from R.end()

1std::ranges::for_each(
2  R.begin(), R.end(), Log 
3);

In this example, the starting iterator moves through our container as the algorithm progresses. At each step, the algorithm compares the current iterator to the sentinel.

The comparison is done by the == operator. After enough iterations, that operator will return true, as the advancing iterator will eventually point to the same memory address that was returned by R.end().

The option to define a range as an iterator-sentinel pair gives us slightly more flexibility right away. For example, we can run the algorithm only on a subrange, by modifying either of the arguments.

Below, we move the starting iterator one position forward, and move the sentinel iterator one position backward. This causes us to exclude the first and last objects from our algorithm execution:

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

14, 3, 8, -2,

Creating Custom Sentinels

The key point to realize is that our sentinel does not need to be an iterator. It just needs to be an object that can be compared to an iterator, using the == and != operators. As such, an object created from this type could be a sentinel:

1struct Sentinel {
2  bool operator==(SomeIteratorType I){
3    /* ... */
4  }
5};

Let's see a real example, using our proposal for a range that stops at the first negative value.

A sentinel that implements this requirement is going to receive some iterator type as an argument to a == operator. That operator will need to return true if the value that iterator is pointing at is less than 0

Below, we’ve created an initial version of this, which we’ll improve through subsequent examples:

1#include <iostream>
2#include <vector>
3
4struct Sentinel {
5  bool operator==(
6    std::vector<int>::const_iterator Iter
7  ) const {
8    return *Iter< 0;
9  }
10};
11
12int main(){
13  std::vector R{1, 4, 3, 8, -2, 5};
14  Sentinel S{};
15
16  for (
17    auto it = R.begin();
18    it != S;
19    ++it
20  ) {
21    std::cout << *it << ", ";
22  }
23}

11, 4, 3, 8,

What about the != operator?

Sentinels typically need to define both the == and != operators for any iterator type they need to support. But, as of C++20, if we don’t define the != operator, the compiler can rewrite any expressions that use it in terms of the == operator instead.

For example, an expression like A != B can be rewritten as !(A == B)

If we’re writing code to an earlier standard, we can’t benefit from expression rewriting, so we just explicitly define the != operators as usual.

We cover expression rewriting in detail in a dedicated lesson later in this course:

The Spaceship Operator and Expression Rewriting

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

With our sentinel now being defined by a custom type we created, we can implement logic that is as complex as we need for our use case.

Commonly, in addition to analyzing the value the iterator is pointing at, a sentinel will also need to know when the container it’s acting on naturally ends.

In this example, this means that if our input range didn’t contain any negative numbers, our algorithm stops running when there are no more objects in the container.

Improving our sentinel type to support that scenario could look something like this:

1#include <iostream>
2#include <vector>
3
4struct Sentinel {
5  bool operator==(
6    std::vector<int>::const_iterator Iter
7  ) const {
8    return Iter == ContainerEnd || *Iter < 0;
9  }
10
11  std::vector<int>::const_iterator ContainerEnd;
12};
13
14int main(){
15  std::vector R{1, 4, 3, 8, -2, 5};
16  Sentinel S{R.end()};
17
18  for (
19    auto it = R.begin();
20    it != S;
21    ++it
22  ) {
23    std::cout << *it << ", ";
24  }
25}

11, 4, 3, 8,

Template Sentinels

Sentinel types are typically implemented as templates. This is because they don’t necessarily know (or care) what specific type of iterator they’re going to be receiving as part of the == operator.

The sentinel in our previous example is only compatible with inputs that specifically have a type of std::vector<int>.

We can make it more flexible by converting it to a template type, calling our templated iterator type T:

1#include <iostream>
2#include <vector>
3
4template <typename T>
5struct Sentinel {
6  bool operator==(T Iter) const {
7    return Iter == ContainerEnd || *Iter < 0;
8  }
9
10  T ContainerEnd;
11};
12
13int main(){
14  std::vector R{1, 4, 3, 8, -2, 5};
15  Sentinel S{R.end()}; // Unchanged 
16
17  for (
18    auto it = R.begin();
19    it != S;
20    ++it
21  ) {
22    std::cout << *it << ", ";
23  }
24}

11, 4, 3, 8,

Note, that in this example, the main function didn’t need to be updated to specify the Sentinel template type.

This is because the template type T is the same type as the ContainerEnd variable within our struct.

As we’re providing a value for that member when we’re initializing our Sentinel, the compiler can use class template argument deduction (CTAD) to automatically infer what T is.

Using Sentinels with Algorithms

Now that we can define sentinels using any logic we require, we can go back to using algorithms rather than raw for loops:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
Sentinel Struct (Unchanged)|Show
5struct Sentinel {/*...*/};
14
15void Log(int x){ std::cout << x << ", "; }
16
17int main(){
18  std::vector R{1, 4, 3, 8, -2, 5};
19
20  std::ranges::for_each(
21    R.begin(), Sentinel{R.end()}, Log
22  );
23}

11, 4, 3, 8,

If our custom sentinel is going to see recurring use through a large code base, we can consider packaging it into a range-compatible container.

This container can then work exactly the way our project needs. The basic foundations involve defining the begin() method as normal, but having our end() method return our custom sentinel, rather than a simple iterator:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
Sentinel Struct (Unchanged)|Show
5struct Sentinel {/*...*/};
14
15template <typename T>
16class PositiveRange {
17public:
18  PositiveRange(
19    std::initializer_list<T> Numbers)
20    : Container{Numbers},
21      Sentinel{Container.end()} {}
22
23  auto begin() const{
24    return Container.begin();
25  }
26
27  auto end() const{ return Sentinel; }
28
29private:
30  std::vector<T> Container;
31  Sentinel<typename std::vector<
32    T>::const_iterator> Sentinel;
33};

This means consumers do not need to worry about constructing the sentinel - that’s all encapsulated way. They can treat our range as a simple, single object:

1void Log(int x){ std::cout << x << ", "; }
2
3int main(){
4  PositiveRange R{1, 4, 3, 8, -2, 5};
5  std::ranges::for_each(R, Log);
6}

11, 4, 3, 8,

Finding where Ranges End

A common requirement we will have for our programs is to know how large a range is, or where it ends. When that ending is defined by a sentinel, this can require some extra work.

If we just want to find the first object for which the sentinel returns true, the std::ranges::find() algorithm, which we cover in the next section, can help us.

However, this is rarely needed. When using almost any algorithm on our range, that algorithm naturally needs to determine where the range ends.

Running a second process to calculate the same thing again is a waste of resources. Fortunately, most of the range-based standard library algorithms return an object that includes an iterator pointing at where the sentinel was triggered.

For example, the std::ranges::for_each() algorithm returns an object with two fields:

• in - An iterator to where the sentinel was triggered
• fun - A reference to the function that we provided to the algorithm - such as the Log function from our earlier examples

Different algorithms may have slightly different return values. Still, it’s somewhat common that any algorithm that accepts an input range will have a return value that includes an iterator to where the range ended.

By accessing this property, typically by structured binding, we can uncover where the sentinel was triggered. We can then use that information for any follow-up actions we might need to do:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
Sentinel Struct (Unchanged)|Show
5struct Sentinel {/*...*/};
14
PositiveRange Class (Unchanged)|Show
15class PositiveRange {/*...*/};
35
36void Log(int x){ std::cout << x << ", "; }
37
38int main(){
39  PositiveRange R{1, 4, 3, 8, -2, 5};
40
41  auto [in, fun]{std::ranges::for_each(R, Log)};
42
43  std::cout << "\nObject at sentinel: " << *in;
44  std::cout << "\nSize of range: "
45    << std::distance(R.begin(), in);
46  std::cout << "\nLast in range: " << *(in - 1);
47}

11, 4, 3, 8,
2Object at sentinel: -2
3Size of range: 4
4Last in range: 8

Summary

In this lesson, we explored the concept and applications of sentinels in C++ ranges, demonstrating how they offer flexibility in defining range endpoints beyond traditional iterators. We also examined how to create custom sentinel types and use them with algorithms.

Main Points Covered

• Understanding that a range in C++ can be defined using a sentinel instead of an end iterator.
• Exploring the limitations of end iterators in ranges and how sentinels provide greater flexibility.
• Defining what a sentinel is and its role in terminating algorithms or loops.
• Demonstrating the use of iterators as sentinels in standard range-based algorithms.
• Creating custom sentinels to implement specific stopping conditions for ranges.
• Implementing template sentinels for greater flexibility with different iterator types.
• Using custom sentinels with standard library algorithms, such as std::ranges::for_each.
• Packaging custom sentinels into range-compatible containers for simplified use.
• Using structured binding to extract information from algorithms that utilize sentinels.
• Gaining an understanding of how to determine the size and endpoint of ranges defined by sentinels.

Next Lesson

Creating Custom Iterators using C++20 Concepts

A detailed guide to implementing a custom iterator type from scratch, using modern recommended techniques

ContinueView Course