std::set compare funktioniert nicht so recht



  • ich benutz nen std::set und will da drin eine menge von pointern auf disjunkte 3D punkte (grob) speichern.

    also hab ich mir eine eigene compare funktion gebaut:

    struct Vertex
    {
    	float x,y,z;
    	// konstruktoren und so krams
    };
    
    struct cmpVertex
    {
    	bool operator()(const Vertex *lhs, const Vertex *rhs)
    	{
    		return lhs->x < rhs->x || lhs->y < rhs->y || lhs->z < rhs->z;
    	}
    };
    

    und dem set übergeben:

    set<Vertex*, cmpVertex> vertices;
    

    eingefügt wird dann an anderer stelle:

    Vertex *A = new Vertex((*iter).A); // der iterator liefert die daten der punkte aus ner anderen liste, das funktioniert auch wunderbar
    vertices.insert(A);
    

    und so werden zwar einige doppelte punkte aussortiert (habs mit ner testmenge probiert), aber nicht alle.

    die vergleichsfunktion entspricht meiner ansicht nach der strict weak ordering anforderung.

    also dachte ich mir, vielleicht funkt mir float dazwischen, da man diese werte nicht einfach so vergleich kann und hab die vergleichsfunktion testweise umgeschrieben zu:

    struct cmpVertex
    {
    	bool operator()(const Vertex *lhs, const Vertex *rhs)
    	{
    		float t = 1e-3; // schwellwert
    		return fabs(lhs->x - rhs->x) > t || fabs(lhs->y - rhs->y) > t || fabs(lhs->z - rhs->z) > t;
    	}
    };
    

    aber das ergebnis ist immer noch murks.

    hab ich irgendwas offensichtliches übersehen?



  • Folgende zwei Punkte sind nach Deiner Sortierung äquivalent:

    (1, 2, 3) und (2, 1, 3)

    Weil 1 < 2 (1. Koordinate) ist der Vergleich links < rechts true.
    Weil 2 > 1 (2. Koordinate) ist der Vergleich rechts < links auch true.

    if (lhs->x < rhs->x) return true;
    else {
      if (lhs->y < rhs->y) return true;
      else
        return lhs->z < rhs->z;
    }
    

    Das wäre IMHO ein korrektes Strict Weak Ordering.



  • Nein, das ist keine strikt weak ordering - z.B. gilt sowohl (0,1,0)<(1,0,0) (l.x<r.y) als auch (1,0,0)<(0,1,0) (l.y<r.y). D.h. du müsstest nochmal zurück ans Zeichenbrett und deinen Vergleichsoperator nochmal überdenken.



  • ihr habt ja so recht *schäm* bastel mir nu aus den punkten sowas ähnliches wie nen hash und vergleich die. funzt exzellent.


Log in to reply