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?
reverse_iterator
.std::sort(b, e);
setzt das Minimum aufb
(in unserem Fallrbegin
also das letzte Element) und das Maximum aufe
(in unserem Fallrend
also das erste Element).Antworten:
Eigentlich ist der erste eine schlechte Idee. Verwenden Sie entweder den zweiten oder diesen:
Auf diese Weise wird Ihr Code nicht stillschweigend unterbrochen, wenn jemand entscheidet,
numbers
ob er halten solllong
oderlong long
nichtint
.quelle
greater
als der andere?rbegin
undrend
wurden für einen bestimmten Zweck gemacht.std::greater<typename decltype(numbers)::value_type>()
oder so?std::greater<>()
seit C ++ 14 verwenden.Verwenden Sie die erste:
Es ist explizit, was los ist - weniger Wahrscheinlichkeit, falsch zu lesen
rbegin
alsbegin
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.
quelle
Mit c ++ 14 können Sie dies tun:
quelle
Was ist damit?
quelle
=
und+
ist nur an Komfort bedeutet ,∈
und∪
. In diesem FallO(n*log(n)) + O(n)
ist eine bequeme Notation, fürO(n*log(n)) ∪ O(n)
die die gleiche ist wieO(n*log(n))
. Das Wort "Berechnung" ist ein guter Vorschlag und Sie haben Recht mit dem Ton.Anstelle eines Funktors, wie Mehrdad vorgeschlagen hat, können Sie auch eine Lambda-Funktion verwenden.
quelle
Laut meiner Maschine
long long
dauert 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
-O3
sie ungefähr die gleiche Zeit, um fertig zu werden.quelle
reverse_iterator
danach, 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.base()
Member-Funktion gibt beispielsweise den umschlossenen Iterator zurück.std::vector<>::reverse_iterator
in Bezug auf implementiert wirdstd::reverse_iterator<>
. Bizarr; heute habe ich gelernt. :-PSie 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.
quelle
quelle
TL; DR
Verwenden Sie eine. Sie sind fast gleich.
Langweilige Antwort
Wie immer gibt es Vor- und Nachteile.
Verwendung
std::reverse_iterator
:operator>()
std::greater<int>()
Verwenden Sie,
std::greater
wenn:In Bezug auf die Leistung sind beide Methoden gleich effizient. Ich habe folgenden Benchmark ausprobiert:
Mit dieser Befehlszeile:
std::greater
demostd::reverse_iterator
demoTimings sind gleich. Valgrind meldet die gleiche Anzahl von Cache-Fehlern.
quelle
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:
quelle
std::greater
Komparators ...Sie können entweder den ersten verwenden oder den folgenden Code ausprobieren, der gleichermaßen effizient ist
quelle