std::map - key austauschen
-
ah, *_heap ist ziemlich genial - aber leider fuer mich nicht verwendbar da ich iteratoren auf die map brauche die nicht invalidieren.
-
Heap würde auch nicht sortieren - du bräuchtest aber eine Sortierung, um ein bestimmtes Element schnell zu finden. Damit die Iteratoren nicht invalidieren brauchst du aber tatsächlich Node-Container. Sieh dir mal Boost.Intrusive an, dass sind Container, die die Elemente selber manipulieren um die Verkettung zu realisieren. Das gibt dir eine gute Kontrolle darüber, wie der Speicher verwaltet wird. Vielleicht ist da was brauchbares dabei.
-
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).
Shade Of Mine schrieb:
ah, *_heap ist ziemlich genial - aber leider fuer mich nicht verwendbar da ich iteratoren auf die map brauche die nicht invalidieren.
Das hamwa gern, wichtige Voraussetzungen zurückhalten
Aber wenn du eh sehr kleine Objekte da rumschiebst, kannst du dann statt der Iteratoren nicht einfach Kopien von denen halten?
Oder du könntest dir (da du den Heap ja sicher eh anständig kapseln willst) einen Heapiterator schreiben, der sich selbst schön valide hält (wenn Heap geändert, guckstu neu) oder einfach jedesmal das durchsteppen in Kauf nimmt.
-
.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.
-
*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 