std::map - key austauschen
-
*doppelpost*
-
life schrieb:
.filmor schrieb:
Optimizer schrieb:
Heap würde auch nicht sortieren - du bräuchtest aber eine Sortierung, um ein bestimmtes Element schnell zu finden.
Element finden geht auch in Heaps in O(log n) (weil's ja im Prinzip ein Binärbaum in linearem Speicher ist).
Nein, denn es ist zwar im Prinzip ein Binärbaum (zumindest der Binäre Heap), aber eben kein Suchbaum.
-
http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive/avl_set_multiset.html
Ich sehe keine map, aber man könnte hier ein pair reintun und nur nach dem key vergleichen.
-
Optimizer schrieb:
http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive/avl_set_multiset.html
Ich sehe keine map, aber man könnte hier ein pair reintun und nur nach dem key vergleichen.rbtree ist ein binaerer suchbaum
aber boost::intrusive ist hier ein genialer ansatz, da ich die nodes ploetzlich in der liste und im baum halten kann - ich habe dadurch eine enorm gute cache lokalitaet und kann alle nodes im voraus allokieren... muss nur die zeit finden es zu implementieren - aber auf der todo liste steht es schonmal oben
-
Und, hat's gerockt? Vielleicht brauche ich sowas auch mal...
-
Optimizer schrieb:
Und, hat's gerockt? Vielleicht brauche ich sowas auch mal...
wie koennte es anders sein: ich haenge am design fest.
ich will es moeglichst generisch machen, denn hardcoded rbtree und list zu vereinen waere uncool. und das wirft eine menge design entscheidungen auf und ich habe noch keinen schoenen weg gefunden.
das ist das privileg wenn man das als hobby projekt macht
ich wuenschte den luxus haette ich immer. aber dafuer dauert sowas triviales halt auch ein monat oder mehr 