Wie sucht eine map einen bestimmten Key?

Ja, es gibt "Fallback" Operatoren für alle Typen.

Irgendwo existiert ein

template<class T>
bool operator==(T const& a1, T const& a2)
{
  return !(a1 < a2) && !(a2 < a1);
}

So werden verdammt viele Operatoren nachgebildet.

314159265358979

Du brauchst das doch nicht implementieren. Wenn du den operator < implementiert hast, benutzt die map diesen zum Vergleich. Mehr brauchst du nicht machen

Ethon__ schrieb:

template<class T>
bool operator==(T const& a1, T const& a2)
{
  return !(a1 < a2) && !(a2 < a1);
}

Das sieht mir aber nicht so effizient aus...

Bei mir müsste hierfür im Prinzip nur eine int id mit einer zweiten int id verglichen werden. Wäre es dann geschickter einen eigenen operator == () im Sinne von

bool operator == (  settings const & lhs, settings const & rhs )
{
	return lhs.get() == rhs.get();
}

zu implementieren um nicht unnötige aufrufe zu generieren?

Nexus

blublub schrieb:

Sortiren ja. Dafür implementiere ich ja operator<()
Aber wie find() ?

Binäre Suche mit dem gleichen Kriterium wie fürs Sortieren. Wenn im Sinne des Sortierkriteriums keine Äquivalenz vorliegt, wird der end() -Iterator zurückgegeben.

blublub schrieb:

Bei mir müsste hierfür im Prinzip nur eine int id mit einer zweiten int id verglichen werden. Wäre es dann geschickter einen eigenen operator == () im Sinne von [...] zu implementieren um nicht unnötige aufrufe zu generieren?

Nein, die std::map würde den operator== ignorieren. Und geschickter wäre es ohnehin nicht, weil du so die Äquivalenzbedingung ( == mit < ausgedrückt) kaputt machen könntest.

Möglicherweise suchst du aber einen anderen Container wie z.B. std::unordered_map . Allerdings sollte dafür der treibende Faktor die O(1)-Suche sein und sicher nicht die "ineffizienten" zusätzlichen arithmetischen Operationen für den Vergleich. Vergiss nicht, dass Hash-Maps auch was kosten (vor allem Speicher).

Das sieht mir aber nicht so effizient aus...

Bei mir müsste hierfür im Prinzip nur eine int id mit einer zweiten int id verglichen werden. Wäre es dann geschickter einen eigenen operator == () im Sinne von zu implementieren um nicht unnötige aufrufe zu generieren?

Macht prinzipiell Sinn, diese Fallbacks sind ja nur dazu da, nicht implementierte Operatoren nachzubauen.

Aber die Map interessiert sich wirklich nicht, die ist ja intern ein Suchbaum, da sieht das pseudomäßig etwa so aus:

Foo find(Node node, Bar key)
{
  if(key > node.key)
    return find(node.right, key);

  if(node.key > key)
    return find(node.left, key);

  return node.data;
}

Nexus schrieb:

... weil du so die Äquivalenzbedingung (== mit < ausgedrückt) kaputt machen könntest ...

Warum den das?
Ich vergleiche doch nur eine int variable und dieser Vergleich ist in jedem Fall richtig.

Bin jetzt total verwirrt.

Nexus

struct Elem
{
    int x;
};

bool operator< (Elem lhs, Elem rhs)
{
    return lhs.x < rhs.x;
}

bool operator== (Elem lhs, Elem rhs)
{
    return lhs.x == rhs.x - 5; // niemand hindert dich daran
}

int main()
{
    Elem a = {3}, b = {8};
    assert(a == b); // aha, sie sind gleich, also sicher auch äquivalent
    assert(!(a < b) && !(b < a)); // wtf, warum doch nicht?
}

Indem du sowohl operator< als auch operator== bereitstellst, baust du nur unnötige Fehlerquellen ein. operator< alleine reicht vollständig, da es nur um Äquivalenz (im Sinne des Sortierkriteriums) und nicht um Gleichheit geht.

Nexus schrieb:

bool operator== (Elem lhs, Elem rhs)
{
    return lhs.x == rhs.x - 5; // niemand hindert dich daran
}

Hmm.. das war mir noch gar nicht so in den Sinn gekommen. Ich dachte so etwas wäre ein Bug den man i. d. R. durch Unit Tests zurückverfolgen kann. Zumindest hindert mich ja auch keiner daran so etwas zu machen:

bool operator< (Elem lhs, Elem rhs)
{
    return lhs.x < rhs.x - 5;
}

Danke an alle Antwortenden für eure Hinweise

Michael E.

Was heißt Bug? Es kann durchaus manchmal gewollt sein, dass a == b nicht dasselbe ist wie !(a < b) && !(a > b) . Z.B. gibt NaN == NaN falsch zurück. Wenn du also operator== benutzen würdest, würdest du nie den NaN-Wert aus deiner map finden. Mit operator< findest du ihn aber.

Oder ein anderes (konstruiertes) Beispiel: Ich sage für zwei Mengen A und B, dass A < B genau dann gilt, wenn A weniger Elemente enthält als B. Ich sage aber nur A == B, wenn alle Elemente übereinstimmen (das brauch ich dann woanders im Programm). Wenn ich nun zu jedem Zeitpunkt nur die neueste Menge mit einer bestimmten Kardinalität haben will (ich lösche also alte Mengen mit derselben Kardinalität), kann ich sie in eine map stecken.

Mit ein wenig Bedenkzeit glaube ich mittlerweile auch dass nur ein operator< genügt solange der Profiler hier keinen Engpass meldet. Dazu käme ja noch eine weitere Testklasse, UML, Doku usw.

Nein das lohnt sich wirklich nicht.

Danke nochmal

Michael E. schrieb:

...

Gleich mal als PDF in die Wertvolle Tips liste einfügen

blublub schrieb:

Mit ein wenig Bedenkzeit glaube ich mittlerweile auch dass nur ein operator< genügt solange der Profiler hier keinen Engpass meldet. Dazu käme ja noch eine weitere Testklasse, UML, Doku usw.

Nein das lohnt sich wirklich nicht.

Danke nochmal

Wie bereits gesagt: In einem binären Suchbaum ist sowieso nur der operator< relevant, da eigentlich nur verglichen werden muss ob man in das linke o. rechte Kind absteigen muss, andernfalls wird der gespeicherte Wert zurückgegeben.