Wie funktioniert die vergleichen Funktion std::map in C++ funktionieren, wenn es reflexiv wahr?

Ich habe eine Karte in meinem Projekt.
Jedes mal, wenn ich das einfügen ein neues element, ich will, um sicherzustellen, dass die Schlüssel für das neue element einzufügen ist, die mindestens eine minimale Breite, abgesehen von anderen Elementen in der map. Dazu schrieb ich eine benutzerdefinierte Klasse vergleichen wie diesem:

class PulseCompare
{
public:
    PulseCompare(int minwidth_):minwidth(minwidth_){};
    bool operator()(const int x, const int y) const {
        if(abs(x-y)>minwidth) return false;
        else return true;
    }
private:
    int minwidth;
};

erstellt und die Karte wie diese:

std::map<int,float,PulseCompare> pulsemap(PulseCompare(256));

und bevor ich ein element einzufügen verwende ich die map.find Methode wie diese:

if ( pulsemap.find(1600) == pulsemap.end() ) {
  //not found so I can insert
} else {
  //found
}

Aber das problem ist, dass wenn die Karte versucht reflexartig vergleichen mit den oben genannten vergleichen Funktion durch vertauschen der Werte von x und y, wäre es ein true für beide Fälle das in der Regel nicht der Fall mit den normalen Vergleichsoperatoren wie < und >

Auf dem cplusplus Dokumentation std::map::key_comp hier es sagt, und ich zitiere

Vergleich Objekt von einer map-Objekt wird festgelegt, auf Bau. Ihr Typ (Mitglied key_compare) ist das Dritte template-parameter der map-Vorlage. Standardmäßig ist dies ein Gegenstand weniger, das gibt das gleiche wie operator "<".

Dieses Objekt bestimmt die Reihenfolge der Elemente im container: es ist ein Funktionszeiger oder ein Objekt Funktion, die zwei Argumente des gleichen Typs wie die element-Tasten, und gibt true zurück, wenn das erste argument wird als zu gehen, bevor der zweite in der strict weak ordering definiert ist, und false sonst.

Beiden Schlüssel werden als gleichwertig angesehen, wenn key_comp gibt false zurück, reflexiv (D. H., egal, in welcher Reihenfolge die Schlüssel übergeben werden als Argumente).

Aber nicht sagen, über einen Fall, wo es reflexartig true. Kann mir jemand sagen, was sein Verhalten dann? Oder sollte ich dies tun, Intervall-Vergleich nur durch Iteration über die gesamte Karte?

Sie wollen wissen, was passiert, wenn a>b und b>a... Gott, ich hoffe, das Universum ist nicht kaputt
Ich bin mir nicht sicher, wie Sie Sie auch std::map<int,float> pulsemap(PulseCompare(256)); ist arbeiten
übergeben Sie den Gegenstand vergleichen, als constructor-argument
Könnten Sie bitte sagen, wie genau dein Beispiel hier, (Aktien den link) habe ich noch nie verwendet.
furchtbar Leid. nur klar, dass es war ein Tippfehler es. Ich hatte zu geben, vergleichen Sie die Klasse in der template-bevor ich es über den Streit. Ich bearbeitet jetzt. Ich denke, jetzt, es macht die Dinge klar.

InformationsquelleAutor Vivek V K | 2014-07-11

c++stdmap stl

4

