V
snuggl3s schrieb:
Danke erst mal fuer die vielen Antworten. Ich glaube ich hab vergessen ein paar Randbedingungen zu erwaehnen. Die Mapping-Tabelle wird ueber eine sehr lange Zeit verwendet und ich bin sicher, dass es ueber kurz oder lang zu einem Ueberlauf der verwendeten Schluessel kommen wird und ich danach ueber einen "fragmentieren" Bereich nach freien ID's suchen muss. Eine sequentielle Suche ist daher nur beschraenkt moeglich.
dann würfle doch einfach. hast 32-bitter als IDs? und sagen wie mal 1000000 datensätze. dann haste beim würfeln ne cahce von 1 zu 4000, daß du nicht beim ersten wurf nen freie platz triffst. ist das nicht gut genug? und 1 zu 16000000, daß du auch beim zweiten mal nicht triffst.
Die map wird hauptsaechlich dazu verwendete gespeicherte Objekte anhand ihrer ID schnellstmoeglich zu finden.
dann nimm hash_map statt map.
An und fuer sich tut es ja. Ich war mir nur nicht sicher, ob es doch irgendeine "schoenere" Moeglichkeit gibt, nicht verwendete Schluessel aus der Map zu ziehen.
nicht aus der map. bei einer sehr vollen hashtable würde ich noch nen 4k großen stack (oder ringpuffer, falls ich freie IDs möglichst nicht sofort wiederverwenden will) der zuletzt freigegebenen IDs mitschleppen. bei 1 zu 4000 ist aber ein sicher benötigter plattenzugriff auf den stack vor dem vergeben der ID teurer, als einfach zu würfeln. sinds aber so viele zugriffe, daß der stack eh im ram bleibt, ist er schneller. worde hier aber keine überlegungen hinverschwenden, da O(1) in diesem fall nicht deutlich langsamer als O(1) ist und man eh erst duch ausmessen sehen kann, was besser ist und die messerei durchaus spät gemacht werden kann, weil du die ganze geschichte in eine klasse gewrapped hast, die eine hash_map enthält und deren schnittstelle zur verfügung stellt und dasüberhinaus die frage nach einer freien ID erlaubt (bzw ID als rückgabewert von "ID insert(Data d)" in einer überladung zu "void insert(ID i,Data d)" anbietet.)
