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

[icarus2]

MFK schrieb:

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

Da hast du recht, gibt natürlich keine totale Ordnung (ich nehme an das ist worauf du hinaus willst).

Dann halt die richtige Implementierung (wolte euch nicht meinen hässlichen Code an den Kopf werden ):

auto comp = [this](const std::pair<double,std::pair<K,K> > &lhs, const std::pair<double,std::pair<K,K> > &rhs)
        {
            const Mouse<int,K> &lhs_male = (*m_population.find(lhs.second.first)).second;
            const Mouse<int,K> &lhs_female = (*m_population.find(lhs.second.second)).second;
            const Mouse<int,K> &rhs_male = (*m_population.find(rhs.second.first)).second;
            const Mouse<int,K> &rhs_female = (*m_population.find(rhs.second.second)).second;

            RecombProbs<double> probs(m_simulation->ideotype().nof_genes()); // only a matrix containing probabilities
            double lhs_prob = prob(lhs_male.genome(), lhs_female.genome(), m_simulation->ideotype(), probs); // compute some probability
            double rhs_prob = prob(rhs_male.genome(), rhs_female.genome(), m_simulation->ideotype(), probs); // compute some probability

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

*Edit
Bitte fragt nach wenn ihr mehr zum Code wissen müsst. Ist mir durchaus bewusst, dass man nicht versteht was da genau gemacht wird.

[Caligulaminus]

icarus2 schrieb:

return lhs_prob >= rhs_prob || ...;

Bei Gleichwertigkeit liefert comp() true. Das darf nicht sein.

[icarus2]

Caligulaminus schrieb:

icarus2 schrieb:

return lhs_prob >= rhs_prob || ...;

Bei Gleichwertigkeit liefert comp() true. Das darf nicht sein.

Habe ich auch gerade gemerkt, es sollte

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

sein.

Habs probiert und jetzt klappt es auch. Vielen Dank für die Hilfe. Habe stundenlang den Fehler an der falschen Stelle gesucht...

[camper]

icarus2 schrieb:

Habe ich auch gerade gemerkt, es sollte

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

sein.

Das ist immer noch falsch. falls lhs_prob < rhs_prob und lhs.first < rhs.first sind comp(lhs,rhs) und comp(rhs,lhs) beide true.

[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?

[skalierbar]

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?