Warum nicht einfach diese als Komparator?
```
return minwidth < (y - x);
```
Hier ist ein funktionierendes Beispiel: http://coliru.stacked-crooked.com/a/e115d3a2f6714773
- Bedenken habe ich 1700 bereits in ihm, und ich bin das einfügen von 1600, 1800.mit min-width 256 soll ich sagen 1600-1700 <256 und 1800-1700<256 deshalb brauche ich abs()
- Ihr Vergleich wird zweimal ausgeführt werden um zu überprüfen, für die Gleichstellung (einmal von jeder Seite). abs ist nicht erforderlich. Haben Sie haben versucht es?
- Ich bin nicht zu sagen über vertauschen von x und y in meine Komparator. Ich möchte das einfügen von element nicht vorhanden element plus-oder minus die minwidth. und brauche ich abs (), um beide Seiten der derzeitigen element. Bin ich darin einen Sinn? oder bin ich da falsch und nicht zu verstehen?
- Sie sind immer noch nicht zu verstehen. Die Vergleich-Funktion ist im wesentlichen ein "kleiner als" - operator. Karte rufen compare(a,b) um zu sehen, ob "a < b" und dann wird es call compare(b,a) um zu sehen, ob b < a. Sie halten zu schreiben versucht, eine Vergleich-Funktion, die prüft, "a = b", wenn alles, was Sie schreiben müssen, ist die Rückgabe "ein" < b".
- ja.. was sollte ich denken? Es ist so einfach. Vielen Dank. Dein code erklärt es am besten.
- Dies ist nicht eine strenge schwache Ordnung ist, so hat das gleiche problem wie Slava ' s Antwort.
InformationsquelleAutor Brandon
9
1. Den Komparator, der in std::map muss eine strenge schwache bestellen der Objekte.
2. Ihre Komparator nicht.
3. Daher, die Instanz von std::map produzieren zu undefiniertem Verhalten.
Hinweis: Es ist generell einfacher, einfach den Komparator bieten eine gesamte Bestellung.

Darüber hinaus lassen Sie uns beschreiben, was eine strenge schwache Bestellung erfordert. Hier mache ich Auszüge aus C++ 2011, Abschnitt 25.4.
- Sie gehen zu erstellen Funktor Compator comp; ich werde beziehen sich auf comp(lhs, rhs) eine Funktion, die einen booleschen Wert zurückgibt. Es ist hilfreich, daran zu denken, wie lhs < rhs.
- Wir erstellen eine Funktion equiv(lhs, rhs). Dieser ist definiert als (!comp(lhs, rhs) && !comp(rhs, lhs)). Also !(lhs < rhs) && !(rhs < lhs).
Sind wir verpflichtet, die folgenden Regeln halten:
```
comp(a, b) && comp(b, c) implies comp(a, c)
equiv(a, b) && equiv(b, c) implies equiv(a, c)
```
- ja, das macht Sinn. danke.
- Auch comp(a, b) impliziert !comp(b, a), und comp(a, a) ist falsch.
InformationsquelleAutor Bill Lynch
1

