std::map - key austauschen

[.filmor]

Wenn du das letzte da machen willst, dann sind die *_heap-Funktionen der STL wahrscheinlich sauig praktisch. Ein Heap ist eh das „natürliche“ Pendant zur Map wenn die Größe fix ist.
Das ganze ist dann schneller und portabel und alle sind glücklich

[vlad_tepesch]

was verstehst du denn unter state?

ein allocator wird doch mit der map konstruiert und mit der map destructed.

simple ausgesprochen muss dein allokator doch nur folgendes machen:

constructor:
hohle bestimmte menge an speicher (kan zB über templateaargument festgelegt werden)
(der Speicher muss noch nicht mal mit new geholt werden, wenn du die maximale größe deiner map kennst

zb folgendes

template<class T, N>
class MyAlloc
{
  uint8 m_buf[N*sizeof(T)];   // keine ahnung, ob das mit dem N*sizeof(T) geht, falls nicht, dann doch dynamisch holen.
  // auf keinen fall sowas wie T m_buf[N]; schreiben, da für diese objekte der konstruktor aufgerudfen würde
}

//instanzierung der map würde dann in etwaso aussehen: 
map<keytype, valtype, MyAlloc<valtype, maxsize> > myFixMemPoolMap;

destruktor:
speicher freigeben, falls welchen geholt

allocate-funkion:
nachschauen, welche stelle frei ist und pointer daruaf geben:

deallocate-funktion:
die stelle, auf die der übergebene pointer zeigt, wieder als frei markieren

[.filmor]

Der Standard sagt

20.1.5/4 schrieb:

* All instances of a given allocator type are required to be interchangeable and always compare equal to each other.

Das gilt aber in der Tat nicht mehr, sobald man Member hat.

[Shade Of Mine]

Optimizer schrieb:

Für die map sollte so ein Allokator ohnehin nicht funktionieren, weil was die map allokiert ist nicht sizeof(pair), sondern sizeof(node).

Deshalb gibt es rebind...
Sonst waeren allokatoren ja komplett sinnlos.

Die Allokation und Deallokation, die du umgehen willst, ist O(1), das finden und einfügen O(log n). Wenn die Allokation trotzdem deine Laufzeit dominiert, hast du wahrscheinlich nicht viele Einträge. In diesem Fall ist es vielleicht besser, gleich einen sortierten vector<pair> zu verwenden. Bei wenigen Elementen ist das einfügen mit verschieben nicht teuer, finden geht in O(log n) und Allokationen hast du keine.

Das Problem ist, dass die lookup table einmal 5 und einmal 500000 eintraege hat. Und ich das vorher nie sagen kann. Ich kann jetzt natuerlich 2 oder 3 implementierungen liefern - aber das hier ist ein super Beispiel warum man nicht die O-Notation als alles bestimmendes kriterium nehmen darf.

Denn allokation ist zwar O(1) aber mit einer sehr hohen konstanten. Solche Probleme wie cache lokalitaet lassen wir mal komplett aussen vor - das kommt naemlich eigentlich auch noch dazu.

Die lookups ansich sind schon enorm schnell - vorallem da ich da auch sehr viel cache. eine hashmap koennte uU etwas speed bringen, aber das haengt dann eben von der hash funktion ab und da ist mir aktuell ein binaerer baum wegen dem besseren worst case lieber.

aktuell laeuft es ja auch mit der sinnlosen allokation und die performance ist tragbar, aber es gefaellt mir dennoch nicht. es waere viel sinnvoller wenn alle nodes in der selben page liegen wuerden, dann gaebe es deutlich weniger page faults.

@vlad_tepesch:
genau das ist aber nicht erlaubt. sobald ein allokator member variablen hat, ist es praktisch unmoeglich ihn portabel zu verwenden.

denn:

allocator_type alloc;

//folgendes muss aequivalent sein:
allocator_type().allocate(1);
alloc.allocate(1);

und das ist nicht garantierbar wenn alloc intern speicher verwaltet. man muss den speicher statisch machen und dann muss man synchronisieren und dann wird es teuer.

@filmor:
mhm, *_heap habe ich nicht bedacht. Mal ansehen. Mir ist aktuell unklar wie push_heap in O(log n) laufen kann - aber das laesst sich ja bald heraus finden. uU ist das genau die richtige loesung. mal sehen.

[Shade Of Mine]

ah, *_heap ist ziemlich genial - aber leider fuer mich nicht verwendbar da ich iteratoren auf die map brauche die nicht invalidieren.

[Gast]

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.

[.filmor]

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.

[life]

.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.

[life]

*doppelpost*

[Gast]

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.

[Gast]

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.

[Shade Of Mine]

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

[Gast]

Und, hat's gerockt? Vielleicht brauche ich sowas auch mal...

[Shade Of Mine]

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