Ich suche nach einer C ++ - Implementierung einer Datenstruktur (oder einer Kombination von Datenstrukturen), die die folgenden Kriterien erfüllen:
O(log(n)) Komplexität O(log(n)) complexity O(log(n)) complexity Vielen Dank im Voraus für Anregungen
Dalibor
(Bearbeiten) Antworten:
Die von mir gewählte Antwort beschreibt eine Datenstruktur, die alle diese Anforderungen erfüllt. Boost :: multi_index, wie von Maxim Yegorushkin vorgeschlagen, bietet jedoch sehr ähnliche Funktionen.
(Bearbeiten) Einige der Anforderungen wurden nicht korrekt angegeben. Sie sind nach korrektur (: original)
modifiziert(Bearbeiten) Ich habe eine Implementierung der in der angenommenen Antwort beschriebenen Datenstruktur gefunden. Bis jetzt funktioniert es wie erwartet. Es heißt Counter-Struktur
(Bearbeiten) Ziehen Sie in Betracht, das von sp2danny vorgeschlagene AVL-Array zu verwenden.
Gehen wir durch diese ...
- Die durchschnittliche Suchzeit für Elemente ist im schlimmsten Fall die Komplexität von O (log (n))
- Entfernen / Einfügen von Elementen macht zuvor erhaltene Iteratoren nicht ungültig.
- ermöglicht das Einfügen und Entfernen von Elementen im schlimmsten Fall O (log (n)) Komplexität
Das schreit ziemlich "Baum".
- bietet einen Direktzugriffs-Iterator (zusammen mit dem Iterator-Vergleich & lt;, & gt;)
- Bei einem Iterator kann ich die Ordinalposition des Objekts ermitteln, auf das im Container verwiesen wird, im schlimmsten Fall von O (log (n)) complexity
- Elemente werden in der gleichen Reihenfolge durchlaufen, in der sie dem Container hinzugefügt wurden
Ich gehe davon aus, dass der Index, den Sie für den Direktzugriffs-Iterator bereitstellen, in der Reihenfolge der Einfügung ist, also wäre [0] das älteste Element im Container, [1] wäre das nächstälteste usw. bedeutet, dass der Iterator intern den Index nicht speichern kann, da er sich ohne vorherige Benachrichtigung ändern kann, damit die Iteratoren gültig sind. Also einfach mit map mit dem Schlüssel zu arbeiten, der die Reihenfolge der Insertion nicht funktioniert.
Jeder Knoten in Ihrem Baum muss zusätzlich zu seinen üblichen Mitgliedern die Anzahl der Elemente in jedem Teilbaum verfolgen. Dies ermöglicht einen wahlfreien Zugriff mit O(log(N)) time. Ich kenne keinen fertigen Code, aber die Unterklassen std::rb_tree und std::rb_node wären mein Ausgangspunkt.
Basierend auf Ihren Anforderungen macht boost::multi_index mit zwei Indizes den Trick.
Der erste Index ist geordneter Index . Es ermöglicht O (log (n)) einfügen / suchen / entfernen. Der zweite Index ist Direktzugriffsindex . Es ermöglicht einen wahlfreien Zugriff und die Elemente werden in der Reihenfolge des Einfügens gespeichert. Für beide Indizes werden Iteratoren nicht ungültig gemacht, wenn andere Elemente entfernt werden. Die Konvertierung von einem Iterator in einen anderen ist O (1) Operation.
Siehe hier: STL-Container (scrollen Sie auf der Seite nach unten, um Informationen zur algorithmischen Komplexität zu erhalten), und ich denke, std::deque entspricht Ihren Anforderungen.
Hier ist mein "lv" -Container, der die Anforderung erfüllt, O (log n) einzufügen / löschen / Zugriffszeit. Ссылка
Der Container ist nur Header-C ++ - Bibliotheken, und hat den gleichen Iterator und funktioniert mit anderen C ++ - Containern wie Liste und Vektor.
Der"lv" -Behälter basiert auf dem rb-Baum, wobei jeder Knoten einen Größenwert über die Anzahl der Knoten in dem Unterbaum hat. Durch Überprüfung der Größe des linken / rechten Kinds eines Baumes können wir schnell auf den Knoten zugreifen.
Tags und Links c++ data-structures complexity-theory iterator