Eigentlich, wenn Sie schreiben Sie Ihre Komparator diese Weise sollte es funktionieren:
```
bool operator()(const int x, const int y) const {
    if(abs(x-y)<=minwidth) return false;
    else return x < y;
}
```
Und Sie brauchen nicht zu verwenden, bevor Sie einfügen, werden Sie doppelte Arbeit. Nur versuchen einzufügen, wenn eine solche Taste vorhanden ist, anzeigen abzulehnen, die insertion. std::map::insert gibt auch std::pair<iterator,bool> so können Sie überprüfen, ob die insertion erfolgreich war oder nicht.
- Unfortuately, diese Bediener nicht eine strenge schwache bestellen. Besonders schlecht, dass es scheinen zu arbeiten, für die meisten Werte, die eingesetzt in die Karte, aber es gibt ein paar Fälle, in denen die anzeigen brechen schlecht.
- können Sie mir ein Beispiel, wenn dies nicht gelingt?
- Legen Sie zwei Werte, die sich unterscheiden, von etwas mehr als minwidth, dann legen Sie einen Wert in der Mitte zwischen den beiden Werten (in minwidth von beiden). Dadurch erhalten Sie eine Karte, die zwei Werte vergleichen, die gleich durch den Komparator, und die Dinge gehen bergab von dort. Die details des Fehlers hängt von den internen details der Implementierung der std::map in Ihrer Bibliothek.
- Betrachten minwidth = 100. Ich stecken 100 ersten. dann 201, das ist kein problem. dann, wenn ich insert 150, dann wird der Komparator prüft, abs(100-150)<100? was wahr ist, so würde es auf false zurückgeben, sowohl die reflexive Fällen.Also die Karte würde davon ausgehen, 150~=100 und es kommen aus der Schleife denken, es ist das element gefunden. Es wird auch nicht begegnen, das nächste element 201. das gleiche gilt, wenn 201 festgestellt wird ersten. Was ist also das problem?
- Übernehmen eine einfache rot-schwarz-Baum. Legen Sie 100 zuerst, dann 201. Fügen Sie jetzt 150; es wird ersetzen Sie 100 und Sie haben 150 und 201 in der Struktur (zwei Werte innerhalb minwidth). Wenn das nicht schon schlimm genug, jetzt einfügen 225; er ersetzt die 150, dann einfügen 305; es ersetzt das 225. Nun suchen Sie für 201 und es wird scheitern, um es zu finden, wie es Aussehen wird, in der falsch-Zweig der Baum...
- Warum wird es ersetzt alles, wenn ich zu finden, bin mit map::find, bevor ich das einfügen? Es würde nur wird es nicht ersetzen, nur, wenn ich stecken Sie es direkt? wenn std::find etwas findet, wird es nie gehen Sie in das einfügen Verzweigung rechts?
- Ersetzt es jedes mal, wenn Sie anrufen legen Sie mit einem Wert vergleicht, als gleich zu einem vorhandenen Wert (operator() gibt false zurück, für beide (a,b) und (b,a)), ob Sie schon vorher genannt finden, ist irrelevant.
- die Annahme brandon beantworten, weil seine einfach und macht genau das, was ich will.Wir waren kompliziert die Dinge wirklich schlecht
- ersetzen Sie jederzeit aufrufen, einfügen, mit einem Wert, der verglichen als gleich" kann ich sehen, Verweis auf die Dokumentation, die nachweist, dass dieses Verhalten der "std::map'?
- es ist bis zu Ihnen, aber Chris' Beispiele scheint nicht korrekt zu sein.
- Es hängt davon ab, was Sie tun, in der else Teil. Wie lange, wie nie legen Sie einen Wert, der vergleicht, wie gleich zu einem vorhandenen Wert in der Karte, sollten Sie ok sein.
- Ich trat zurück, um Ihr Beispiel here. Lassen Sie uns die folgenden: map[100] = 10; map[101] = 15. Das Endergebnis ist eine Karte, die hat map[100] == 15, nicht map[101] == 15. Also in deinem Beispiel am Ende, die Karte wird nur über 2 Tasten in: {100, 201}
- So Ihr std::map Umsetzung ist anders. Versuchen Sie, die 101, dann 100, dann 201. Ihre Karte wird nur 101 und nicht 100 oder 201. Aber das zugrunde liegende problem ist, wenn Sie eine Vergleich-Funktion, die ist nicht schwach, um die Ergebnisse nicht definiert wird, so etwas passieren könnte
- Sie können nicht legen Sie einen Schlüssel, der vergleicht, als gleich in die Karte, es sei denn, es ist eine multimap. Mit multimap dieser Komparator mehrdeutig sein, für den regulären anzeigen sollte es ok sein.
- einfügen 101, dann 100, dann 201. Ihre Karte wird nur 101 und nicht 100 oder 201." Dies ist das erwartete Verhalten von OP.
- Ich Stimme mit einfügen 101, dann 100, dann 201, wird die Karte nur 101. AboveSie behauptet, dass das einfügen 100, dann 201, dann 150 Ergebnis wäre eine Karte mit {150, 201}. Aber das ist nicht das, was führen würde. Sie würden das Ergebnis mit einer Karte mit {100, 201}. Außerdem, ich Rede nicht über eine Umsetzung, ich spreche von den standard-Anforderungen für das Objekt.
- Für einige Implementierungen von std::map das ist das, was passieren könnte. Die der standard nicht spezifiziert, ob eine neu eingefügte Schlüssel, der vergleicht gleich einen alten Schlüssel ersetzt oder nicht. Es könnte davon abhängen, ob Sie std::map::insert oder std::map::operator[] zum einfügen neuer Werte. Der standard sagt nur seinen undefinierten Verhalten, so dass nichts passieren kann
- Der standard ist explicit über dieses Verhalten. Für std::map::operator[]. Abschnitt 23.4.4.3 Absatz 1: "Effekte: Wenn es keinen Schlüssel entspricht x in der Karte, Beilagen value_type(x, T()) in die Karte." Also, wir werden nicht überschreiben Sie die Taste gibt es. Und für std::map::insert, wir werden Auszug aus der Tabelle 102. "Fügt t, wenn und nur wenn es kein element in den container mit der Taste entspricht der Taste t."
InformationsquelleAutor Slava

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.