Ich bin auf der Suche nach einer C++ - Container-Klasse, die wie ein std::vector indiziert ist, hat aber schnelle Einfügungen, Löschungen und Indizierung. Eine vector Schnittstelle, die mit einem zugrunde liegenden Balancing-Baum implementiert wurde, würde beispielsweise O (logN) -Einfügungen/Löschungen und O (logN) -Indexierung aufweisen.Container mit schnellen Einsätzen und Index?
Um klar zu sein: Ich bin nicht auf der Suche nach std::map<int, T>. Das Einfügen eines Elements bei Index N sollte Indizes aller nachfolgenden Elemente im Array erhöhen, was bei std::map<int, T> nicht der Fall wäre.
Ich habe AVL Array gefunden, die genau das tut, was ich suche. Es hat die richtige Schnittstelle, aber ich würde gerne sehen, ob es andere Möglichkeiten gibt.
Kennen Sie weitere (Produktionsqualitäts-) Implementierungen? Vielleicht etwas beliebter (hat Boost etwas von der Sorte?). Etwas mit einem kleineren Speicherbedarf? (Ein Knoten, der einen Zeiger im AVL-Array enthält, hat auf meinem Computer 64 Bytes.)
können Sie erarbeiten, warum Sie den Direktzugriff benötigen? – BeyelerStudios
Dies scheint off-topic zu sein - auf der Suche nach Software/Bibliothek Empfehlungen. –
Ich glaube nicht, dass es eine einfachere (in Bezug auf die Datenstruktur) Sache, die tut, was Sie wollen, so dass es 2 ptrs für nächste/vorherige und 3 ptrs für Eltern/links/rechts plus den ursprünglichen Zeiger benötigt. Insgesamt sind 6 Zeiger = 48 Bytes für 64-Bit-Umgebungen. Das ist das Mindeste, was man in Bezug auf den Speicherbedarf erreichen kann (denke ich). – mostruash