Warum brauch std::map nur less?

BorisDieKlinge

glaub ehr das std::less "<" dafür da ist um die elemente in std::map stortiert abzulegen.. gleiche elemente darf std::map nicht enthalten..

HumeSikkins

black knight schrieb:

Wieso braucht die map kein == Operator?
Wenn ich z.B. map.find(suche) mache wird das dann so gemacht?
if( !(suche < element) && !(element < suche)) -> == -> gefunden

Genaugenommen: !map.key_compare()(suche, element) && !map.key_compare(element, suche). Für den Default-Fall key_compare() == std::less, resultiert das aber ziemlich genau in dem Code, den du angegeben hast.

Eine Map verwendet also nicht Gleichheit (==) sondern "Äquivalenz im Sinne der Sortierreihenfolge" um zu prüfen, ob zwei Element gleich sind. Das gilt übrigens nicht nur für map, sondern für alle sortierten Container (set, multimap, ...) und ale Algorithmen, die auf sortierten Sequenzen arbeiten (std::lower_bound,...).

BorisDieKlinge schrieb:

gleiche elemente darf std::map nicht enthalten..

Klar, aber bei "find" will ich ja ein gleiches finden.

Konrad Rudolph

Die map braucht kein ==, weil < ausreicht, um die Gleichheit abzubilden, wenn es eine gültige Metrik ist. Dann gilt nämlich folgendes:

T a, b;

assert( ( a == b )   ==   (not (a < b) and not (b < a)) );

/EDIT: Hmm … 'false and false' … ergibt 'false'. Code korrigiert.
/EDIT2: Mist, steht ja bereits korrekt im ersten Posting.

Krux

um auf gleichheit zu testen, muss der operator nicht überladen werden, es wird standardmäßig immer auf binäre gleichheit geprüft. Den operator == muss man nur dann überladen, wenn das Objekt Speicher auf dem Heap reserviert (mit new).

Konrad Rudolph

Krux schrieb:

um auf gleichheit zu testen, muss der operator nicht überladen werden, es wird standardmäßig immer auf binäre gleichheit geprüft.

Was meinst Du mit binäre Gleichheit? Bit-für-Bit-Gleichheit?

Falls Du das meinst: nein, das ist falsch.

Konrad Rudolph

Um nochmal auf die Frage zu antworten: Map braucht nur less, weil die Datenstruktur als Binärbaum implementiert ist. Um ein Element zu finden, wird folgender Pseudocode verwendet:

node find_node(node n, value v) {
    if (n == null_ptr) return null_ptr;
    if (v < n->value) return find_node(n->left_child, v);
    if (n->value < v) return find_node(n->right_child, v);
    return n;
}

// Der Aufruf lautet dann natürlich:
find_node(tree->root, v);

lolz

Wenn du dich dafür interressiert, wie man mit op< die ganzen anderen Vergleichsoperatoren abbildet, dann schau dir mal die Implementierung von Boost.Operators an.

finix

Nochmal ein Stichwort zur Ausgangsfrage:

http://de.wikipedia.org/wiki/Strenge_schwache_Ordnung

hustbaer

Was die STL angeht ist wohl eher der Link angebracht: http://www.sgi.com/tech/stl/StrictWeakOrdering.html
EDIT: Er. Ok, nicht "eher" sondern zusätzlich - der erklärt nicht *warum* ein "less" pedicate ausreichend ist bzw. was "strict weak ordering" bedeutet /EDIT

Krux

Konrad Rudolph schrieb:

Krux schrieb:

um auf gleichheit zu testen, muss der operator nicht überladen werden, es wird standardmäßig immer auf binäre gleichheit geprüft.

Was meinst Du mit binäre Gleichheit? Bit-für-Bit-Gleichheit?

Falls Du das meinst: nein, das ist falsch.

sorry, mein fehler, hab da was mit dem standardkopierkonstruktor verwechselt gehabt. Der == operator ist standardmäßig nicht verfügbar.