As you may have heard by now, Ranges got merged and will be part of C++20. This is huge news and represents probably the biggest shift the Standard Library has seen since it was first standardized way back in 1998.

This has been a long time coming. Personally, I’ve been working toward this since at least November 2013, when I opined, “In my opinion, it’s time for a range library for the modern world,” in a blog post on input ranges. Since then, I’ve been busy building that modern range library and nailing down its specification with the help of some very talented people.

Future blog posts will discuss how we got here and the gritty details of how the old stuff and the new stuff play together (we’re C++ programmers, we love gritty details), but this post is strictly about the what.

What is coming in C++20?

All of the Ranges TS — and then some — will ship as part of C++20. Here’s a handy table of all the major features that will be shipping as part of the next standard:

Below, I say a few words about each. But first I wanted to revisit an old coding challenge and recast its solution in terms of standard C++20.

Pythagorian Triples, Revisited

Some years ago now, I wrote a blog post about how to use ranges to generate an infinite list of Pythagorean triples: 3-tuples of integers where the sum of the squares of the first two equals the square of the third.

Below is the complete solution as it will look in standard C++20. I take the solution apart after the break.

// A sample standard C++20 program that prints
// the first N Pythagorean triples.
#include <iostream>
#include <optional>
#include <ranges>   // New header!

using namespace std;

// maybe_view defines a view over zero or one
// objects.
template<Semiregular T>
struct maybe_view : view_interface<maybe_view<T>> {
  maybe_view() = default;
  maybe_view(T t) : data_(std::move(t)) {
  }
  T const *begin() const noexcept {
    return data_ ? &*data_ : nullptr;
  }
  T const *end() const noexcept {
    return data_ ? &*data_ + 1 : nullptr;
  }
private:
  optional<T> data_{};
};

// "for_each" creates a new view by applying a
// transformation to each element in an input
// range, and flattening the resulting range of
// ranges.
// (This uses one syntax for constrained lambdas
// in C++20.)
inline constexpr auto for_each =
  []<Range R,
     Iterator I = iterator_t<R>,
     IndirectUnaryInvocable<I> Fun>(R&& r, Fun fun)
        requires Range<indirect_result_t<Fun, I>> {
      return std::forward<R>(r)
        | view::transform(std::move(fun))
        | view::join;
  };

// "yield_if" takes a bool and a value and
// returns a view of zero or one elements.
inline constexpr auto yield_if =
  []<Semiregular T>(bool b, T x) {
    return b ? maybe_view{std::move(x)}
             : maybe_view<T>{};
  };

int main() {
  // Define an infinite range of all the
  // Pythagorean triples:
  using view::iota;
  auto triples =
    for_each(iota(1), [](int z) {
      return for_each(iota(1, z+1), [=](int x) {
        return for_each(iota(x, z+1), [=](int y) {
          return yield_if(x*x + y*y == z*z,
            make_tuple(x, y, z));
        });
      });
    });

    // Display the first 10 triples
    for(auto triple : triples | view::take(10)) {
      cout << '('
           << get<0>(triple) << ','
           << get<1>(triple) << ','
           << get<2>(triple) << ')' << '\n';
  }
}

The above program prints the following:

(3,4,5)
(6,8,10)
(5,12,13)
(9,12,15)
(8,15,17)
(12,16,20)
(7,24,25)
(15,20,25)
(10,24,26)
(20,21,29)

This program is (lazily) generating an infinite list of Pythagorean triples, taking the first 10, and printing them out. Below is a quick rundown on how it works. Along the way, I’ll point out the parts of that solution that will be standard starting in C++20.

main()

First, let’s look at main, which creates the infinite list of triples and prints out the first 10. It makes repeated use of for_each to define the infinite list. A use like this:

auto x = for_each( some-range, [](auto elem) {
  return some-view;
} );

means: For every element in some-range, call the lambda. Lazily collect all the views thus generated and flatten them into a new view. If the lambda were to return view::single(elem), for instance — which returns a view of exactly one element — then the above is a no-op: first carve some-range into N subranges of 1-element each, then flatten them all back into a single range.

Armed with that knowledge, we can make sense of the triply-nested invocations of for_each:

