Lesson 14: Ranges

Lesson 0014 — A Tour of C++, Chapter 14 (§14.1–§14.6)

Chapter 13's algorithms operate on sequences defined by {begin(), end()} iterator pairs. This chapter's thread: a range is a generalization of that C++98 idea — the standard library's concept-constrained algorithms in <ranges> (namespace ranges) accept ranges directly, and a range can be defined three ways: by a {begin,end} pair of iterators, by a {begin,n} pair (an iterator and a count), or by a {begin,pred} pair (an iterator and a predicate that ends the range — enabling infinite ranges and ranges generated "on the fly"). This is what lets us write sort(v) instead of sort(v.begin(),v.end()), expresses "something like 99% of the common uses of algorithms" more directly, and eliminates a class of silly errors such as sort(v1.begin(),v2.end()) — yes, such errors have been seen "in the wild."

14.1 Introduction

The standard library offers algorithms both constrained using concepts (Chapter 8) and unconstrained (for compatibility). The constrained (concept) versions are in <ranges>, in namespace ranges. Naturally, Stroustrup prefers the versions using concepts. A range can be defined by:

• A {begin,end} pair of iterators;
• A {begin,n} pair, where begin is an iterator and n is the number of elements;
• A {begin,pred} pair, where begin is an iterator and pred is a predicate — if pred(p) is true for the iterator p, we have reached the end of the range. This allows infinite ranges and ranges generated "on the fly" (§14.3).

The range concept is what allows us to say sort(v) rather than sort(v.begin(),v.end()) as we had to using the STL since 1994. We can do similarly for our own algorithms:

template<forward_range R> requires sortable<iterator_t<R>>
void my_sort(R& r) {                       // modern, concept-constrained version of my_sort
    return my_sort(r.begin(), end());      // use the 1994-style sort
}

In addition to the notational advantage, ranges offer some opportunities for optimization and eliminate a class of "silly errors," such as sort(v1.begin(),v2.end()) and sort(v.end(),v.begin()). Naturally, there are different kinds of ranges corresponding to the different kinds of iterators: input_range, forward_range, bidirectional_range, random_access_range, and contiguous_range are represented as concepts (§14.5).

14.2 Views

A view is a way of looking at a range. For example:

void user(forward_range auto& r) {
    filter_view v {r, [](int x) { return x % 2; }};   // view (only) odd numbers from r
    for (int x : v) cout << x << ' ';                // "odd numbers: "
}

When reading from a filter_view, we read from its range. If the value read matches the predicate, it is returned; otherwise, the filter_view tries again with the next element from the range. Many ranges are infinite, and we often only want a few values, so there are views for taking only a few values from a range:

void user(forward_range auto& r) {
    filter_view v {r, [](int x) { return x % 2; }};    // view (only) odd numbers in r
    take_view tv {v, 100};                             // view at most 100 elements from v
    for (int x : tv) cout << x << ' ';
}
// We can avoid naming the views by using them directly:
for (int x : take_view{filter_view{r, [](int x) { return x % 2; }}, 3}) cout << x << ' ';

Such nesting of views can quickly get a bit cryptic — hence pipelines (§14.4). The standard library offers many views, also known as range adaptors (in <ranges>; here v is a view, r is a range, p is a predicate, n is an integer):

A view offers an interface very similar to a range, so in most cases we can use a view wherever we can use a range and in the same way. The key difference: a view doesn't own its elements; it is not responsible for deleting the elements of its underlying range — that's the range's responsibility. On the other hand, a view must not outlive its range:

auto bad() {
    vector v = {1, 2, 3, 4};
    return filter_view{v, odd};   // v will be destroyed before the view
}

Views are supposed to be cheap to copy, so we pass them by value. And views work on user-defined types too — e.g., averaging temperatures by looking at just one field of a Reading struct via views::elements<1>:

struct Reading { int location {}; int temperature {}; int humidity {}; int air_pressure {}; /* ... */ };

