C++17 In Detail

12 October 2020

Increased Complexity of C++20 Range Algorithms Declarations - Is It Worth?

With the addition of Ranges and Concepts in C++20, our good old algorithm interfaces got super long “rangified” versions. For example, copy is now 4 lines long… and it’s just the declaration!

template <ranges::input_range R, std::weakly_incrementable O>
requires std::indirectly_copyable<ranges::iterator_t<R>, O>
constexpr ranges::copy_result<ranges::borrowed_iterator_t<R>, O>
copy(R&& r, O result);

How to decipher such a long declaration? What benefits do we get instead? Is it worth it? Let’s find out.

Super Long Declarations

Here are some algorithms that have the range versions in C++20. They are available in the std::ranges namespace and located in the <algorithm> header.

Copy:

template< ranges::input_range R, std::weakly_incrementable O >
requires std::indirectly_copyable<ranges::iterator_t<R>, O>
constexpr ranges::copy_result<ranges::borrowed_iterator_t<R>, O>
copy( R&& r, O result );

4 lines!

And here’s the standard version, just two lines:

template< class InputIt, class OutputIt >
constexpr OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

Another one: find_if:

template<ranges::input_range R, class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>> Pred >
constexpr ranges::borrowed_iterator_t<R> find_if( R&& r, Pred pred = {}, Proj proj = {} );

Vs the “old” one:

template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );

You can see other algorithm in this handy page on C++ Reference: Constrained algorithms (since C++20) - cppreference.com and the “old” standard version at: Algorithms library - cppreference.com

Deciphering

Those new declarations might be intimidating at first, let’s try to decipher that syntax.

As an example, we can take std::ranges::copy_if which looks like a “monstrous template thing” at first!

template< ranges::input_range R, std::weakly_incrementable O,
          class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>> Pred >
requires std::indirectly_copyable<ranges::iterator_t<R>, O>
constexpr ranges::copy_if_result<ranges::borrowed_iterator_t<R>, O>
copy_if( R&& r, O result, Pred pred, Proj proj = {} );

Below you can find a simple use case:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

int main(){
    std::vector ints { 1, 2, 3, 4, 5, 6, 7 };
    std::ranges::copy_if(ints, std::ostream_iterator<int>(std::cout, ", "),
                          [](int x) { return (x % 2) == 0; });
}

See the live version @Wandbox

This code sample shows the super-easy client API that we can leverage. Just pass a whole container (no need for begin/end) and the output sequence.

To decipher the declaration, we need to look at the four major parts:

  • the template<> declaration
  • the requires clause
  • the return type
  • the function declarator with a parameter list

One additional note: ranges::copy_if is actually implemented not as a function… but a global function object… or niebloid (see at stackoveflow). But that’s a whole other story for now :)

The first part:

The first part is the longest one:

template<ranges::input_range R, std::weakly_incrementable O,
          class Proj = std::identity,
          std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>> Pred>

It describes the input template parameters: the input range R, output O, the projection and also the predicate.

This may look a bit more complicated then the old std::copy_if interface:

template< class InputIt, class OutputIt, class UnaryPredicate>
OutputIt copy_if( InputIt first, InputIt last, OutputIt d_first,UnaryPredicate pred );

The main reason for its complexity is that the declaration uses Concepts which is a massive feature for C++20. For now, we can say that they add some extra meaning and requirements on the template types. The old interface takes almost everything (like a void* in “template” meaning), and then we hope the compiler can compile the code… but with Concepts, we can specify some rules and so the compiler can spot mismatches early on.

For example the input range has to satisfy the input_range concept which is:

template<class T>
  concept input_range =
    ranges::range<T> && std::input_iterator<ranges::iterator_t<T>>;

// the range concept:
template< class T >
concept range = requires(T& t) {
  ranges::begin(t);
  ranges::end(t);
};

Makes sense… right?

The input range has to have begin() and end() and also its iterator type has to be input_iterator.

Then the output is weakly_incrementable so more or less it means that it can be incremented with i++, like an output iterator.

The second part:

The next part is a simple template parameter for projection, by default, it’s identity. In short thanks to projections, we can “see” elements obtained from the container differently. For example, we can iterate through the collection of “User” objects and extract only the name, or perform some additional computation. We’ll touch on that later.

And there is also this long specification for the predicate:

std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>> Pred

