gibt es eine sortierte container Klasse in C++?

[countryclub2]

Gibt es eine container klasse, die O(log n) zugriff auf elemente bietet, O(log n) einfügen und O(1) löschen? Also quasi eine immer sortierte Liste?

[SeppJ]

Kommt drauf an, was du genau mit Löschen meinst. set und damit verwandte Datenstrukturen haben Einfügen und Zugriff in O(log N), und Löschen eines Iterators in konstanter Zeit. Wenn du aber erst einmal das zu löschende Element suchen musst, braucht das logischerweise vorher noch einen Zugriff in O(log N). Sortiert sind diese Container auch von Natur aus.

Ein unordered_set (und verwandte Container) hat sogar im Durchschnitt Einfügen in O(1), Löschen eines Iterators in O(1), Löschen eines noch zu suchenden Elementes in O(Anzahl dieser Elemente im Container), und Zugriff in O(1). Mit dem Nachteil, dass alles schlimmstenfalls auch mal O(N) dauern kann . Das ist dann aber, wie der Name schon sagt, nicht mehr sortiert.

[Finnegan]

@countryclub2 sagte in gibt es eine sortierte container Klasse in C++?:

Gibt es eine container klasse, die O(log n) zugriff auf elemente bietet, O(log n) einfügen und O(1) löschen? Also quasi eine immer sortierte Liste?

Auch auf die Gefahr hin, dass hier wieder ein "alter Bekannter" fragt :

std::map sollte diese Anforderungen erfüllen, bis auf dass Löschen bei dieser ebenfalls $\mathcal{O}(\log{} n)$ ist, da der Knoten im binären Suchbaum erst noch gefunden werden muss (wenn man über den Key löscht) und der Baum neu balanciert werden muss.

Eine fertige Datenstruktur, welche die Daten "sortiert" hält und Löschen mit $\mathcal{O}(1)$ ermöglicht, ist mir auf Anhieb nicht bekannt. In der Standardbibliothek gibt es die jedenfalls nicht. Man müsste eine solche Datenstruktur möglicherweise selbst implementieren. Das Problem ist hier vor allem, dass das neu Balancieren eines binären Suchbaums nach dem Löschen eines Knotens $\mathcal{O}(\log{} n)$ Schritte benötigt und Hash-Verfahren keine implizite Sortierung haben.

Eine spontane Idee wäre vielleicht Keys zu Knoten in einer Hash Map (mit $\mathcal{O}(1)$ Zugriff) parallel mitzuführen und beim Löschen die Knoten lediglich als "gelöscht" zu markieren. Wenn ein gewisser Schwellenwert an gelöschten Knoten erreicht ist, wird der Suchbaum komplett neu "konstruiert". Die Elemente des Suchbaums lassen sich in sortierter Reihenfolge in $\mathcal{O}(n)$ abfragen und wenn die Daten bereits sortiert vorliegen, kann man daraus einen (balancierten) binären Suchbaum in $\mathcal{O}(n)$ Schritten konstruieren. Damit sollte das Löschen amortisiert $\mathcal{O}(1)$ sein, wenn ich keinen Denkfehler habe.

Das wäre dann allerdings schon eine sehr spezielle Lösung für sehr spezielle Anforderungen. Wenn du einfach nur ne simple Datenstruktur aus der Standardbibliothek brauchst, dann nimm std::map und prüfe auch, ob nicht vielleicht wegen cpu-cache-freundlicheren Eigenschaften ein sortierter std::vector + Binäre Suche oder eine std::flat_map (C++23) eine bessere Lösung für dein Problem ist.

[countryclub2]

danke euch beiden

[Finnegan]

@SeppJ sagte in gibt es eine sortierte container Klasse in C++?:

Löschen eines Iterators in konstanter Zeit.

Ich dachte eigentlich immer, dass auch wenn man den Knoten nicht erst noch suchen muss, sich immer noch das Rebalancing mit $\mathcal{O}(\log{}n)$ niederschlägt. Auf cppreference sind die Iterator-basierten erase-Funktionen allerdings tatsächlich mit "Amortized constant" angegeben. Ich glaube da muss ich nochmal was recherchieren und meine Kenntnisse auffrischen

[SeppJ]

Da war ich ein bisschen ungenau, ja es ist O(1), mit gelegentlicher Möglichkeit O(log N) zu brauchen, aber so dass es im Durchschnitt immer noch O(1) ist. Das Rebalancing braucht man ja immer seltener, je größer N ist, so dass sich die gelegentlich längeren Laufzeiten im Durchschnitt weg heben.

[wob]

@countryclub2 sagte in gibt es eine sortierte container Klasse in C++?:

Gibt es eine container klasse, die O(log n) zugriff auf elemente bietet, O(log n) einfügen und O(1) löschen? Also quasi eine immer sortierte Liste?

Darf ich fragen, wo deine Anforderungen herkommen? Du scheinst ja zu erfordern, dass Löschen schneller sein soll als Zugriff. Hast du also eine große Menge an Dingen und willst oft etwas löschen? Gibt es vielleicht andere Möglichkeiten wie Filterkriterien zu bestimmen und deine Ursprungsliste einmalig zu filtern?

Neben den rein technischen Dingen wäre es für mich interessant, den Usecase zu verstehen. Meistens ist ja der schnelle Zugriff viel wichtiger als schnelles Löschen und ich hatte (glaube ich) noch nie den Fall, dass schnelles Löschen für mich wichtig war.