A blog about C++, music software, tech community, and life.

How to make a container from a C++20 range

As a C++ committee member, my biggest problem is that it’s virtually impossible to really understand all the new features that are being added to the language – there are simply too many. The survival strategy is to limit your studies to a subset, at a pace that your brain can handle.

And so I only now finally started getting my head around ranges, even though they are probably the most significant standard library feature coming in C++20.

There’s a lot I like about ranges. Most importantly, they finally make STL algorithms composable. Did you ever have to implement your own transform_if because there was no way to chain std::copy_if and  std::transform? Ranges let you do that.

But the learning curve is somewhat steeper than I had hoped.

Let’s say you have some nice C++20 range r. Perhaps it’s a view that transforms a numerical sequence or something – doesn’t really matter.

Now, you want to store that sequence. Let’s put it into a  std::vector. Everyone loves vectors, right? This should be really simple, right? So how do we do that?

Naively, I expected that it should be as simple as direct-initialising the vector with the range (and thanks to CTAD, we shouldn’t even have to write its template arguments):

std::vector v(r);

Except unfortunately it doesn’t compile. Even though the standard algorithms got shiny new versions taking C++20 ranges instead of iterator pairs, the standard container constructors did not.

Alright, so you can’t convert a range to a container, neither implicitly nor explicitly. Fine. Perhaps there is a utility function to do that? Turns out that in Eric Niebler’s range-v3 library, there is one! This is how you do it in his library:

auto v = std::ranges::to<std::vector>(r);

That little to function is very handy indeed. Except that in C++, it doesn’t exist. It’s one of those features of range-v3 that didn’t make it into the C++20 standard. So we’re out of luck. Perhaps we will get it in C++23 (there is a proposal), but in the meantime, what do we do instead?

Rolling your own to turns out to be surprisingly complicated, so I wouldn’t recommend that unless you’re a ranges expert. So, if you want to stick to standard C++20, what do we have instead? Let’s try the good old STL container constructors taking iterator pairs:

std::vector v(r.begin(), r.end());

Or perhaps, if you prefer,

std::vector v(std::ranges::begin(r), std::ranges::end(r));

But in general, that won’t work either. Turns out there are different flavours of ranges.

There are the STL containers, for which begin() and end() both return iterators of the same type. We call such a range a “common range”. If r is a common range, the above code will work.

However, for all the new C++20 views, begin() returns an iterator and end() returns a sentinel. In general, those are different types. If you give the constructor of std::vector an iterator pair where the types don’t match, it will be all confused and fail to compile.

At first, it might look like we can fix this. There is a view in C++20 that lets you convert a non-common range into a common range. It’s called the common view. The adapter std::views::common returns the common view of a range, if it is not a common range already, and the all view of the range otherwise:

auto common = std::views::common(r);
auto v = std::vector(std::ranges::begin(common), std::ranges::end(common));

Unfortunately, this still doesn’t work for all ranges. Ranges with non-copyable iterators, such as std::ranges::basic_istream_view, cannot be converted to a common range (this is a constraint of common_view). In this case, this approach doesn’t work at all.

Long story short: C++20 ranges really don’t play well with STL functions expecting an iterator pair.

So let’s try another approach. We can default-initialise the container first (which means you won’t get to benefit from CTAD), and then you explicitly copy the elements of the range across:

std::vector<my_type> v;
std::ranges::copy(r, std::back_inserter(v));

This isn’t great. And it gets more verbose if you need to figure out what my_type is. In C++20, you get the element type of a range with range_value_t:

std::vector<std::ranges::range_value_t<decltype(r)>> v;
std::ranges::copy(r, std::back_inserter(v));

Finally, if you care about performance, you probably want to call v.reserve(size), if and only if the range allows you to determine its size in constant time:

std::vector<std::ranges::range_value_t<decltype(r)>> v;

if constexpr(std::ranges::sized_range<decltype(r)>) {
    v.reserve(std::ranges::size(r));
}

std::ranges::copy(r, std::back_inserter(v));

Note that I used a C++20 concept below (sized_range) inside an if constexpr conditional. One of the many cool things about concepts is that you can use them as compile-time functions that take types and return a bool.

Now you can take this code and wrap it into a to_vector function. This will work. Unfortunately, this approach is container-specific. For containers other than std::vector, there might be no reserve and back_inserter, so the code will look somewhat different, but the general idea remains the same.

And that’s how you can make a container from a range in C++20.

Many thanks to Christopher Di Bella and Corentin Jabot for helping me figure this out.

4 Comments

  1. Mario Galindo

    What about the simple:
    for(auto i : r) v.push_back (i);

    • Timur Doumler

      This works, and it’s the same as my ` std::back_inserter(v)` approach above (but written out as raw loop). It requires repeated memory allocations, so it’s less efficient than directly constructing the vector from the range.

  2. Liam

    Hi Timur, I have been trying to update my code with ranges recently and have also been met with a lot of frustration. I found this post very helpful, but there are still a lot of questions and practical restraints with ranges that are holding me back. For instance, the the types that you get after chaining a few views together are insane–the `auto` keyword makes it all go away, but if you ever want to define a range outside of a local scope then good luck!

    There also seem to be very few resources available on ranges, even on stack overflow. I would have though that there would be enough programmers rushing to use the new library that there would be more discussion like this blog post working out best practices together. Is anyone aware of any such forum? If not, is there any interest in creating one?

  3. Sean Farrell

    Implementing to is “surprisingly complicated”. But only if you want to be able to supply the container without a value type. Here is an example of a to function that does 95% of what you need: https://godbolt.org/z/94hWf9vcM

    The key idea why std::copy and friends are not desired is because the entire idea of view and ranges is to do transformations inline. But in some cases they need to be grounded back into actual containers.

Leave a Reply

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

© 2024 timur.audio

Theme by Anders NorénUp ↑