Problem mit std::pair, std::sort und Templates

icarus2

Tippfehler, ich wollte

return lhs_prob > rhs_prob || (lhs_prob == rhs_prob && lhs.first < rhs.first);

schreiben, dann müsste es stimmen.

hustbaer

MFK schrieb:

Eine Vergleichsfunktion, die immer true zurückgibt, erfüllt nicht die Anforderungen von std::sort. Insofern ist das Problem hausgemacht.

Wollte gerade widersprechen, aber du hast natürlich Recht.
Wenn dann müsste sie immer false zurückgeben - das wäre OK.

icarus2

Ich finde das Verhalten von std::sort ziemlich lustig.

Dass die Reihenfolge bei einer falschen Vergleichsfunktion verkehrt rauskommen kann ist klar. Aber dass Elemente verändert werden ist doch ziemlich speziell, das hätte ich nicht erwartet.

volkard

icarus2 schrieb:

Ich finde das Verhalten von std::sort ziemlich lustig.

Dass die Reihenfolge bei einer falschen Vergleichsfunktion verkehrt rauskommen kann ist klar. Aber dass Elemente verändert werden ist doch ziemlich speziell, das hätte ich nicht erwartet.

Ganz logisch: Für Quicksort und insertionsort braucht man in der inneren Schleife sowas wie

for(…;a[i]<a[j] and i>1;…) //oder and i<j oder so
   swap(a[i],a[j]);

und die Vergleiche auf i und j, also ob man aus dem gültigen Bereich rausrennt, kann man bleibenlassen, wenn der aktuell zu sortierende Bereich nach unten abgeschlossen ist durch ein Element, was garantiert <= aller Elemente im Bereich ist. Bei Quicksort (mit links-vor-rechts-Ausführung) muss man also nur immer den linken Teil geprüft machen und der rechte geht ungeprüft (und von einem ungeprüften Teil gehen sogar beide Kinder ungeprüft)).

Im op< dann zu schummeln führt direkt zu Schutzverletzungen bzw die vector-Elemente werden man auch in fremden Speicher vor dem vector sortiert.

Stichwort: Sentinel
Afair hat Sedgewick den in Quicksort bekannt gemacht, ich kann aber nicht nach Sedgewick Sentinel googlen.

icarus2

volkard schrieb:

[..]
und die Vergleiche auf i und j, also ob man aus dem gültigen Bereich rausrennt, kann man bleibenlassen, wenn der aktuell zu sortierende Bereich nach unten abgeschlossen ist [..]

Stimmt, jetzt ist es auch für mich logisch. Danke für die Erklärung.

Nexus

Tipp: Wenn du nach mehreren Kriterien lexikographisch sortieren willst, verzichte auf Basteleien mit logischen Operatoren. Wie du siehst, muss man genau nachdenken und macht trotzdem sehr schnell Fehler.

Stattdessen

return std::make_pair(lhs_prob, lhs.first) < std::make_pair(rhs_prob, rhs.first);

Mit std::make_tuple() skaliert der Vergleich wunderbar für beliebig viele Kriterien.

icarus2

Guter Tipp, das kannte ich nicht.

Vielen Dank!

Kellerautomat

Sollte man nicht eher std::tie verwenden?

Nexus schrieb:

Tipp: Wenn du nach mehreren Kriterien lexikographisch sortieren willst, verzichte auf Basteleien mit logischen Operatoren. Wie du siehst, muss man genau nachdenken und macht trotzdem sehr schnell Fehler.

Stattdessen
return std::make_pair(lhs_prob, lhs.first) < std::make_pair(rhs_prob, rhs.first);
Mit std::make_tuple() skaliert der Vergleich wunderbar für beliebig viele Kriterien.

Der Trick ist std::tie:

return std::tie(lhs_prob, lhs.first) < std::tie(rhs_prob, rhs.first);

Das skaliert noch viel besser als make_tuple, weil keine Kopien gemacht werden.

volkard

icarus2 schrieb:

Tippfehler, ich wollte
return lhs_prob > rhs_prob || (lhs_prob == rhs_prob && lhs.first < rhs.first);
schreiben, dann müsste es stimmen.

Lange Ausdrücke mit && oder || meide ich. Dann lieber mehrere ifs. Immer die zuerst, was sofort rausreturnen können, dann gibts auch keine riesigen Verschachtelingen.

Nexus

Danke für den Hinweis mit std::tie() . Bei std::make_tuple() zerfallen die Argumenttypen mittels std::decay , daher fällt die Referenz tatsächlich weg.

Wisst ihr auch, wie es z.B. hier aussieht?

void Function(std::pair<std::string, int> p);

Function(std::make_pair("string", 4)); // const char*, int

Das sollte meines Erachtens keine unnötigen Kopien erzeugen. Klar wird wegen der Konvertierung eine weggeworfen, aber es sollte nicht teurer sein als

Function(std::make_pair(std::string("string"), 4)); // std::string, int

oder

Function({"string", 4});

Jetzt nicht nur im Bezug auf den C++-Standard, sondern auch falls jemand weiss, wie gut aktuelle Compiler optimieren. Könnte ich bei Gelegenheit mal testen...

Columbo

Jetzt nicht nur im Bezug auf den C++-Standard

Dann kann ich ja den Anfang machen:

aber es sollte nicht teurer sein als [...]

Stimmt, da kann copy elision angewandt werden um sowohl die Temporary für den String als auch für den Rückgabewert zu elidieren.
Letztlich kommt es runter auf die Kopie der Zeichen im Stringliteral, oder?