Why can't a range be sorted in range-v3?

Question

Using the Range-v3 (release 0.10.0) library I was trying to construct a range from a std::vector, transform it into another range and finally sort that range. I expected the sort step to produce another range that I could consume later. But the best I could come up with was this:

std::vector<std::string> const input { "2", "3", "1" };
using namespace ranges;
std::vector<int> output = input
    | views::transform([](std::string s) { return std::stoi(s); })
    | to<std::vector>()
    | actions::sort

Notice the use of to<std::vector>() after the transform step and before the sort step. This seems to allocate a new std::vector when all I wanted was to sort the range that the transform step had produced.

Why is there no view::sort ? It would fit nicely in the above composition of ranges.

Consider how one would implement a hypothetical view::sort. — Sneftel
– Sneftel, Commented Feb 21, 2020 at 11:53

Alan Birtles · Accepted Answer · 2020-02-21 11:59:19Z

9

The transformed range is only a view, the elements are generated one at a time as the view is iterated. It can't be sorted as there is nowhere to store the sorted elements. A hypothetical implementation would also be inefficient as it would have to transform each element every time it needed to do a comparison for the sort.

Your solution is correct to store the transformed elements in a vector then sort them.

answered Feb 21, 2020 at 11:59

Alan Birtles

38.4k4 gold badges39 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Angle.Bracket Over a year ago

When you look at Enumerable.OrderBy(...) in C# or Stream.sorted(...) in Java: these functions both do accept and produce "Ranges" so they contribute to composability of their respective libraries. I also can't see any significant downside regarding efficiency compared to the procedural way of doing the same things in these languages. So I thought the same should be possible in C++. Has the author of ranges-v3 sacrificed style for speed in this case ?

Alan Birtles Over a year ago

Both of those presumably generate a list of elements internally, the c++ api is just making you explicitly ask it to do so, that way you aren't surprised when sorting your million element view uses lots of memory

Alan Birtles Over a year ago

E.g see stackoverflow.com/questions/3329985/…

Alan Birtles Over a year ago

A vector is a range?

T.C. Over a year ago

It interrupts the view pipeline because a temporary vector is not a view. If you want further eager processing, use actions. If you want laziness, store the vector into a variable so that it's not a temporary.

|

Collectives™ on Stack Overflow

Why can't a range be sorted in range-v3?

1 Answer 1

9 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Linked

Related