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?

Depurate

+1 I think the answer is obvious, but this question has an interesting bit of trivium. :) – Yolondayon

I'd vote for the first option, just because then I won't ever have to deal with reverse_iterator's. – Lipocaic

@Yolondayon A noob question but why should the second one sort in descending order ? We are giving the same array as input to the sort method. It's just that we are giving it in the reverse order so why should it be sorted in descending and not ascending order as would be the case with ar.begin() and ar.end. – Mohsen

@Mohsen std::sort(b, e); puts the minimum at b (in our case rbegin, so the last element) and the maximum at e (in our case rend, so the first element). – Depurate

Does this answer your question? Sorting vector elements in descending order – Cohette

Answer 1

With c++14 you can do this:

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

Vibration

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

@SimonEatwell is the latter superior to the former if C++20 is available? – Krispin

@Krispin Yes, the latter is superior given that C++20 is available because one can accidentally pass a wrong pair of iterators in the former case. One can accidentally do std::sort(numbers.end(), numbers.begin(), std::greater{}) or std::sort(numbers.begin(), something_else.end(), std::greater{}). Always prefer std::ranges. – Plutonic

Answer 2

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.

Harkey

Answer 3

What about this?

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

Undershrub

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

@Ardithardme 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." – Gadolinium

@Gadolinium 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. – Ilocano

@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. – Gadolinium

Answer 4

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; });

Hundredpercenter

Answer 5

According to my machine, sorting a long long vector of [1..3000000] using the first method takes around 4 seconds, while using the second takes about twice the time. That says something, obviously, but I don't understand why either. Just think this would be helpful.

Same thing reported here.

As said by Xeo, with -O3 they use about the same time to finish.

Martinez

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. – Jeu

@Jeu Even if they were inlined some implementations use an addition per dereference. – Harkey

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

@Jeu Now they both finish in a second. Thanks! – Martinez

@Jeu : 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 – Lactic

iteration order can change behavior based on prefetching and caching optimizations: https://mcmap.net/q/16801/-c-for-loop-indexing-is-forward-indexing-faster-in-new-cpus – Bencher

Answer 6

First approach refers:

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

You may use the first approach because of getting more efficiency than second.
The first approach's time complexity less than second one.

Henninger

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

Answer 7

TL;DR

Use any. They are almost the same.

Boring answer

As usual, there are pros and cons.

Use std::reverse_iterator:

• When you are sorting custom types and you don't want to implement operator>()
• When you are too lazy to type std::greater<int>()

Use std::greater when:

• When you want to have more explicit code
• When you want to avoid using obscure reverse iterators

As for performance, both methods are equally efficient. I tried the following benchmark:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std::chrono;

/* 64 Megabytes. */
#define VECTOR_SIZE (((1 << 20) * 64) / sizeof(int))
/* Number of elements to sort. */
#define SORT_SIZE 100000

int main(int argc, char **argv) {
    std::vector<int> vec;
    vec.resize(VECTOR_SIZE);

    /* We generate more data here, so the first SORT_SIZE elements are evicted
       from the cache. */
    std::ifstream urandom("/dev/urandom", std::ios::in | std::ifstream::binary);
    urandom.read((char*)vec.data(), vec.size() * sizeof(int));
    urandom.close();

    auto start = steady_clock::now();
#if USE_REVERSE_ITER
    auto it_rbegin = vec.rend() - SORT_SIZE;
    std::sort(it_rbegin, vec.rend());
#else
    auto it_end = vec.begin() + SORT_SIZE;
    std::sort(vec.begin(), it_end, std::greater<int>());
#endif
    auto stop = steady_clock::now();

    std::cout << "Sorting time: "
          << duration_cast<microseconds>(stop - start).count()
          << "us" << std::endl;
    return 0;
}

With this command line:

g++ -g -DUSE_REVERSE_ITER=0 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out
g++ -g -DUSE_REVERSE_ITER=1 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out

std::greater demo std::reverse_iterator demo

Timings are same. Valgrind reports the same number of cache misses.

Servais

Thank you for detailed answer. But personally for me the first way is more explicit. Because using reverse_iterator intuitively gives reverse sort. UPD, ok, I googled for "reverse sort" and got to this question, so for me the first way is explicit. If you need descending order then the second way is more explicit. But it's all the same anyway. – Segarra

But reverse sort is more generic, I think. You can use it for objects for which "greater" is not a quite correct word. – Segarra

Answer 8

bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);

Ideomotor

to be a valid answer, you should consider writing something about advantages/drawbacks of your vs. the OP's mentions methods – Geographical

Answer 9

You can either use the first one or try the code below which is equally efficient

sort(&a[0], &a[n], greater<int>());

Contortionist

Answer 10

I don't think you should use either of the methods in the question as they're both confusing, and the second one is fragile as Mehrdad suggests.

I would advocate the following, as it looks like a standard library function and makes its intention clear:

#include <iterator>

template <class RandomIt>
void reverse_sort(RandomIt first, RandomIt last)
{
    std::sort(first, last, 
        std::greater<typename std::iterator_traits<RandomIt>::value_type>());
}

Lignin

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

@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). – Ernaldus

Answer 11

For C++20:

std::ranges::sort(numbers, std::ranges::greater());

This rules out any possibility of passing in an invalid pair of iterators like:

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

Plutonic