Angenommen, ich habe einen Vektor von ganzen Zahlen:
std::vector<int> indices;
for (int i=0; i<15; i++) indices.push_back(i);
Dann sortiere ich es in absteigender Reihenfolge:
sort(indices.begin(), indices.end(), [](int first, int second) -> bool{return indices[first] > indices[second];})
for (int i=0; i<15; i++) printf("%i\n", indices[i]);
Dies ergibt Folgendes:
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
Jetzt möchte ich, dass die Zahlen 3, 4, 5 und 6 an das Ende verschoben werden und die absteigende Reihenfolge für sie beibehalten wird (vorzugsweise ohne sie zum sort
zweiten Mal verwenden zu müssen). Dh hier ist was ich will:
14
13
12
11
10
9
8
7
2
1
0
6
5
4
3
Wie soll ich die Vergleichsfunktion des ändern std::sort
, um dies zu erreichen?
return indices[first] > indices[second]
Meinst du nichtreturn first < second;
?std::greater
aus<functional>
kann anstelle des Lambda verwendet werden. In Bezug auf Ihre Frage ist es möglicherweise am einfachsten, einen ausführlicheren Vergleicher zu schreiben, der sicherstellt, dass Ihre Werte so vergleichen, wie Sie es möchten.return first > second
.Antworten:
Ihre Vergleichsfunktion ist falsch , da die Werte , die Sie erhalten , wie
first
undsecond
sind die Elemente derstd::vector
. Daher müssen sie nicht als Indizes verwendet werden. Sie müssen sich also ändernzu
Nun zu dem Problem, das Sie zu lösen versuchen ...
Sie können 3, 4, 5 und 6 aus dem Vergleich mit anderen Elementen herauslassen und sie trotzdem miteinander vergleichen:
Demo
quelle
Funktionen aus der Standard - Algorithmen - Bibliothek wie
iota
,sort
,find
,rotate
undcopy
würden das Leben leichter machen. Ihr Beispiel lautet:Ausgabe:
@TedLyngmo in den Kommentaren macht den guten Punkt, dass es verbessert werden könnte / sollte mit:
quelle
auto b = a + 4;
ist falsch (wenn Sie die Konsistenz mit dem vorherigen Snippet beibehalten möchten). Es sollte sein,auto b = a + 3;
weil in derstd::rotate
Sie verwendenb + 1
Lösung 1
Einfacher Ansatz mit einem nichtlinearen Komparator.
Lösung 2
Mit
std::algorithm
s (Partition)!Leistungsüberlegungen
Es kann so aussehen, als ob die zweite Lösung aufgrund des Overheads der Partition langsamer ist. Wahrscheinlich nicht, weil in modernen Prozessoren Cache- und Fehlverzweigungsvorhersagen vorliegen.
Benchmark
quelle
n <= 6 && 3 <= n
, was für die Ziel-CPU am besten funktioniert, damit Sie durch die Einführung der Zahlen 2 und 7 nichts als mögliche Verwirrung gewinnen - und warum anstelle einer Referenz einen Zeiger auf den Vektor verwenden?const
dem Leser nicht, dass die Funktion den Wert nicht ändert? In diesem speziellen Fall eines Einzeilers mag es klar sein, aber im Allgemeinen ist es nicht.