Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using a projection from the elements instead of a comparator for sorting

I searched for c++ analog for this (python):

sorted(vector, key=lambda x : my_function(x))

There is of course the construction:

std::sort(vector.begin(), vector.end(), [](const auto& lhs, const auto& rhs) {
    return my_function(lhs) < my_function(rhs);
});

I just wondering if one-argument construction exists.

like image 947
MrNewman Avatar asked Oct 15 '22 08:10

MrNewman


1 Answers

Using ranges instead of iterator-pairs when you want will come with C++20.

Aside from that, a projection (in combination with a flag for reversing the order) is more concise where the job is straight-forward, like all sub-keys in the same order, and all sorted according to their "natural" ordering.
A comparator is not relentlessly optimised for that scenario, trading that ease for all-around optimal performance and easy implementation of more demanding and even outright weird orders.

Python's sorted() only allows for a projection and optional reverse-flag.

std::sort() sorts elements, optionally according to a custom comparator. In principle, it could be extended to try using the passed function-object (if any) as a projection if it doesn't work as a comparator, feel free to propose it for standardisation.

Until and unless that happens, you can easily synthesise a comparison from a projection and an order-relation though:

template <class Projection, class Comparator = std::less<>>
struct use_projection {
    [[no_unique_address]] Projection p = Projection();
    [[no_unique_address]] Comparator c = Comparator();
    template <class... T>
    auto operator()(T&&... t) const
    noexcept(noexcept(c(p(std::forward<T>(t))...)))
    -> decltype(c(p(std::forward<T>(t))...))
    { return c(p(std::forward<T>(t))...); }
};

auto my_projection = [](auto&& x)->auto&& { return x.y; };
std::sort(v.begin(), v.end(), use_projection{my_projection});
std::sort(v.begin(), v.end(), use_projection{my_projection, std::greater()});

Adapting that idea for pre-C++17 is left as an exercise for the reader.

like image 155
Deduplicator Avatar answered Oct 27 '22 00:10

Deduplicator