CODEWITHSUNDEEP
c++sortingstlvectoriterator
fredoverflow
fredoverflow

Reputation: 263018

Sorting a vector in descending order

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?

Upvotes: 410

Views: 370222

Answers (11)

Gordon Hsu
Gordon Hsu

Reputation: 111

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

Upvotes: 1

Krish Munot
Krish Munot

Reputation: 1103

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

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

Upvotes: 6

ivaigult
ivaigult

Reputation: 6667

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.

Upvotes: 16

rashedcs
rashedcs

Reputation: 3725

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.

Upvotes: 15

user325117
user325117

Reputation:

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

Upvotes: 2

user7069426
user7069426

Reputation: 

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

Upvotes: 10

Julian Declercq
Julian Declercq

Reputation: 1586

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

Upvotes: 33

mrexciting
mrexciting

Reputation: 1596

With c++14 you can do this:

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

Upvotes: 158

shoumikhin
shoumikhin

Reputation: 1345

What about this?

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

Upvotes: 35

zw324
zw324

Reputation: 27180

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.

Upvotes: 19

Pubby
Pubby

Reputation: 53017

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.

Upvotes: 83

Related Questions