for_each(iota(1), [](int z) {
  return for_each(iota(1, z+1), [=](int x) {
    return for_each(iota(x, z+1), [=](int y) {

This code is generating every combination of integers x, y, and z in some order (selecting the bounds so that x and y are never larger than z, because those can’t be Pythagorean triples). At each level we create structure: we start with a single range (iota(1), described below), and then get a range of ranges where each inner range corresponds to all the combinations that share a value for z. Those inner ranges are themselves further decomposed into subranges, each of which represents all the combinations that share a value of x. And so on.

The innermost lambda has x, y, and z and can decide whether to emit the triple or not:

return yield_if(x*x + y*y == z*z,
    make_tuple(x, y, z));

yield_if takes a Boolean (have we found a Pythagorean triple?) and the triple, and either emits an empty range or a 1-element range containing the triple. That set of ranges then gets flattened, flattened, and flattened again into the infinite list of the Pythagorean triples.

We then pipe that infinite list to view::take(10), which truncates the infinite list to the first 10 elements. Then we iterate over those elements with an ordinary range-based for loop and print out the results. Phwew!

Now that we have a high-level understanding of what this program is doing, we can take a closer look at the individual components.

view::iota

This is a very simple view. It takes either one or two objects of Incrementable type. It builds a range out of them, using the second argument as the upper bound of a half-closed (i.e., exclusive) range, taking the upper bound to be an unreachable sentinel if none is specified (i.e., the range is infinite). Here we use it to build a range of integers, but any incrementable types will do, including iterators.

The name “iota” comes from the std::iota numeric algorithm, which itself has an interesting naming history.

for_each

The range-v3 library comes with view::for_each and yield_if, but those haven’t been proposed yet. But view::for_each is a trivial composition of view::transform and view::join which will be part of C++20, so we can implement it as follows:

inline constexpr auto for_each =
  []<Range R,
     Iterator I = iterator_t<R>,
     IndirectUnaryInvocable<I> Fun>(R&& r, Fun fun)
       requires Range<indirect_result_t<Fun, I>> {
     return std::forward<R>(r)
       | view::transform(std::move(fun))
       | view::join;
  };

This declares an object for_each that is a C++20 constrained generic lambda with explicitly specified template parameters. “Range” and “IndirectUnaryInvocable” are standard concepts in C++20 that live in namespace std. They constrain the arguments r and fun of the lambda to be a range (duh) and a function that is callable with the values of the range. We then further constrain the lambda with a trailing requires clause, ensuring that the function’s return type must be a Range as well. indirect_result_t will also be standard in C++20. It answers the question: if I call this function with the result of dereferencing this iterator, what type do I get back?

The lambda first lazily transforms the range r by piping it to view::transform, moving fun in. view:: is a namespace within std:: in which all the new lazy range adaptors live. Since fun returns a Range (we required that!), the result of the transformation is a range of ranges. We then pipe that to view::join to flatten the ranges into one big range.

The actual code, lines 6-8, kind of gets lost in the sea of constraints, which are not strictly necessary to use the library; I’m being a bit pedantic for didactic purposes here, so please don’t let that trip you up.

I also could have very easily written for_each as a vanilla function template instead of making it an object initialized with a constrained generic lambda. I opted for an object in large part because I wanted to demonstrate how to use concepts with lambdas in C++20. Function objects have other nice properties, besides.

yield_if

yield_if is simpler conceptually, but it requires a little legwork on our part. It is a function that takes a Boolean and an object, and it returns either an empty range (if the Boolean is false), or a range of length one containing the object. For that, we need to write our own view type, called maybe_view, since there isn’t one in C++20. (Not yet, at least. There is a proposal.)

Writing views is made a little simpler with the help of std::view_interface, which generates some of the boilerplate from begin() and end() functions that you provide. view_interface provides some handy members like .size(), .operator[], .front(), and .back().

maybe_view is reproduced below. Notice how it is trivially implemented in terms of std::optional and std::view_interface.

template<Semiregular T>
struct maybe_view : view_interface<maybe_view<T>> {
  maybe_view() = default;
  maybe_view(T t) : data_(std::move(t)) {
  }
  T const *begin() const noexcept {
    return data_ ? &*data_ : nullptr;
  }
  T const *end() const noexcept {
    return data_ ? &*data_ + 1 : nullptr;
  }
private:
  optional<T> data_{};
};

Once we have maybe_view, the implementation of yield_if is also trivial. It returns either an empty maybe_view, or one containing a single element, depending on the Boolean argument.

inline constexpr auto yield_if =
  []<Semiregular T>(bool b, T x) {
    return b ? maybe_view{std::move(x)}
             : maybe_view<T>{};
  };

Note: maybe_view owns its elements. It is generally a violation of the View concept’s semantic requirements for a view to own its elements because it gives the type’s copy and move operations O(N) behavior. However, in this case — where N is either 0 or 1 — we just squeak by.

And that’s it. This program demonstrates how to use view::iota, view::transform, view::join, view_interface, and some standard concepts to implement a very useful bit of library functionality, and then uses it to construct an infinite list with some interesting properties. If you have used list comprehensions in Python or Haskell, this should feel pretty natural.

But these features are just a tiny slice of the range support in C++20. Below, I go through each row of the table at the top of the post, and give an example of each.

Fundamental Concepts

The C++20 Standard Library is getting a host of generally useful concept definitions that users can use in their own code to constrain their templates and to define higher-level concepts that are meaningful for them. These all live in the new <concepts> header, and they include things like Same<A, B>, ConvertibleTo<From, To>, Constructible<T, Args...>, and Regular<T>.

Say for instance that you have a thread pool class with an enqueue member function that takes something that is callable with no arguments. Today, you would write it like this:

struct ThreadPool {
  template <class Fun>
  void enqueue( Fun fun );
};

Users reading this code might wonder: what are the requirements on the type Fun? We can enforce the requirement in code using C++20’s std::Invocable concept, along with the recently-added support for abreviated function syntax:

#include <concepts>

struct ThreadPool {
  void enqueue( std::Invocable auto fun );
};

This states that fun has to be invocable with no arguments. We didn’t even have to type template <class ...>! (std::Invocable<std::error_code &> auto fun would declare a function that must be callable with a reference to a std::error_code, to take another example.)

Iterator and Range Concepts

A large part of the Standard Library concerns itself with containers, iterators, and algorithms, so it makes sense that the conceptual vocabulary would be especially rich in this area. Look for useful concept definitions like Sentinel<S, I>, InputIterator<I>, and RandomAccessIterator<I> in the <iterator> header, in addition to useful compositions like IndirectRelation<R, I1, I2> which test that R imposes a relation on the result of dereferencing iterators I1 and I2.

Say for example that you have a custom container type in your codebase called SmallVector that, like std::vector, can be initialized by passing it two iterators denoting a range. We can write this with concepts from <iterator> and <concepts> as follows:

template <std::Semiregular T>
struct SmallVector {
  template <std::InputIterator I>
    requires std::Same<T, std::iter_value_t<I>>
  SmallVector( I i, std::Sentinel<I> auto s ) {
    // ...push back all elements in [i,s)
  }
  // ...

Likewise, this type can get a constructor that takes a range directly using concepts defined in the new <ranges> header:

  // ... as before
  template <std::InputRange R>
    requires std::Same<T, std::range_value_t<R>>
  explicit SmallVector( R && r )
    : SmallVector(std::ranges::begin(r),
                  std::ranges::end(r)) {
  }
};

Note: range_value_t<R> hasn’t been formally accepted yet. It is an alias for iter_value_t<iterator_t<R>>.

New Convenience Iterator Traits

In C++17, if you want to know the value type of an iterator I, you have to type typename std::iterator_traits<I>::value_type. That is a mouthful. In C++20, that is vastly shortened to std::iter_value_t<I>. Here are the newer, shorter type aliases and what they mean:

There is no iter_category_t<I> to get an iterator’s tag type because tag dispatching is now passé. Now that you can dispatch on iterator concept using language support, there is no need for tags.

Safe Range Access Functions

What is wrong with std::begin and std::end? Surprise! they are not memory safe. Consider what this code does:

extern std::vector<int> get_data();
auto it = std::begin(get_data());
int i = *it; // BOOM

std::begin has two overloads for const and non-const lvalues. Trouble is, rvalues bind to const lvalue references, leading to the dangling iterator it above. If we had instead called std::ranges::begin, the code would not have compiled.

ranges::begin has other niceties besides. It does the ADL two-step for you saving you from remembering to type using std::begin; in generic code. In other words, it dispatches to a begin() free function found by ADL, but only if it returns an Iterator. That’s an extra bit of sanity-checking that you won’t get from std::begin.

Basically, prefer ranges::begin in all new code in C++20 and beyond. It’s more better.

Prvalue and Proxy Iterator Support

The C++98 iterator categories are fairly restrictive. If your iterator returns a temporary (i.e., a prvalue) from its operator*, then the strongest iterator category it could model was InputIterator. ForwardIterator required operator* to return by reference. That meant that a trivial iterator that returns monotonically increasing integers by value, for example, cannot satisfy ForwardIterator. Shame, because that’s a useful iterator! More generally, any iterator that computes values on-demand could not model ForwardIterator. That’s :’-(.

It also means that iterators that return proxies — types that act like references — cannot be ForwardIterators. Hence, whether it was a good idea or not, std::vector<bool> is not a real container since its iterators return proxies.

The new C++20 iterator concepts solve both of this problems with the help of std::ranges::iter_swap (a constrained version of std::iter_swap), and the new std::ranges::iter_move. Use ranges::iter_swap(i, j) to swap the values referred to by i and j. And use the following:

iter_value_t<I> tmp = ranges::iter_move(i);

… to move an element at position i out of sequence and into the temporary object tmp.

Authors of proxy iterator types can hook these two customization points to make their iterators play nicely with the constrained algorithms in the std::ranges namespace (see below).

The new iter_rvalue_reference_t<I> type alias mentioned above names the return type of ranges::iter_move(i).

Contiguous Iterator Support

In Stepanov’s STL, RandomAccessIterator is the strongest iterator category. But whether elements are contiguous in memory is a useful piece of information, and there exist algorithms that can take advantage of that information to become more efficient. Stepanov was aware of that but felt that raw pointers were the only interesting model of contiguous iterators, so he didn’t need to add a new category. He would have been appalled at the library vendors who ship std::vector implementations with wrapped debug iterators.

TL;DR, we are now defining an extra category that subsumes (refines) RandomAccessIterator called ContiguousIterator. A type must opt-in to contiguity by defining a nested type named iterator_concept (note: not iterator_category) that is an alias for the new std::contiguous_iterator_tag tag type. Or you could specialize std::iterator_traits for your type and specify iterator_concept there.

There is a whole blog post coming about iterator_category, iterator_concept, and how to write an iterator type that conforms both to the old iterator concepts and the new, with different strengths in each. It’s a brave new world of back-compat considerations.

Constrained Algorithms

Ever tried to pass a std::list‘s iterator to std::sort? Or any other combination of nonesense? When you accidentally fail to meet an algorithm’s (unstated) type requirements today, your compiler will inform you in the most obscure and voluminous way possible, spewing errors that appear to come from within the guts of your STL implementation.

Concepts are designed to help with this. For instance, look at this code that is using the cmcstl2 reference implementation (which puts std::ranges in std::experimental::ranges for now):

#include <list>
#include <stl2/algorithm.hpp>
using ranges = std::experimental::ranges;

int main() {
  std::list<int> l {82,3,7,2,5,8,3,0,4,23,89};
  ranges::sort( l.begin(), l.end() );
}

Rather than an error deep in the guts of ranges::sort, the error message points right to the line in main that failed to meet the constraints of the sort template. “error: no matching call for ranges::sort(list<int>::iterator, list<int>::iterator)“, followed by a message that shows the prototype that failed to match and an explanation that the constraints within RandomAccessIterator we not satisfied. You can see the full error here.

Much can be done to make the error more user-friendly, but it’s already a vast improvement over the status quo.

Range Algorithms

This one is fairly obvious. It’s been 20 years since the STL was standardized, and all I want to do is pass a vector to sort. Is that too much to ask? Nope. With C++20, you will finally be able to do this:

std::vector< int > v =  // ...
std::ranges::sort( v ); // Hurray!

Constrained Function Objects

Have you ever used std::less<>, the “diamond” specializations of the comparison function objects that were added in C++14? These let you compare things without having to say up front what type you’re comparing or forcing conversions. These exist in the std::ranges namespace too, but you don’t have to type <> because they are not templates. Also, they have constrained function call operators. So less, greater, less_equal, and greater_equal are all constrained with StrictTotallyOrderedWith, for instance.

These types are particularly handy when defining APIs that accept a user-specified relation, but default the relation to operator< or operator==. For instance:

template <class T, Relation<T, T> R = ranges::less>
T max( T a, T b, R r = {} ) {
  return r( a, b ) ? b : a;
}

This function has the nice property that if the user specifies a relation, it will be used and the constraints guarantee that R is a Relation over type T. If the user doesn’t specify a relation, then the constraints require that T satisfies StrictTotallyOrderedWith itself. That is implicit in the fact that R defaults to ranges::less, and ranges::less::operator() is constrained with StrictTotallyOrderedWith.

Generalized Callables

In C++17, the Standard Library got a handy function: std::invoke. It lets you call any “Callable” thing with some arguments, where “Callable” includes ordinary function-like things in addition to pointers to members. However, the standard algorithms were not respecified to use std::invoke, which meant that code like the following failed to compile:

struct Wizard {
  void frobnicate();
};

int main() {
  std::vector<Wizard> vw { /*...*/ };
  std::for_each( vw.begin(), vw.end(),
                 &Wizard::frobnicate ); // Nope!
}

std::for_each is expecting something callable like fun(t), not std::invoke(fun, t).

The new algorithms in the std::ranges namespace are required to use std::invoke, so if the above code is changed to use std::ranges::for_each, it will work as written.

Projections

Ever wanted to sort a range of things by some property of those things? Maybe sort a vector of Employees by their ids? Or last name? Or maybe you want to seach an array of points for one where the magnitude is equal to a certain value. For those things, projections are very handy. A projection is a unary transformation function passed to an algorithm that gets applied to each element before the algorithm operates on the element.

To take the example of sorting a vector of Employees by id, you can use a projection argument to std::ranges::sort as follows:

struct Employee {
  int Id;
  std::string Name;
  Currency Salary;
};

int main() {
  using namespace std;
  vector<Employee> employees { /*...*/ };
  ranges::sort( employees, ranges::less{},
                &Employee::Id );
}

The third argument to std::ranges::sort is the projection. Notice that we used a generalized callable for it, from the previous section. This sort command sorts the Employees by the Id field.

Or for the example of searching an array of points for one where the magnitude is equal to a certain value, you would do the following:

using namespace std;
array< Point > points { /*...*/ };
auto it = ranges::find( points, value, [](auto p) {
  return sqrt(p.x*p.x + p.y*p.y);
} );

Here we are using a projection to compute a property of each element and operating on the computed property.

Once you get the hang of projections, you’ll find they have many uses.

Range Utilities

The part of the standard library shipping in the <ranges> header has a lot of goodies. Besides an initial set of lazy range adaptors (described below), it has some handy, general-purpose utilities.

view_interface

As in the Pythagorean triples example above, your custom view types can inhert from view_interface to get a host of useful member functions, like .front(), .back(), .empty(), .size(), .operator[], and even an explicit conversion to bool so that view types can be used in if statements:

// Boolean conversion operator comes from view_interface:
if ( auto evens = vec | view::filter(is_even) ) {
  // yup, we have some evens. Do something.
}

subrange

std::ranges::subrange<I, S> is probably the most handy of the range utilities. It is an iterator/sentinel pair that models the View concept. You can use it to bundle together two iterators, or an iterator and a sentinel, for when you want to return a range or call an API that expects a range.

It also has deduction guides that make it quite painless to use. Consider the following code:

auto [b,e] = subrange{vec};

This code is equivalent in effect to:

auto b = ranges::begin(vec);
auto e = ranges::end(vec);

The expression subrange{vec} deduces the iterator and sentinel template parameters from the range vec, and since subrange is tuple-like, we can unpack the iterator/sentinel pair using structured bindings.

ref_view

Although not officially merged yet, C++20 will have a std::ranges::ref_view<R> which, like std::reference_wrapper is, well, a wrapper around a reference. In the case of ref_view, it is a reference to a range. It turns an lvalue container like std::vector<int>& into a View of the same elements that is cheap to copy: it simply wraps a pointer to the vector.

Range Generators

Now we get to the really fun stuff. The <ranges> header has a couple of ways to generate new ranges of values, including std::view::iota that we saw above. Here is how to use them, and what they mean:

Range Adaptors

This is the really, really fun stuff. The true power of ranges lies in the ability to create pipelines that transform ranges on the fly. The range-v3 library has dozens of useful range adaptors. C++20 will only be getting a handful, but expect the set to grow over time.

These adaptors can be chained, so for instance, you can do the following:

using namespace std;
for ( auto && e : r | view::filter(pred)
                    | view::transform(fn) ) {
  // Iterate over filtered, transformed range
}

Of course, you can also use range adaptor pipelines as arguments to the range-based algorithms in std::ranges:

using namespace std;
// Insert a filtered, transformed range into
// the back of container `v`.
ranges::copy( r | view::filter(pred)
                | view::transform(fn),
              back_inserter(v) );

Lazily adapting ranges is a powerful way to structure your programs. If you want a demonstration of how far this programming style can take you, see my CppCon keynote on ranges from 2015, or just skim the code of the calendar application I describe there, and note the lack of loops, branches, and overt state manipulation. ‘Nuf said.

Future Directions

Clearly, C++20 is getting a lot of new functionality in support of ranges. Getting here has taken a long time, mostly because nobody had ever built a fully general, industrial strength, generic library using the C++20 language support for concepts before. But now we are over that hump. All the foundational pieces are in place, and we’ve acrued a lot of knowledge in the process. Expect the feature set to expand rapidly post-C++20. There are already papers in flight.

Things currently in the works include:

• Constructors for the standard containers that accept ranges,
• A take_while range adaptor that accepts a predicate and returns a view of the first N elements for which the predicate evaluates to true,
• A drop range adaptor that returns a view after dropping the first N elements of the input range,
• A drop_while view that drops elements from an input range that satisfy a predicate.
• An istream_view that is parameterized on a type and that reads elements of that type from a standard istream,
• A zip view that takes N ranges and produces a view where the elements are N-tuples of the elements of the input ranges, and
• A zip_with view that takes N ranges and a N-ary function, and produces a view where the elements are the result of calling the function with the elements of the input ranges.

And there’s more, lots more in range-v3 that has proven useful and will eventually be proposed by myself or some other interested range-r. Things I would especially like to see:

• An iterator façade class template like range-v3’s basic_iterator;
• A view façade class template like range-v3’s view_facade;
• Range-ified versions of the numeric algorithms (e.g., accumulate, partial_sum, inner_product);
• More range generators and adaptors, like view::chunk, view::concat, view::group_by, view::cycle, view::slice, view::stride, view::generate[_n], view::repeat[_n], a view::join that takes a delimiter, view::intersperse, view::unique, and view::cartesian_product, to name the more important ones; and
• A “complete” set of actions to go along with the views. Actions, like the adaptors in the view:: namespace, operate on ranges and compose into pipelines, but actions act eagerly on whole containers, and they are potentially mutating. (The views are non-mutating.)

With actions, it should be possible to do:

v = move(v) | action::sort | action::unique;

…to sort a vector and remove all duplicate elements.

And I haven’t even mentioned asynchronous ranges yet. But that’s a whole other blog post. 🙂

Summary

C++20 is rapidly approaching, and now that the Ranges work has been officially merged into the working draft, I have been hearing from Standard Library vendors who are starting to think about implementing all of this. Only GCC is in a position to ship the ranges support any time soon, since it is the only compiler currently shipping with support for concepts. But clang has a concepts branch which is already usable, so there is hope for concepts — and ranges — in clang trunk sometime in the not-too-distant future. And Microsoft has publicly committed to supporting all of C++20 including concepts and ranges, and the conformance of the Microsoft compiler has been rapidly improving, recently gaining the ability to compile range-v3. So things are looking good there, too.

It’s a stRANGE new world. Thanks for reading.

"\e"