int average_temp(vector<Reading> readings) {
    if (readings.size() == 0) throw No_readings{};
    double s = 0;
    for (int x : views::elements<1>(readings))   // look at just the temperatures
        s += x;
    return s / readings.size();
}

14.3 Generators

Often, a range needs to be generated on the fly. The standard library provides a few simple generators (aka factories) for that (in <ranges>; here v is a view, x is of the element type T, is is an istream):

The iota_views are useful for generating simple sequences:

for (int x : iota_view(42, 52))   // 42 43 44 45 46 47 48 49 50 51
    cout << x << ' ';

The istream_view gives a simple way of using istreams in range-for loops, and — like other views — composes with other views:

for (auto x : istream_view<complex<double>>(cin)) cout << x << '\n';

auto cplx = istream_view<complex<double>>(cin);
for (auto x : transform_view(cplx, [](auto z) { return z * z; })) cout << x << '\n';
// an input of 1 2 3 produces 1 4 9

14.4 Pipelines

For each standard-library view (§14.2), the standard library provides a function that produces a filter — an object usable as an argument to the filter operator |. For example, filter() yields a filter_view. This lets us combine filters in a sequence rather than as a set of nested function calls:

void user(forward_range auto& r) {
    auto odd = [](int x) { return x % 2; };
    for (int x : r | views::filter(odd) | views::take(3)) cout << x << ' ';
}

The pipeline style (using the Unix pipeline operator |) is widely regarded as more readable than nested function calls. The pipeline works left to right: in f|g, the result of f is passed to g, so r|f|g means (g_filter(f_filter(r))). The initial r has to be a range or a generator. These filter functions are in namespace ranges::views:

for (int x : r | views::filter([](int x) { return x % 2; }) | views::take(3)) cout << x << ' ';
// or, shorter:
using namespace views;
auto odd = [](int x) { return x % 2; };
for (int x : r | filter(odd) | take(3)) cout << x << ' ';

The implementation of views and pipelines involves some quite hair-raising template metaprogramming, so if you are concerned about performance, make sure to measure whether your implementation delivers what you need. If not, there is always a conventional workaround:

void user(forward_range auto& r) {
    int count = 0;
    for (int x : r)
        if (x % 2) { cout << x << ' '; if (++count == 3) return; }
}
// however, here the logic of what's going on is obscured.

14.5 Concepts Overview

The standard library offers many useful concepts, in three families:

• Concepts defining properties of types (§14.5.1)
• Concepts defining iterators (§14.5.2)
• Concepts defining ranges (§14.5.3)

14.5.1 Type Concepts

The concepts related to properties of types and the relations among types reflect the variety of types; they help simplify most templates. Core language concepts (in <concepts>; T and U are types):

Many algorithms should work with combinations of related types — e.g., expressions mixing ints and doubles. We use common_with to say whether such a mix is mathematically sound: if common_with<X,Y> is true, we can use common_type_t<X,Y> to compare an X with a Y by first converting both to common_type_t<X,Y>. To specify a common type for a pair of types, we specialize common_type_t used in the definition of common — e.g., using common_type_t<Bigint,long> = Bigint; — but fortunately we don't need such a specialization unless we want to use operations on mixes of types for which a library doesn't (yet) have suitable definitions. The comparison concepts are strongly influenced by [Stepanov, 2009]:

Curiously, there is no standard boolean concept — Stroustrup often needs one, so he shows a version: concept Boolean = requires(B x, B y) { { x = true }; ... };. When writing templates, we often need to classify types (object concepts in <concepts>):

The ideal for types is regular — a regular type works roughly like an int and simplifies much of our thinking about how to use a type (§8.2). The lack of a default == for classes means that most classes start out semiregular even though most could and should be regular.

Whenever we pass an operation as a constrained template argument, we need to specify how it can be called, and sometimes also what assumptions we make of their semantics (callable concepts in <concepts>):

