Wie Klasse "Point2D" in C++ Set speichern
-
Aus gegebenem Anlass:
Angenommen ich lese eine Menge an Punkten ein. Es können doppelte Punkte vorkommen und die Punkte werden in einer Klasse Point2D gespeichert. Einzige Attribute sind x und y als double.
Double vergleiche ich wie folgt:
template<class T> bool compareFloatingPoint(T first, T second, T epsilon = std::numeric_limits<T>::epsilon()) { return std::abs(first - second) < epsilon; }
Frage: Wie kann ich jetzt diese Punkte-Klasse in ein Set "inserten"? Hierfür ist ja der < Operator zu überladen. Nur wie überprüft das Set auf Gleicheit? Würde ggfs. einfach der == Operator genutzt werden, was Fehler in Kombination mit doubles verursachen kann?
-
Das wird so nicht funktionieren, weil die C++-Container verlangen, dass dein == transitiv ist: Wenn x == y und y == z ist, dann muss auch x == z sein.
Das funktioniert mit deiner Vergleichsfunktion aber nicht: Nimm z.b. epsilon = 0.1. Dann sind 1.00 und 1.08 äquivalent, und 1.08 und 1.16 sind auch äquivalent, aber 1.00 und 1.16 sind nicht mehr äquivalent.
Das ist nicht nur eine technische Formalität. std::set verhält sich (beim g++, aber bestimmt auch mit anderen Compilern) tatsächlich falsch, wenn == nicht transitiv ist.
Du müsstest dir also erstmal eine Vergleichsfunktion überlegen, die transitiv ist.
Zu deiner Frage: std::set u.ä. Container gehen davon aus, !(x < y) und !(y < x) impliziert, dass x == y ist (und sparen sich dadurch den Aufruf von ==). Du musst einen operator< bereitstellen, der das erfüllt. Insbesondere die Transitivität von == muss gelten, sonst wird dein Set sich weigern Punkte einzufügen, obwohl sie noch nicht drin sind, und ähnliche Fehler machen.
-
Rastlos schrieb:
Hierfür ist ja der < Operator zu überladen.
Nein, du kannst auch einen Funktor angeben.
Rastlos schrieb:
Nur wie überprüft das Set auf Gleicheit?
!(a<b) && !(b<a)
Rastlos schrieb:
Würde ggfs. einfach der == Operator genutzt werden, was Fehler in Kombination mit doubles verursachen kann?
Welchen "Fehler" soll == haben, den < nicht hat?