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?


Log in to reply