A function f() is equality preserving if x==y implies f(x)==f(y). An invocable and a regular_invocable differ only semantically; we can't (currently) represent that in code, so the names simply express our intent. Similarly, a relation and an equivalence_relation differ only semantically — an equivalence relation is reflexive, symmetric, and transitive — and a relation and a strict_weak_order differ only semantically: strict weak ordering is what the standard library usually assumes for comparisons, such as <.

14.5.2 Iterator Concepts

The traditional standard algorithms access their data through iterators, so we need concepts to classify properties of iterator types (in <iterators>):

The different categories of iterators are used to select the best algorithm for a given set of arguments (§8.2.2, §16.4.1). For an example of an input_iterator, see §13.3.1.

The basic idea of a sentinel: we can iterate over a range starting at an iterator until the predicate becomes true for an element. That way, an iterator p and a sentinel s define a range [p : s(*p)). For example, we could define a predicate for a sentinel for traversing a C-style string using a pointer as the iterator. This requires some boilerplate because the idea is to present the predicate as something that can't be confused with an ordinary iterator but that you can compare the iterator used to traverse the range to:

template<class Iter> class Sentinel {
public:
    Sentinel(int ee) : end(ee) { }
    Sentinel() : end(0) {}   // Concept sentinel_for requires a default constructor
    friend bool operator==(const Iter& p, Sentinel s) { return (*p == s.end); }
    friend bool operator!=(const Iter& p, Sentinel s) { return !(p == s); }
private:
    iter_value_t<const char*> end;   // the sentinel value
};
// The friend declarator defines == and != for comparing an iterator to a sentinel within the class scope.

static_assert(sentinel_for<Sentinel<const char*>, const char*>);   // check the Sentinel for C-style strings

const char aa[] = "Hello, World!\nBye for now\n";
ranges::for_each(aa, Sentinel<const char*>('\n'), [](const char x) { cout << x; });
// Yes, this really writes Hello, World! not followed by a newline.

14.5.3 Range Concepts

The range concepts define the properties of ranges (in <ranges>):

There are a few more concepts in <ranges>, but this set is a good start. The primary use of these concepts is to enable overloading of implementations based on type properties of their inputs (§8.2.2).

14.6 Advice

Here is a summary of the guidance from this chapter. All 9 items, with the section where each is introduced. The C++ Core Guidelines link each item to its recommended practice.

Retrieval Quiz

Notes

Primary source: Stroustrup, B. (2022). A Tour of C++, 3rd ed., Chapter 14: "Ranges." Addison-Wesley.
Reference: Chapter 1–12 Quick Reference & Glossary — keep it beside you while you study.
Recommended supplement: cppreference on ranges library, views (range adaptors), and concepts library.

Questions? Ask your agent — your teacher — about anything unclear: when a view dangles, why common_with matters for mixed-type arithmetic, or how a sentinel differs from an iterator. Follow-ups are expected, not optional.

Chapters

1. Lesson 1: The Basics (Ch. 1)
2. Lesson 2: User-Defined Types (Ch. 2)
3. Lesson 3: Separate Compilation (Ch. 3)
4. Lesson 4: Error Handling (Ch. 4)
5. Lesson 5: Classes (Ch. 5)
6. Lesson 6: Essential Operations (Ch. 6)
7. Lesson 7: Templates (Ch. 7)
8. Lesson 8: Concepts and Generic Programming (Ch. 8)
9. Lesson 9: Library Overview (Ch. 9)
10. Lesson 10: Strings and Regular Expressions (Ch. 10)
11. Lesson 11: Input and Output (Ch. 11)
12. Lesson 12: Containers (Ch. 12)
13. Lesson 13: Algorithms (Ch. 13)
14. Lesson 14: Ranges (Ch. 14 — this lesson)
15. Lesson 15: Pointers and Containers (Ch. 15)
16. Lesson 16: Utilities (Ch. 16)
17. Lesson 17: Numerics (Ch. 17)
18. Lesson 18: Concurrency (Ch. 18)
19. Lesson 19: History and Compatibility (Ch. 19)