In c++, what is the fastest way to sort in reverse order?

Question

Is it one of the following or something else?

//1
sort(first,last,[](const T &a,const T &b){return comp(b,a);});
//2
sort(first,last,bind(comp,ref(_2),ref(_1));
//3
sort(make_reverse_iterator(last),make_reverse_iterator(first),comp);
//Use value instead of reference if object size is small.

This is not a duplicate of Sorting a vector in descending order ,this one considers user-defined comparison function.

Possible duplicate of [Sorting a vector in descending order](https://stackoverflow.com/questions/9025084/sorting-a-vector-in-descending-order) — smac89, Sep 07 '19 at 04:09
one idea using a `std::set` and operating on it with reverse iterators — Andreas DM, Sep 07 '19 at 04:14

smac89 · Answer 1 · 2019-09-07T04:41:00.893

0

No easier way than to simply reverse your comparator. If your comparator returns true when it compares A and B, make it return false instead, and vice versa.

Make sure to take care of the case where A and B are equal; that case, you want the comparator to still return false

It doesn't get any faster when you do that btw.

edited Sep 07 '19 at 04:41

answered Sep 07 '19 at 04:17

smac89

39,374
15
132
179

What will be faster usually, lambda or bind? – user Sep 07 '19 at 04:19
@user I'd say it doesn't matter, but you should probably do a benchmark to test that theory. IMO, use lambda as much as possible (and watch those scopes!) – smac89 Sep 07 '19 at 04:24
@smac89 The comparison function object for `std::sort` returns a `bool`. Returning -1 instead of 1 won't work. – Blastfurnace Sep 07 '19 at 04:27
@Blastfurnace ahh yes thanks. I was thinking java when I wrote that – smac89 Sep 07 '19 at 04:28
The "vice versa" is not quite that simple - your original comparator will also return `false` if `A` and `B` are equivalent, and in that case your new comparator needs to return `false` as well. – Nate Eldredge Sep 07 '19 at 04:39
1

It turns out that lambda is significantly faster – user Sep 07 '19 at 04:50
@user: Are you compiling with optimization fully enabled (e.g. `g++ -O3`)? – John Zwinck Sep 07 '19 at 13:44
@JohnZwinck I mainly use MSVC with full optimization. Further discussion: https://stackoverflow.com/questions/57830971/why-wrapping-a-function-into-a-lambda-potentially-make-the-program-faster – user Sep 07 '19 at 13:52

score -1 · Answer 2 · answered Sep 07 '19 at 04:56

-1

Benchmark shows using a lambda is much faster than the other two.

answered Sep 07 '19 at 04:56

user

475
3
10

In c++, what is the fastest way to sort in reverse order?

2 Answers2