Briefly, projection can perform addition operation on the input element and then the result is pushed into the predicate, which then decides if the element matches the copying criteria or not.

The third section:

The other part “requires“:

requires std::indirectly_copyable<ranges::iterator_t<R>, O>

This time it restricts the input and output types so that they can read values from the input iterator and then write them into the output sequence. See the standard concept here: std::indirectly_copyable - cppreference.com

The final one:

After all of those restrictions, we can then read the most interesting part: the interface of the function:

copy_if( R&& r, O result, Pred pred, Proj proj = {} );

Easy right? :)

What do we get instead?

New versions of rangified algorithms are super large, and sometimes it’s even hard to find the name of the function.

It’s a great thing because we can now lament that C++ was super complicated and now it’s getting even worse! :)

But:

But Concepts and Ranges are not just for making our life more complex… it’s actually the opposite.

What do we get instead? What are the advantages do we get paying the price of more extended interfaces?

The Ranges

We can just call the algorithm on the whole range, no need to ask for begin/end:

std::vector ints { 1, 2, 3, 4, 5, 6, 7 };
std::ranges::copy_if(ints, ...);

With the regular version of std::copy you have to pass the start and end of the sequence:

std::copy_if(std::begin(ints), std::end(ints), ...);

That’s a feature on its own and C++ developers dreamed about it for decades :)

Composability

Ranges allow us to compose algorithms together. You can add filters, views, transforms and many other operations which they return a new range. This is not possible with standard algorithms.

For example we can create a simple view and take the first four elements of our container:

std::vector ints { 1, 2, 3, 4, 5, 6, 7 };
std::ranges::copy_if(ints | std::ranges::views::take(4), std::ostream_iterator<int>(std::cout, ", "),
                     [](int x) { return (x % 2) == 0; });

See the live code @Wandbox

Projections

I mentioned this before, but now we can look at a simple example:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>

struct Package {
    double weight;
    double price;
};

int main(){
    std::vector<Package> packages { 
        {100.0, 10.0}, 
        {104.0, 7.5},
        {95.0, 17.5},
        {91.0, 15.0},
        {100.1, 12.5 },
    };
    auto print = [](Package& p) { std::cout << p.weight << ": " << p.price << '\n'; };
    std::ranges::sort(packages, {}, &Package::weight);
    std::cout << "by weight: \n";
    std::ranges::for_each(packages, print);
    std::ranges::sort(packages, {}, &Package::price);
    std::cout << "by price: \n";
    std::ranges::for_each(packages, print);
}

Live code @Wandbox

The range algorithms use std::invoke to call the given projection on the given element of the range. Thanks to this approach, we can not only pass function objects but also ask for a data member of a class.

In our example above we can simply sort by Package::weight or Package::price in just a single line of code. There even no need to pass custom comparators!

Meaningful interfaces

With Concepts, we get a longer, but more descriptive interface for template types. They are not only <typename output, typename input> but you can now apply restrictions and convey that vital information through the code.

Better warnings

Compilers now have a way to check if the input argument for a template function matches the requires clause and concepts in the declaration. They can potentially improve on the warning side and make their messages cleaner.

Reduced compilation time (hopefully)

It’s improving! One one hand Ranges are a complicated beast, and compiling that might make code bloat, but on the other hand, Concepts might help the compilers to process things faster.

Sorry for a little interruption in the flow :)
I've prepared a little bonus if you're interested in Modern C++, check it out here:

Summary

In this blog post, I wanted to present that while the new declarations of range functions and algorithms might look very complicated, they are here for a reason. Not only they give us better interfaces, with more precise parameters, but also they allow easy algorithm composition or even doing projections.

You have to learn new syntax and constructs, but it’s worth the price.

It looks like that while you have 2x longer function declarations for those new algorithms, your final client code is several times shorter.

What do you think? Have you played with Ranges? What's your experience so far?

If you want to get additional C++ resources, exlusive articles, early access content, private Discord server and weekly curated news, check out my Patreon website: (see all benefits):

© 2017, Bartlomiej Filipek, Blogger platform
Disclaimer: Any opinions expressed herein are in no way representative of those of my employers. All data and information provided on this site is for informational purposes only. I try to write complete and accurate articles, but the web-site will not be liable for any errors, omissions, or delays in this information or any losses, injuries, or damages arising from its display or use.
This site contains ads or referral links, which provide me with a commission. Thank you for your understanding.