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

icarus2

In meinem Programm habe ich Mäuse, die eine ID vom Typ K haben, wobei K ein Template-Parameter ist (ich instanziere K als int ).

Das Mapping von ID zu Maus wird wie folgt in einer Klasse Foo gespeichert:

std::map<K,Mouse<int,K>> m_population;

Ich habe anschliessend folgende Funktion (die Vergleichsfunktion ist so natürlich nicht sinnvoll aber sie genügt, um das Problem aufzuzeigen):

template <typename K>
void Foo<K>::foo()
{
    std::vector<std::pair<double,std::pair<K,K>>> value_pairs;

    // do something with value_pairs
    // all id's in value_pairs are in m_population

    auto comp = [this](const std::pair<double,std::pair<K,K>> &lhs, const std::pair<double,std::pair<K,K>> &rhs)
        {
            assert( m_population.find(lhs.second.first) != m_population.end() ); // this assertion fails
            assert( m_population.find(lhs.second.second) != m_population.end() );
            assert( m_population.find(rhs.second.first) != m_population.end() );
            assert( m_population.find(rhs.second.second) != m_population.end() );

            return true;
        };

    std::sort(value_pairs.begin(), value_pairs.end(), comp);
}

In value_pairs speichere ich bloss irgend einen Wert zu jedem Paar von IDs (ist nicht wichtig was dieser Wert bedeutet). Bevor ich std::sort aufrufe existieren alle IDs in value_pairs .

Das Problem ist nun, dass die erste Assertion nicht hält, denn lhs.second.first (eine Maus-ID) hat den Wert 0, aber alle IDs sind positiv. Wenn ich lhs ausgebe, dann erhalte ich (0,(0,0)).

Das merkwürdge ist nun folgendes: Wenn ich in der Vergleichsfunktion anstatt true einfach false zurückgebe, dann tritt der Fehler nicht auf. Das heisst das Problem sind wohl die Vertauschungen, die std::sort ausführt.

Hat irgend jemand eine Idee woran das liegen könnte? Ich habe den Verdacht, dass bei einer Vertschauschung einfach Default-Werte gesetzt werden und nicht richtig vertauscht wird. Verstehe allerdings nicht wie das passieren kann.

PS:
Sorry für den schwachen Titel aber mir ist wirklich nix besseres eingefallen

MFK

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

volkard

Wenn ich mich recht erinnere, darfste (sogar nach C++-Standard) sort eh nicht mit einem Vergleicher aufrufen, der schummelt, also widersprüchlich ist.
Sonst könnte man sort innendrin gar nicht schlau programmieren/optimieren.

return false; geht, dann sind halt für Dich alle Werte gleich.
Aber return true; kann nicht sein, es kann nicht a<b und zugleich b<a sein.

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?

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?