Sortieren eines Vektors in absteigender Reihenfolge

310

Sollte ich es benutzen

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

oder

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

einen Vektor in absteigender Reihenfolge sortieren? Gibt es Vor- oder Nachteile bei dem einen oder anderen Ansatz?

Fredoverflow
quelle
2
+1 Ich denke, die Antwort liegt auf der Hand, aber diese Frage hat ein interessantes Trivium. :)
wilhelmtell
3
Ich würde für die erste Option stimmen, nur weil ich mich dann nie mit ihnen befassen muss reverse_iterator.
Evandrix
2
@wilhelmtell Eine Noob-Frage, aber warum sollte die zweite in absteigender Reihenfolge sortieren? Wir geben das gleiche Array als Eingabe für die Sortiermethode. Es ist nur so, dass wir es in umgekehrter Reihenfolge geben. Warum sollte es also in absteigender und nicht in aufsteigender Reihenfolge sortiert werden, wie dies bei ar.begin () und ar.end der Fall wäre?
Shshnk
6
@shshnk std::sort(b, e);setzt das Minimum auf b(in unserem Fall rbeginalso das letzte Element) und das Maximum auf e(in unserem Fall rendalso das erste Element).
Fredoverflow

Antworten:

114

Eigentlich ist der erste eine schlechte Idee. Verwenden Sie entweder den zweiten oder diesen:

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

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

Auf diese Weise wird Ihr Code nicht stillschweigend unterbrochen, wenn jemand entscheidet, numbersob er halten soll longoder long longnicht int.

user541686
quelle
1
@FredOverflow: Sie haben die Ehre in Ihrem Kommentar
getan
2
Oder bleib beim ersten. Verwenden Sie ein typedef für den numberContainer - eine gute Idee, damit jemand zu lange tauschen kann - und schreiben Sie: std :: sort (numbers.begin (), numbers.end (), std :: major <numContainer :: value_type> ( ));
RichardHowells
1
+1 Der erste ist wirklich verwirrend. Was ist greaterals der andere? rbeginund rendwurden für einen bestimmten Zweck gemacht.
Abhishek Divekar
6
Warum nicht einfach std::greater<typename decltype(numbers)::value_type>()oder so?
Einpoklum
1
Diese Antwort ist veraltet - Sie können sie std::greater<>()seit C ++ 14 verwenden.
Nikolai
70

Verwenden Sie die erste:

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

Es ist explizit, was los ist - weniger Wahrscheinlichkeit, falsch zu lesen rbeginalsbegin auch mit einem Kommentar. Es ist klar und lesbar, was genau Sie wollen.

Aufgrund der Art der umgekehrten Iteratoren ist der zweite möglicherweise weniger effizient als der erste, obwohl Sie ihn zur Sicherheit profilieren müssten.

Pubby
quelle
68

Mit c ++ 14 können Sie dies tun:

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

Was ist damit?

std::sort(numbers.begin(), numbers.end());
std::reverse(numbers.begin(), numbers.end());
Shoumikhin
quelle
13
Ein Grund könnte sein, die zusätzliche Komplexität zu vermeiden: O (n * log (n)) + O (n) gegen O (n * log (n))
Greg
32
@ aggreg O (n * log (n)) = O (n * log (n) + n). Es gibt zwei Möglichkeiten, dieselbe Menge zu definieren. Sie wollen sagen "Das könnte langsamer sein."
pjvandehaar
4
@pjvandehaar Greg geht es gut. Er sagte ausdrücklich nicht O (n * log (n) + n), er sagte O (n * log (n)) + O (n). Sie haben Recht, dass sein Wortlaut unklar ist (insbesondere sein Missbrauch des Wortes Komplexität), aber Sie hätten freundlicher antworten können. Beispiel: Vielleicht wollten Sie das Wort "Berechnung" anstelle des Wortes "Komplexität" verwenden. Das Umkehren der Zahlen ist ein unnötiger O (n) -Schritt zu einem ansonsten identischen O (n * log (n)) - Schritt.
Ofek Gila
3
@OfekGila Mein Verständnis ist , dass Big-O - Notation über Sätze von Funktionen ist, und Notation beteiligt =und +ist nur an Komfort bedeutet , und . In diesem Fall O(n*log(n)) + O(n)ist eine bequeme Notation, für O(n*log(n)) ∪ O(n)die die gleiche ist wie O(n*log(n)). Das Wort "Berechnung" ist ein guter Vorschlag und Sie haben Recht mit dem Ton.
pjvandehaar
22

