Kennt jemand eine C/C++ Hash-Tabelle/Map-Implementierung, die nicht Speicher dynamisch zuordnen? Ich arbeite an einem eingebetteten System, das keine Standardbibliothek & keinen Heap hat (außer ich möchte einen schreiben/portieren).Hash-Tabelle/Map-Implementierung ohne dynamische Zuordnungen
Die Begriffe, nach denen Sie suchen, sind "Open Adressing" oder "Closed Hashing". Siehe http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables#Open_addressing und http://en.wikipedia.org/wiki/Open_addressing
keine spezifische Implementierung wissen Sie, though. Es tut uns leid.
Gute Links, aber sie könnten hilfreich sein. –
Tatsächlich haben mir die hübschen Bilder in diesem Artikel gezeigt, dass ich auch verketten kann, wenn ich eine Freelist aus einem Knotenspeicher (wahrscheinlich nur ein statisches Array) implementiert habe. Aber ich mag die Cache-Kohärenz der linear-sondierenden Open-Adressierung. –
Wäre es nicht einfacher, eine Heap-Zuweisungsimplementierung für Embedded als eine Hash/Map ohne dynamische Speicherzuweisung zu finden? – dtech
Wenn Sie den zugewiesenen Speicher immer in der genau entgegengesetzten Reihenfolge seiner Zuweisung freigeben können (z. B. 'allo a, b, c',' frei c, b, a'), kann Ihr Speicher/Heap-Manager so einfach sein wie einige Dutzende von Codezeilen, die eine Stapeldatenstruktur implementieren. –
Es _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ Und ein Stapelspeicher würde bedeuten, dass ich nicht in der Lage wäre, die Objekte außer Betrieb zu nehmen, was ein Problem sein könnte. –