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 theView
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 foriter_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 ForwardIterator
s. 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 View s 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 totrue
, - 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 standardistream
, - 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]
, aview::join
that takes a delimiter,view::intersperse
,view::unique
, andview::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.
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.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 :).
It’s very exciting to finally get usable STL interface 🙂
Looks like link to godbolt is broken? (From the end of “Constrained Algorithms” section).
“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.
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!
In range-v3, it’s called
view::bounded
. The Committee changed its name, and I haven’t gotten around to updating range-v3.Hi Eric,
In the list sort example, the following line
using ranges = std::experimental::ranges;
should probably be
namespace ranges = std::experimental::ranges;
Right?
Oops, you’re right! Thanks.
Eric, another question. Following your description of
ranges::begin
and the definition of theRange
concept, I thoughtvector<int>&&
should not satisfyRange
. However, a test with CMCSTL2 showedRange<vector<int>&&>
returnedtrue
. What did I miss?The
Range
concept is defined such thatRange<T>
is the same asRange<T&>
. That was done because it should be possible to passvector<int>&&
tostd::ranges::count
for instance. It would be perfectly safe. From with the body of thecount
algorithm,begin
andend
are called on the vector as an lvalue.Thanks. I forgot that the
Range
definition follows the same rule as normal code, and any variable not marked bystd::forward<T>(…)
is always an lvalue.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.
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?
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.
Your for_each operator is called flatMap in other PLs and frameworks, that would avoid confusion with common foreach semantics.
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.
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.
Ok
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?
Because single view and empty view have different types, they cannot both be returned from the same function. But you have the right idea.
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 ?
It’s something I can certainly look into in the new year. There are better ways to present code blocks today than there were when I set this blog up.
Everywhere in C++ pipelines are built like a>>b>>c or a
Okay so apparently this wonderful website decided to drop most of my message because I dared to use the mirror image of the > character.
Maybe you missed my website’s tagline: judge me by my C++, not my WordPress. But maybe I won’t come out any better in your estimation… 😉
By the way, what’s the justification for introducing a brand new meaning to the or operator with the a|b|c syntax instead of leaning on the decades-old second meaning of a>>b>>c?
The pipe syntax from Unix is older by far. But you’re right, I could have picked
>>
.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!
Soon C++ compilers are going to pass Turing Test.
this::post::makes::me::to::
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.
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?
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!
C++20 will have a join view and a transform view, but not a type-erased view. For the time being, you’ll need a separate library for that.
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 ?
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);
It’s an algorithm:
std::ranges::accumulate
. You pass the adapter range to the algorithm instead of piping the range into it.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) {
}
}
}
};
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?
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?
views::group_by
takes a binary predicate and returns true if the two elements are in the same group.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.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.
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 ?
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!
Thank you! 🙏