Standard Ranges

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:

Feature Example
Fundamental concepts std::Copyable<T>
Iterator and range concepts std::InputIterator<I>
New convenience iterator traits std::iter_value_t<I>
Safer range access functions std::ranges::begin(rng)
Proxy iterator support std::iter_value_t<I> tmp =
    std::ranges::iter_move(i);
Contiguous iterator support std::ContiguousIterator<I>
Constrained algorithms std::ranges::sort(v.begin(), v.end());
Range algorithms std::ranges::sort(v);
Constrained function objects std::ranges::less
Generalized callables std::ranges::for_each(v, &T::frobnicate);
Projections std::ranges::sort(employees, less{},
    &Employee::id);
Range utilities struct my_view : std::view_interface<my_view> {
Range generators auto indices = std::view::iota(0u, v.size());
Range adaptors for (auto x : v | std::view::filter(pred)) {

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:

New iterator type alias Old equivalent
iter_difference_t<I> typename iterator_traits<I>::difference_type
iter_value_t<I> typename iterator_traits<I>::value_type
iter_reference_t<I> typename iterator_traits<I>::reference
iter_rvalue_reference<I> no equivalent, see below

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:

Syntax Semantics
view::iota(i) Given the incrementable object i, generates an infinite range of values like [i,i+1,i+2,i+3,...).
view::iota(i,j) Given the incrementable object i and some other object j that is comparable to i (but not necessarily the same type), generates a range of values like [i,i+1,i+2,i+3,...,j-1]. Note that the upper bound (j) is excluded, which makes this form usable with iterator/sentinel pairs. It can also be used to generate the indices of a range with view::iota(0u, ranges::size(rng)).
view::single(x) Construct a one-element view of the value x; that is, [x].
view::empty<T> A zero-element view of elements of type T.
view::counted(it, n) Given an iterator it and a count n, constructs a finite range of n elements starting at the element denoted by it.

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.

Syntax Semantics
r | view::all Create a View over all the elements in Range r. Perhaps r is already a View. If not, turn it into one with ref_view if possible, or subrange failing that. Rvalue containers are not “viewable,” and so code like std::vector<int>{} | view::all will fail to compile.
r | view::filter(pred) Given a viewable range r and a predicate pred, return a View that consists of all the elements e for which invoke(pred, e) returns true.
r | view::transform(fn) Given a viewable range r and a function fn, return a View that consists of all the elements of r transformed with fn.
r | view::reverse Given a viewable range r, return a View that iterates r‘s values in reverse order.
r | view::take(n) Given a viewable range r, return a View containing the first n elements of r, or all the elements of r if r has fewer than n elements.
r | view::join Given a viewable range of ranges, flatten all the ranges into a single range.
r | view::split(r2) Given a viewable range r and a pattern range r2, return a View of Views where the inner ranges are delimited by r2. Alternativly, the delimiter can be a single value v which is treated as if it were view::single(v).
r | view::common Given a viewable range r, return a View for which the begin and end iterators of the range have the same type. (Some ranges use a sentinel for the end position.) This range adaptor is useful primarily as a means of interfacing with older code (like the std:: algorithms) that expects begin and end to have the same type.

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"

51 Replies to “Standard Ranges”

  1. Hello Eric Niebler. Great and huge amount of work. Looking forward to these improvements, all of them very welcome, but the proxy support and improved safety and error messages really stand out.

    I have a question:

    If there is view_interface, why do we need iterator_facade or view_facade? Not sure, but please forgive my total ignorance, I did not study the library fully just yet.

    • view_interface still requires you to author an iterator type. Writing a standard-conforming iterator is hard and requires lots of boilerplate and some esoteric knowledge in the case of proxy iterators. An iterator facade and a view facade would ease that burden.

  2. It’s not the first time I’ve said it and it won’t be the last: the work that you and Casey and others have done on this is remarkable – thanks so much.

    I’m so impressed by how much useful stuff has been included for C++20. Thanks to everyone that has made this possible. And anticipatory thanks to all those who’ll be involved in implementing it :).

  3. It’s very exciting to finally get usable STL interface 🙂
    Looks like link to godbolt is broken? (From the end of “Constrained Algorithms” section).

  4. “Users reading this code might wonder: what are the requirements on the type Fun?”

    Nope, thats a lame excuse. Before I enter the beautiful State of Wonder, I take the docs and read them. And then I wonder: Where are the docs? Ah, the author thinks that code = docs.
    Maybe all the new features are very useful, but I have the feeling, that they are the cheap argument to save writing documentation.

    • Clearly you are a person who has never used an API incorrectly, either out of error or ignorance. The problem with unconstrained code is that when you do, either it fails at compile time with mysterious errors that take time to triage, or else it actually compiles and silently does the wrong thing. That is why expressing your requirements in code is important. Docs do not sanity-check your code for you.

      • That is not what I said. I know about checking in code and use it. What I said is: Writing these requirements makes good docs superfluous, more and more code writers think, they tend to generate them instead of writing. That’s my impression.
        In other words: Docs are required to use a library on the right way, concepts and assert() are a technical help to do that, but not more.
        I suppose you see it the same way, but you ran into a trap with your sentence.

        • For what’s it worth, I 100% agree with you.

          I’m thinking this is an amazing piece of work. But I can’t make heads nor tails of it. I’m not complaining about the concept checking. The problem is that that is all it has.

          Unless this changes, it will one more of those things that everyone says is great but that no one actually uses.

  5. Hi.

    That’s a really amazing work!

    I see you mention view::common but looks like there is no such a thing in the current range-v3 repo. It’s not implemented yet or am I missing something?

    Thanks!

  6. Eric, another question. Following your description of ranges::begin and the definition of the Range concept, I thought vector<int>&& should not satisfy Range. However, a test with CMCSTL2 showed Range<vector<int>&&> returned true. What did I miss?

    • The Range concept is defined such that Range<T> is the same as Range<T&>. That was done because it should be possible to pass vector<int>&& to std::ranges::count for instance. It would be perfectly safe. From with the body of the count algorithm, begin and end are called on the vector as an lvalue.

  7. Awesome,

    Knee jerk reaction though. I’m a C++ programmer but really don’t like “gritty details”. I learned to live with them but they still make me cringe.

  8. Thank you for all your efforts. One question, we do have constrained ranges, views, algorithms etc. But I do not see that constrained containers among things that are planned. Are they considered less important or unnessecary?

  9. I commented on post years ago that this example with triplets is bad(because fancy lazy solution has horrible algorithmic complexity) and now I also must say that it may be a bit too hard for beginners, so maybe you should have lead with simpler stuff…

    But anyway I am happy to stop writing .begin and .end, I am a bit skeptical if I will change the way I code when I adopt ranges(I doubt I will encounter many real world problems that benefit from fancy ranges features like laziness or generators) but I would be happy to be proven wrong.

    Projections are awesome, for sure I will use those.

    • C++ will likely get a container called flat_map. The function called map in functional programming languages if called transform in C++. Trying to make C++ consistent with other languages at this point is beyond hopeless. That ship sailed 20 years ago.

  10. This stuff is unreadable. Come on, seriously?

    T const end() const noexcept {
    return data_ ? &data_ + 1 : nullptr;
    }

    C++ is no longer inviting.

    Python is so easy.

      • I apologize for my fellow Python evangelist’s dismissal. As a Cython hacker, I’m both accustomed to these shenanigans, and very very excited for the range library to be included in C++20.

         

        I took a pass at simplifying the code, and wondered why maybe_view was even implemented for this example. Can you comment on how your yield_if differs from the following?

        inline constexpr auto yield_if =
           [](bool b, T x) {
            return b ? view::single(x)
                     : view::empty;
        };
        
  11. Hey Eric, I see a lot of people saying the code is hard to read. I think you should consider changing the theme, nothing in the codes fits on a line because it is so narrow. Or maybe make the code area scrollable ?

  12. I’m nt sure I understand the point of the abstraction. Can we please discuss a REAL world (non-toy) example of this being used? Also, can we see a comparison of
    how you would implement this without ranges (and any C++ nonsense for that matter)?

    Thanks!

  13. I must say that the ranges are my top expectations from c++ 20.
    I’m a little bit confused, thou since I was told that they are creating a bunch of dangling references.
    But the functional way to look at containers in c++ seems to me a great addition in the language.
    Great work. Really!

    • It’s certainly possible to create dangling references with views, just as it is easy to be left holding an iterator to a container that is no longer in scope. Ranges have some built-in guard rails, but they won’t keep you out of every pit.

  14. The code scares me ! I am still trying to learn templates and STL and having a little idea of python simplicity, i am wondering why the code before main is not auto generated / hidden. How nice it would have been if one has to write just the code written in main. Why can’t C++ do it?

  15. Hi, currently I’m using ranges to provide a common interface for an arbitrary templated number of underlying containers with different types.

    For this I used tools like boost::join, boost::any_range and boost::adaptors::transformed to provide a lazy mechanism of base casting and joining. Surely range-v3 is completely capable of this, but I manage to do it quickly enough without adding new libraries to the project.

    Would be possible to do something like this with little/no extra work with C++20 Ranges?? Or there will be some key feature lacking yet?

    Great work, keep on rocking it!

  16. Hi Eric,

    In your declval implementation you use the following approach:
    template
    _Up __declval(int);

    Could you please explain why it’s better than just:

    template
    _Tp&& __declval(int);

    Or is it just a matter of style?

    Sorry for the offtopic ?

  17. Will c++20 ranges have some kind of reduce?

    std::vector start{1,23,4,54,97};
    auto sum = start | filtered(iseven)|reduced(2,add);
    assert(sum == 60);

      • struct triple_t {
        int x, y, z;

        void next() {
        // To transform a coroutine to a normal function:
        // 1. Factor all the state into data members.
        // 2. Replace the yield with a return.
        // 3. Put a resume label right after the yield.
        // 4. Start with a jump to the resume label.

        goto resume;

        // Find triples x * x == y * y + z * z.
        for(; ; ++x) {
        for(y = 1; y < x; ++y) {
        for(z = y; z < x; ++z) {

          if(x * x == y * y + z * z)
            return;     // Replace a yield with a return.
        
          resume: ;     // Resume right after the yield.
        }
        

        }
        }

        }
        };

        You can transform a coroutine (the more natural formulation for this) to a normal function using these steps. Why is computing Pythagorean triples a good showcase for ranges when the treatment above is easier to follow, doesn’t require any new mechanisms, builds faster and will execute faster?

  18. This is an exciting library!
    May I ask a question: are containers and view supposed to be used orthogonally?
    For instance, this compiles:
    std::vector const v { 1, 2, 3, 4, 5, 6 };
    auto rng = v | views::filter([](int i) { return i % 2 == 0; });

    But this does not:
    std::vector const v { 1, 2, 3, 4, 5, 6 };
    auto rng = v | views::group_by([](int c) { return c; });

    Why is that?

  19. Oh, I misunderstood. I thought it’s a unary predicate that returns an identifier of the group that supports equivalency.
    It’s still not quite intuitive – why is the output of the following program:

    std::vector<int> const v2 { 1, 2, 3, 4, 5, 6 };
    auto rng = v2 | views::group_by([](int c, int d) { return c % 2 == d % 2; });
    cout << rng << endl;

    [[1],[2],[3],[4],[5],[6]]

    instead of

    [[1,3,5],[2,4,6]]
    ?

    • The name group_by is leading you astray. This is not like a SQL query. It is grouping adjacent elements that satisfy the predicate. In that way, group_by is linear in time and space.

  20. Congrats on getting ranges into C++! This is a great addition. I am a little late, but anyway…

    I have recently spent some time with the old iterator concepts and I believe that some of your conclusions are more grim than they should be.

    For example I think that a “iota” iterator can be implemented in them even as a random access iterator. The trick is that operator* returns a reference to the number that lives inside the iterator. Of course this means that as soon as the iterator is changed or destroyed, the reference becomes dangling. I am of the opinion that this still conforms with the definition. Note that istream_iterator does exactly that (even though it could have been specified to return something else, because it is an input iterator). The intersting case is operator[], which can’t return a reference, because there is no iterator object, where the value could live in. But then see how the definition requires it returns something “convertible” to reference. Now what (besides reference) could be convertible to a reference you ask? Well, a temporary is (at least convertible to a const reference). So it seems that the old iterator concepts were carefully designed so that such iterators are still possible.

    Also, iterators that use proxy objects can be random access iterators in C++98 to C++17 as well, using the same trick as well (i.e. the proxy object lives inside the iterator) with the simple addition that value_type also needs to specify the proxy type. Of course it would be a different type than the underlying container’s value_type, but algorithms usually work on the iterators and so the inconsistency doesn’t break them.

    So I believe that both iota and proxy iterators are possible as random access iterators, but implementing that (especially good proxy iterators) is quite some work, and being freed from the requirement to hold a physical copy of the proxy object should make that much simpler.

  21. I have a question regarding the design of the ranges library.

    The following code snippet is used to illustrate two expectations that I had when I took a first look at the ranges library.

    std::vector const input{ “2”, “3”, “1” };
    using namespace ranges;
    std::vector output = input
    | views::transform([](std::string s) { return std::stoi(s); })
    // expectation #1: transform returns something that can be sorted
    | to() // this line is needed
    | actions::sort
    // expectation #2 : sort returns something that can be filtered
    | views::filter([](int i) { return i % 2 == 0; }); // this line won’t compile

    Both of my expectations are obviously not met: firstly, one has to convert the result of transform to a container in order to sort it and secondly, you can not use this sorted container in the next step of the pipeline. I am sure there are good reasons that led to this specific design, but could not come up with them myself. So can you maybe shed some light on them ?

  22. Thank you for doing this awesome work! I am new to C++, and coming from python and JS, I really like that you can finally pass a range in an algorithm instead of passing begin and end iterators. And transform and filter make my code more functional and easy to read. Kudos for your work!

Leave a Reply to Jan Cancel reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.