Anstelle eines Funktors, wie Mehrdad vorgeschlagen hat, können Sie auch eine Lambda-Funktion verwenden.

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

Laut meiner Maschine long longdauert das Sortieren eines Vektors von [1..3000000] mit der ersten Methode ungefähr 4 Sekunden, während das Verwenden der zweiten Methode ungefähr doppelt so lange dauert. Das sagt natürlich etwas aus, aber ich verstehe auch nicht warum. Denken Sie nur, das wäre hilfreich.

Das Gleiche wurde hier berichtet .

Wie von Xeo gesagt, verwenden -O3sie ungefähr die gleiche Zeit, um fertig zu werden.

zw324
quelle
12
Haben Sie vielleicht nicht mit aktivierten Optimierungen kompiliert? Klingt sehr reverse_iteratordanach, als wären die Operationen nicht inline, und da sie nur ein Wrapper um die eigentlichen Iteratoren sind, ist es kein Wunder, dass sie die doppelte Zeit ohne Inlining benötigen.
Xeo
@Xeo Auch wenn sie inline waren, verwenden einige Implementierungen einen Zusatz pro Dereferenzierung.
Pubby
@ildjarn: Weil es so ist? Die base()Member-Funktion gibt beispielsweise den umschlossenen Iterator zurück.
Xeo
1
@Xeo Jetzt sind beide in einer Sekunde fertig. Vielen Dank!
zw324
3
@Xeo: Ich nehme es zurück; Der Standard schreibt tatsächlich vor, dass std::vector<>::reverse_iteratorin Bezug auf implementiert wird std::reverse_iterator<>. Bizarr; heute habe ich gelernt. :-P
ildjarn
11

Der erste Ansatz bezieht sich auf:

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

Sie können den ersten Ansatz verwenden, weil Sie effizienter als der zweite sind.
Die Zeitkomplexität des ersten Ansatzes ist geringer als die des zweiten.

Hautausschläge
quelle
Dies ist die gleiche Antwort wie die von mrexciting. Die Bemerkung zur Komplexität ist mir ebenfalls unklar.
Philipp Claßen
7
bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);

quelle
4
Um eine gültige Antwort zu erhalten, sollten Sie überlegen, etwas über die Vor- und Nachteile Ihrer Erwähnungsmethoden gegenüber den OP-Methoden zu
schreiben
3

TL; DR

Verwenden Sie eine. Sie sind fast gleich.

Langweilige Antwort

Wie immer gibt es Vor- und Nachteile.

Verwendung std::reverse_iterator:

  • Wenn Sie benutzerdefinierte Typen sortieren und diese nicht implementieren möchten operator>()
  • Wenn Sie zu faul zum Tippen sind std::greater<int>()

Verwenden Sie, std::greaterwenn:

  • Wenn Sie expliziteren Code haben möchten
  • Wenn Sie die Verwendung obskurer Reverse-Iteratoren vermeiden möchten

In Bezug auf die Leistung sind beide Methoden gleich effizient. Ich habe folgenden Benchmark ausprobiert:

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

Mit dieser Befehlszeile:

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 sind gleich. Valgrind meldet die gleiche Anzahl von Cache-Fehlern.

ivaigult
quelle
2

Ich denke nicht, dass Sie eine der Methoden in der Frage verwenden sollten, da beide verwirrend sind und die zweite fragil ist, wie Mehrdad vorschlägt.

Ich würde Folgendes befürworten, da es wie eine Standardbibliotheksfunktion aussieht und seine Absicht klar macht:

#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>());
}
Martin Broadhurst
quelle
2
Das ist tausendmal verwirrender als nur die Verwendung des std::greaterKomparators ...
Apollys unterstützt Monica
@Apollys Ich stimme zu, dass ab C ++ 14 std :: Greater <> wie die bevorzugte Lösung aussieht. Wenn Sie nicht über C ++ 14 verfügen, kann es dennoch nützlich sein, wenn Sie Überraschungen mit std :: Greater <int> ausschließen möchten (z. B. wenn sich die Typen irgendwann von int zu long ändern).
Philipp Claßen
2

Sie können entweder den ersten verwenden oder den folgenden Code ausprobieren, der gleichermaßen effizient ist

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