How to sort a vector using std::views C++20 feature?

Question

I want to loop through a vector in a sorted way without modifying the underlying vector.

Can std::views and/or std::range be used for this purpose?

I've successfully implemented filtering using views, but I don't know if it is possible to sort using a predicate.

You can find an example to complete here : https://godbolt.org/z/cKer8frvq

#include <iostream>
#include <ranges>
#include <vector>
#include <chrono>

struct Data{
    int a;
};

int main() {

    std::vector<Data> vec = {{1}, {2}, {3}, {10}, {5}, {6}};
  
    auto sortedView = // <= can we use std::views here ?
                           
    for (const auto &sortedData: sortedView) std::cout << std::to_string(sortedData.a) << std::endl; // 1 2 3 5 6 10

    for (const auto &data: vec) std::cout << std::to_string(data.a) << std::endl; // 1 2 3 10 5 6
}

Irrepressible

[OT]: std::to_string is unneded, std::cout << data.a is correct. – Asta

This vector can hold about 1GB of data...so I'd rather not copying it – Irrepressible

Answer 1

You have to modify something to use std::ranges::sort (or std::sort), but it doesn't have to be your actual data.

#include <iostream>
#include <ranges>
#include <numeric>
#include <algorithm>
#include <vector>
#include <chrono>

struct Data{
    int a;
    friend auto operator<=> (const Data &, const Data &) = default;
};

int main() {

    std::vector<Data> vec = {{1}, {2}, {3}, {10}, {5}, {6}};

    std::vector<std::size_t> indexes(vec.size());
    std::iota(indexes.begin(), indexes.end(), std::size_t{ 0 }); // 0z in C++23

    auto proj = [&vec](std::size_t i) -> Data & { return vec[i]; };

    std::ranges::sort(indexes, std::less<>{}, proj);
  
    auto sortedView = std::ranges::views::transform(indexes, proj);
                           
    for (const auto &sortedData: sortedView) std::cout << sortedData.a << std::endl; // 1 2 3 5 6 10

    for (const auto &data: vec) std::cout << data.a << std::endl; // 1 2 3 10 5 6
}

Scevour

Can you explain this line in detail please? : auto proj = [&vec](std::size_t i) -> Data & { return vec[i]; }; – Irrepressible

@Victor: See lambda (with capture and trailling return type). – Asta

@Asta it's actually the Data & { return vec[i]; } return type that I don't understand right now – Irrepressible

@Victor: -> Data& is trailing return type. (without that it would return by value). – Asta

Answer 2

This solution is a bit misleading, as this is technically not a view. You loose the lazy evaluation. But it is worth mentioning because it is a very simple solution and it fits very well in pipelines.

This solution uses C++23.

You can use a pipe to ranges::to<set>():

#include <iostream>
#include <ranges>
#include <vector>
#include <set>
using namespace std;

struct Data{
    int a;
    friend auto operator<=> (const Data &, const Data &) = default;
};

int main() {

    vector<Data> vec = {{1}, {2}, {3}, {10}, {5}, {6}};
  
    auto sortedView = vec | ranges::to<set>() ;// <= yes, we can use std::views here !
                           
    for (const auto &sortedData: sortedView) cout << to_string(sortedData.a) << ' '; // 1 2 3 5 6 10

    cout << endl;

    for (const auto &data: vec) cout << to_string(data.a) << ' '; // 1 2 3 10 5 6
}

Couldn't be more simple!

If performance really mattered, I wonder if it would be advisable to do it that way ?

It only works if all values are unique. Otherwise, you can use ranges::to<multiset>().

You can use all stl containers do achieve various effects, like sorting, deduplication, ...

I am interested to read what people think about doing this performance wise.

Nepean

sortedView is not a view, it is a std::set. So this is not lazily evaluated and is not avoiding the copy for a smaller memory footprint according to my understanding. Not everything that can be piped is a view (anymore). – Comedown

It is not a view, but it can be part of a pipeline, that is why I thought it was worth mentioning. – Nepean

Maybe that is just me, but without lazy evaluation I don't think one should use this in the middle of a pipeline instead of at the end of one. Either way, both the variable name and the comment citing std::views are misleading. OP only commented the requirement of not copying the data instead of adding it to the question, so I guess this is technically still a valid answer if you make clear that there is no views here (funnily not even a move-only ranges::owning_view). – Comedown

See also std:sort vs inserting into an std::set for performance considerations. – Comedown

there is certainly a performance vs simplicity tradeoff to consider. Also, new containers flat_set and flat_map might make this solution more appealing, when (if ?) they become available. – Nepean

Oh and I just saw the question is tagged c++20 and ranges::to is C++23. – Comedown