Trier un vecteur dans l'ordre décroissant

Question

Dois-je utiliser

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

o

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

pour trier un vecteur dans l'ordre décroissant ? Y a-t-il des avantages ou des inconvénients à l'une ou l'autre de ces approches ?

Answer 1

Au lieu d'un foncteur comme le propose Mehrdad, vous pourriez utiliser une fonction Lambda.

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

Answer 2

Selon ma machine, le tri d'un long long de [1..3000000] en utilisant la première méthode prend environ 4 secondes, tandis qu'en utilisant la deuxième méthode prend environ deux fois plus de temps. Cela veut dire quelque chose, évidemment, mais je ne comprends pas non plus pourquoi. Je pense simplement que cela pourrait être utile.

La même chose a été rapportée aquí .

Comme l'a dit Xeo, avec -O3 ils mettent à peu près le même temps pour finir.

Answer 3

TL;DR

Utilisez n'importe lequel. Ils sont presque identiques.

Réponse ennuyeuse

Comme d'habitude, il y a des avantages et des inconvénients.

Utilisez std::reverse_iterator :

• Lorsque vous triez des types personnalisés et que vous ne voulez pas mettre en œuvre operator>()
• Quand vous êtes trop paresseux pour taper std::greater<int>()

Utilisez std::greater quand :

• Lorsque vous voulez avoir un code plus explicite
• Lorsque vous voulez éviter d'utiliser d'obscurs itérateurs inversés

En ce qui concerne les performances, les deux méthodes sont aussi efficaces l'une que l'autre. J'ai essayé le benchmark suivant :

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

Avec cette ligne de commande :

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

<a href="http://coliru.stacked-crooked.com/a/74aa4e783d6d5a04" rel="noreferrer"><code>std::greater</code> demo</a> <a href="http://coliru.stacked-crooked.com/a/85b330d4d493edc9" rel="noreferrer"><code>std::reverse_iterator</code> demo</a>

Les timings sont les mêmes. Valgrind rapporte le même nombre de manquements au cache.

Answer 4

La première approche fait référence :

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

Vous pouvez utiliser la première approche parce qu'elle est plus efficace que la seconde.
La complexité temporelle de la première approche est inférieure à celle de la seconde.

Answer 5

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