Qualcuno sa di un'implementazione tabella/mappa hash C/C++ che non ha allocare dinamicamente memoria? Sto lavorando su un sistema embedded che non ha una libreria standard & senza heap (a meno che non voglia scrivere/portarne uno).Implementazione tabella/mappa hash senza allocazioni dinamiche
I termini che stai cercando sono "Open affrontare" o "hashing chiuso". Vedi http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables#Open_addressing e http://en.wikipedia.org/wiki/Open_addressing
Non so una specifica implementazione, però. Scusate.
Buoni collegamenti, tuttavia, potrebbero essere utili. –
In realtà, le belle foto di quell'articolo mi hanno fatto capire, potrei anche fare concatenamento se implementassi una lista freelide da un archivio di nodi (probabilmente solo una matrice statica). Ma mi piace la coerenza di cache dell'indirizzamento aperto a scansione lineare. –
Non sarebbe più facile trovare un'implementazione di allocazione dell'heap per embedded rispetto a una hash/mappa senza allocazione dinamica della memoria? – dtech
Se è sempre possibile liberare la memoria allocata nell'ordine esatto opposto della sua allocazione (ad esempio 'alloc a, b, c',' free c, b, a'), il gestore di memoria/heap può essere semplice come pochi dozzina di linee di codice che implementano una struttura di dati dello stack. –
È molto più semplice implementare un heap, ma se questa è l'unica cosa di cui ho bisogno, potrebbe non esserlo. E una memoria di stack significa che non sarei in grado di rimuovere gli articoli in ordine, il che potrebbe essere un problema. –