dutinmeow's blog

By dutinmeow, history, 6 weeks ago, In English

In light of Codeforces recently adding C++20, I would like to introduce one of the most useful features included with that update: The ranges library, now included in the <ranges> header.

Unsurprisingly, the <ranges> header involves manipulating ranges, or a block of memory delimited by a begin() and end(). One example of its use can be found in the std::sort function.

Pre C++20, how one might sort a vector may look something like:

vector v {5, 4, 3, 2, 1};
sort(v.begin(), v.end());     // sort in increasing order, using '<' comparator
sort(v.rbegin(), v.rend());   // sort in reverse order
sort(v.begin() + 2, v.end()); // sort all but first 2 elements

Of course, these aren't the most syntactically pleasing, but given the lack of alternatives, we have gotten used to it. Despite being unambiguous and flexible, this is less intuitive than directly calling sort on the container which we want to sort. What if we could just do sort(v) (similar to Python!)?

C++20 introduces the std::ranges namespace, which includes a range equivalent of every method in the <algorithms> library, including std::sort. To sort a vector, we can now do:

vector v {5, 4, 3, 2, 1};
ranges::sort(v);                 // sort in increasing order
ranges::sort(views::reverse(v)); // sort in reverse order
ranges::sort(views::drop(v, 2)); // sort all but first 2 elements

So what are views? Views are ranges that are usually defined on another range and transform the underlying range via some algorithm or operation. Views do not own any data beyond their algorithm and the time it takes to construct, destruct or copy them should not depend on the number of elements they represent. The algorithm is required to be lazy-evaluated so it is feasible to combine multiple views. That is,

vector<int> v {1, 2, 3, 4, 5};
auto view = views::all(v);

view in the above code contains no additional memory and can be initialized in constant time. This is convenient when we want to "copy" large ranges, without the additional time or memory overhead. Creating view neither changes v nor incurs any additional elements into view. The elements of view are thus accessed on demand.

What makes this technique even more powerful is the ability to chain operations:

vector<int> v {1, 2, 3, 4, 5};
auto view1 = views::drop(views::reverse(v), 2);
auto view2 = v | views::reverse | views::drop(2);

In the above code, view1 and view2 are equivalent: Both contain, in order, the elements 3, 2, 1. The '|' or "pipe" operator combines the view statements.

Suppose we wished to create a view such that we remove the odd numbers, and square the evens. We could do it in the following way:

vector<int> v {1, 2, 3, 4, 5};
auto view = v | views::filter([](const int x) { return x % 2 == 0; }) | views::transform([](const int x) { return x * x; });

Because views are inherently range-like objects, they intuitively support range iteration:

vector<int> v {1, 2, 3, 4, 5};
auto view = views::all(v);
for (int x : view) {
    // stuff goes here

Moreover, we can extend this to create concise and explicit range-based for loops:

vector<int> v {1, 2, 3, 4, 5};
for (int x : v | view::reverse) {
     // stuff goes here

A list of what I think are the most useful views methods:

  • views::filter — Removes elements satisfying some condition
  • views::transform — Changes elements according to some condition
  • views::take — A view consisting of the first N elements of some other view
  • views::take_while — Takes the elements of another view until a condition is not satisfied (potentially useful for range-based while loops)
  • views::drop — A view that skips over the first N elements of some other view
  • views::drop_while — A view that drops elements until a condition is not satisfied
  • views::reverse — This does what you think it does
  • views::keys — Extracts the first element of "pair-like" values (works for pairs as well as maps)
  • views::values — Extracts the second elements of "pair-like" values

I hope everybody finds this useful!

  • Vote: I like it
  • +234
  • Vote: I do not like it

6 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

That's a great progress for C++ although still a bit too verbose as for my taste =)

I'd like to see something along the lines of

vector<int> v {1, 2, 3, 4, 5};
auto view = v | filter(x => x % 2 == 0) | transform(x => x * x);