effizientes find_if in std::map
-
Hallöchen,
Ich bin grad am design einer Datenstruktur. Ich möchte Elemente in einer sortierten Reihenfolge ablegen und dynamisch weitere elemente hinzufügen.
Ich dachte dazu an std::map mit einem eigenen datentyp als key (also eigener compare-funktion).
Jedoch muss ich bevor ich ein Element einfüge noch eine Abfrage mit den Elementen ausführen zwischen denen das neue eingefügt werden würde.find_if mit einem entsprechenden prädikat würde mir die einfügeposition liefern, jedoch läuft find_if die map linear durch was deren Zweck etwas entfremdet.
Ich würde sowas wie binary_find_if benötigen, hat da jemand eine Idee dazu?lg
-
Wie sieht denn Dein Prädikat aus?
Eventuell kannst Du einfach map::lower_bound, map::upper_bound oder map::equal_range benutzen.
-
musst du die operation mit den nachbarn unbedingt vorher stattfinden? map.insert liefert sonst einen iterator mit dem du arbeiten könntest.
Ansonsten gilt wie immer: was willst du erreichen, nicht womit willst du es erreichen?
-
Das Problem ist ein geometrisches: ich habe eine Anzahl von normierten 3D-Vektoren (alle im Ursprung) und möchte eine Sortierung dieser Vektoren um eine Achse erreichen. Die Idee dazu war die Vektorenspitzen in die Ebene normal auf die Achse zu projizieren und dann gemäß dem Winkel zwischen Punkten in der Ebene die Sortierung vorzunehmen.
Dazu möchte ich die std::map dahingehend modifzieren dass ich direkt mit den 3D-Vektoren als Schlüssel arbeite, und das Prädikat den Winkelvergleich vornimmt.
Die Abfrage muss aber vorher stattfinden da es sozusagen "redundante" Vektoren gibt, die nicht eingefügt werden sollen, der Redundanztest muss aber nur an der Stelle geschehen wo das Element eingefügt werden soll.
-
Tja, man sollte doch mal lesen können.. hab map::lower_bound in der stl doku tatsächlich übersehen, das ist genau das wonach ich gesucht habe, danke!
-
Es geht bestimmt auch anders, vielelicht hilft ja: http://www.developia.de/developia/viewarticle.php?cid=31792 .
Dazu möchte ich die std::map dahingehend modifzieren dass ich direkt mit den 3D-Vektoren als Schlüssel arbeite
Warum nimmst du nicht gleich std::set?
Die Abfrage muss aber vorher stattfinden da es sozusagen "redundante" Vektoren gibt, die nicht eingefügt werden sollen, der Redundanztest muss aber nur an der Stelle geschehen wo das Element eingefügt werden soll.
Dazu muss keine std:: Datenstruktur modifiziert werden, kapsle es einfach.
-
knivil schrieb:
Es geht bestimmt auch anders, vielelicht hilft ja: http://www.developia.de/developia/viewarticle.php?cid=31792 .
Diese Art der Sortierung liefert mir leider nicht den Umlaufsinn der Vektoren um eine Achse (was ich aber benötige)
knivil schrieb:
Dazu möchte ich die std::map dahingehend modifzieren dass ich direkt mit den 3D-Vektoren als Schlüssel arbeite
Warum nimmst du nicht gleich std::set?
Weil ich noch zusätzliche Daten pro Vektor ablegen muss, die Vektoren dienen nur zur Sortierung.
knivil schrieb:
Die Abfrage muss aber vorher stattfinden da es sozusagen "redundante" Vektoren gibt, die nicht eingefügt werden sollen, der Redundanztest muss aber nur an der Stelle geschehen wo das Element eingefügt werden soll.
Dazu muss keine std:: Datenstruktur modifiziert werden, kapsle es einfach.
Da habe ich mich wohl falsch ausgedrückt, mit "modifizieren" meinte ich eine modifizierte, also gekapselte Version zu erstellen. std::map möchte ich nicht angreifen
