Sorting a vector in descending order

Question

Should I use

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

or

std::sort(numbers.rbegin(), numbers.rend());   // note: reverse iterators

to sort a vector in descending order? Are there any benefits or drawbacks with one approach or the other?

Solution 1

Actually, the first one is a bad idea. Use either the second one, or this:

struct greater
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};

std::sort(numbers.begin(), numbers.end(), greater());

That way your code won't silently break when someone decides numbers should hold long or long long instead of int.

Solution 2

With c++14 you can do this:

std::sort(numbers.begin(), numbers.end(), std::greater<>());

Solution 3

Use the first:

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

It's explicit of what's going on - less chance of misreading rbegin as begin, even with a comment. It's clear and readable which is exactly what you want.

Also, the second one may be less efficient than the first given the nature of reverse iterators, although you would have to profile it to be sure.

Solution 4

What about this?

std::sort(numbers.begin(), numbers.end());
std::reverse(numbers.begin(), numbers.end());

Solution 5

Instead of a functor as Mehrdad proposed, you could use a Lambda function.

sort(numbers.begin(), numbers.end(), [](const int a, const int b) {return a > b; });

View more solutions

Comments

[Xeo]

Did you maybe just not compile with optimizations turned on? Sounds very much like the reverse_iterator operations weren't inlined, and given that they're just a wrapper around the actual iterators, it's no wonder they take double the time without inlining.

[Pubby]

@Xeo Even if they were inlined some implementations use an addition per dereference.

[Xeo]

@ildjarn: Because it's like that? The base() member function for example returns the wrapped iterator.

[zw324]

@Xeo Now they both finish in a second. Thanks!

[ildjarn]

@Xeo : I take it back; the standard actually mandates that std::vector<>::reverse_iterator is implemented in terms of std::reverse_iterator<>. Bizarre; today I learned. :-P

[user541686]

@FredOverflow: You did the honors in your comment ;)

[niclas werther]

Or stick with the first one. Use a typedef for the numberContainer - a good idea so that someone CAN swap to long long - and write: std::sort(numbers.begin(), numbers.end(), std::greater<numContainer::value_type>());

[yanpas]

Why is it impossible to do with lambda?

[greg]

A reason could be to avoid the additional complexity: O(n * log(n)) + O(n) vs O(n * log(n))

[pjvandehaar]

@greg O(n * log(n)) = O(n * log(n) + n). They are two ways of defining the same set. You mean to say "This might be slower."

[Abhishek Divekar]

+1 The first one is really confusing. What is greater than the other? rbegin and rend were made for a specific purpose.

[einpoklum]

Why not just std::greater<typename decltype(numbers)::value_type>() or something?

[Apollys supports Monica]

This is like a thousand times more confusing than just using the std::greater comparator....

[Philipp Claßen]

This is the same answer as mrexciting's one. The remark about complexity is also unclear to me.

[Philipp Claßen]

@Apollys I agree that starting with C++14, std::greater<> looks like the prefered solution. If you do not have C++14, it could still be useful if you want to rule out any surprises with std::greater<int> (e.g., when the types at some point change from int to long).

[Ofek Gila]

@pjvandehaar Greg is fine. He explicitly didn't say, O(n * log(n) + n), he said O(n * log(n)) + O(n). You're right that his wording is unclear (especially his misuse of the word complexity), but you could've answered in a kinder way. E.g.: Maybe you meant to use the word 'computation' instead of the word 'complexity'. Reversing the numbers is an unnecessary O(n) step to an otherwise identical O(n * log(n)) step.

[pjvandehaar]

@OfekGila My understanding is that big-O notation is about sets of functions, and notation involving = and + are just conveniences meaning ∈ and ∪. In that case, O(n*log(n)) + O(n) is a convenient notation for O(n*log(n)) ∪ O(n) which is the same as O(n*log(n)). The word "computation" is a good suggestion and you are right about the tone.

[Nikolai]

This answer is outdated - you can use std::greater<>() since C++14.

[Simon Eatwell]

C++17 std::sort(numbers.begin(), numbers.end(), std::greater{}); C++20 std::ranges::sort(numbers, std::ranges::greater());

[Abdurrahim]

iteration order can change behavior based on prefetching and caching optimizations: stackoverflow.com/a/1951271/2187015