Gibt es eine solche Struktur in der C ++ - Standardbibliothek? Ich habe keinen Zugang zu etwas anderem, also kann unordered_map in tr1 nicht verwendet werden (und boost etc).
Was ich habe, ist eine große Anzahl von benutzerdefinierten Klassenelementen 100000+, die ich speichern muss und auf die ich sehr schnell auf O (1) zugreifen kann. Ich kann keine Arrays / Vektoren verwenden, da die Elemente zufällig gespeichert werden und ich die Position des Elements nicht kenne.
Ist meine einzige Alternative, eine eigene hashmap-Implementierung mit nur der C ++ - Standardbibliothek zu implementieren?
Das Problem ist, dass die O (1) -Lookup nicht Standard ist. Ich bin mir nicht sicher, was Boost hat, aber einige STL-Implementierungen (wie sgi) haben hash_map. Das brauchst du.
Hier ist die Dokumentation .
Probieren Sie es einfach aus:
%Vor%Denken Sie daran, wenn das funktioniert, ist es nicht tragbar ... aber vielleicht ist das jetzt in Ordnung, und später können Sie Workarounds finden.
Wenn Sie wirklich auf std:: beschränkt sind und nichts anderes verwenden können, ist std::map Ihre beste Wahl. Dies gibt Ihnen nur logarithmische Nachschlagezeit, nicht konstante, aber im Vergleich zu Arrays / Vektoren wird es blitzschnell sein. Auch ich denke, für nur 100000 Elemente wird die logarithmische Suche schnell genug sein und Sie werden nicht viel gewinnen, wenn Sie eine Hash-Tabelle verwenden.
Es besteht die Möglichkeit, dass Ihre Implementierung bereits eine Implementierung der Hash-Tabelle enthält. Wenn std::map wirklich nicht schnell genug ist, versuchen Sie
oder
%Vor%oder sogar
%Vor% Warum kannst du Boost nicht benutzen? Die Sammlungsbibliothek Unsortiert ist "Nur Kopfzeile", was bedeutet, dass Sie keine haben Boosts BJam-Build-Prozess und Installer einholen. Sie könnten einfach die .hpp -Dateien greifen und sie zu Ihrem Projekt hinzufügen.
hash_map ist Teil der SGI-Erweiterung der STL. In GCC können Sie es verwenden, indem Sie Folgendes tun; Ich weiß nichts über andere Implementierungen:
unordered_map ist Teil des TR1. In GCC können Sie es verwenden, indem Sie Folgendes tun; Ich weiß nichts über andere Implementierungen:
Standard-AWL im aktuellen Standard hat keine (1) Nachschlage-Container.
Sie können den Container unordered_map verwenden. Es ist in tr1 und wird im nächsten vollen Standard sein. Visual Studio hat eine Implementierung in & lt; unordered_map & gt; Die und Dokumentation kann hier gefunden werden: Ссылка
Tags und Links c++ performance data-structures