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.

[hustbaer]

Mir fällt jetzt keine Anwendung ein, wo die Kombination aus O(log N) einfügen und O(1) löschen Sinn macht. Man kann nur so viel löschen, wie man eingefügt hat. Also O(log N) einfügen und löschen, oder O(1) einfügen und löschen. Letzteres kann man mit einer hash map haben. Und wenn nur selten iteriert werden muss, könnte es vielleicht OK sein einfach ad-hoc zu sortieren - weil die hash map ja nicht sortiert ist.

[SeppJ]

Forenerfahrung sagt XY-Problem. Oder eine leichte Abwandlung davon, wo man zwar eigentlich O(1) Einfügen möchte, aber denkt das wäre unmöglich, und daher schon vorauseilend nur nach O(log N) fragt.

[Finnegan]

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

Mir fällt jetzt keine Anwendung ein, wo die Kombination aus O(log N) einfügen und O(1) löschen Sinn macht. Man kann nur so viel löschen, wie man eingefügt hat. Also O(log N) einfügen und löschen, oder O(1) einfügen und löschen. Letzteres kann man mit einer hash map haben. Und wenn nur selten iteriert werden muss, könnte es vielleicht OK sein einfach ad-hoc zu sortieren - weil die hash map ja nicht sortiert ist.

Ich kann mir da auch nur was aus den Fingern saugen, wie ein System, bei dem nur das "aufräumen" (bzw. Löschen) in einem Prozess passiert, der z.B. Echtzeitanforderungen zu erfüllen hat. Dann wären aber auch alle "amortisiert O(1)"-Lösungen hinfällig und man würde für eine so spezielle Anforderung eh etwas eigenes bauen - zumal da auch noch einiges an Synchronisation nötig wäre.

Ich denke auch wie @SeppJ sagt ein XY-Problem oder eine Übungsaufgabe, bei der es vornehmlich darum geht, sich eben solche Gedanken zu machen. Oder O(1) ist gar nicht wirklich wichtig und die Antwort lautet schlicht std::map

[Columbo]

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

Mir fällt jetzt keine Anwendung ein, wo die Kombination aus O(log N) einfügen und O(1) löschen Sinn macht.

In der Komplexitaetstheorie wird man die bestmoeglichen Laufzeiten fuer eine gegebene Datenstruktur erreichen wollen um bestimmte bounds einzuhalten (siehe bspw. Fibonacci Heaps fuer Dijkstra Komplexitaet). Da wir hier in einem C++ Kontext sind wird das nicht die Motivation des TEs sein, aber trotzdem erwaehnenswert.

Man kann einfach stumpf O(N * log N) als bauen eines flat-sets betrachten, d.h. N mal in ein Array inserieren und am Ende (oder laufend) sortieren, dann ist das loeschen trivial O(1), und zwar worst-case. Klingt aber irgendwie unsinnig und ich stimme bzgl. X/Y zu.

[hustbaer]

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

Man kann einfach stumpf O(N * log N) als bauen eines flat-sets betrachten, d.h. N mal in ein Array inserieren und am Ende (oder laufend) sortieren, dann ist das loeschen trivial O(1), und zwar worst-case. Klingt aber irgendwie unsinnig und ich stimme bzgl. X/Y zu.

Verstehe ich nicht ganz. Wie soll das Löschen dabei O(1) sein? Man muss dann ja alle Elemente die danach (oder davor) kommen verschieben. Also O(N). Es sei denn man markiert das Element nur als gelöscht. Das geht aber mit jeder Datenstruktur. Und wie gesagt: ich frage mich wozu man das brauchen würde.

[*john 0]

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

Verstehe ich nicht ganz. Wie soll das Löschen dabei O(1) sein? Man muss dann ja alle Elemente die danach (oder davor) kommen verschieben. Also O(N).

Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1). Was die O-Notation so gerne unterschlägt ist die Konstante, die man für die Durchführung benötigt. Sprich Dein O(N) ist wahrscheinlich schneller als das O(1) Löschen in einem anderem Fall.

[Columbo]

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

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

Man kann einfach stumpf O(N * log N) als bauen eines flat-sets betrachten, d.h. N mal in ein Array inserieren und am Ende (oder laufend) sortieren, dann ist das loeschen trivial O(1), und zwar worst-case. Klingt aber irgendwie unsinnig und ich stimme bzgl. X/Y zu.

Verstehe ich nicht ganz. Wie soll das Löschen dabei O(1) sein? Man muss dann ja alle Elemente die danach (oder davor) kommen verschieben. Also O(N). Es sei denn man markiert das Element nur als gelöscht. Das geht aber mit jeder Datenstruktur. Und wie gesagt: ich frage mich wozu man das brauchen würde.

Ich hab die Frage falsch verstanden. Ich dachte es geht hier nur um delete-min (das waere einfach pop_*). Offensichtlich funktioniert ein flat-set auch nicht fuer worst-case O(log n) insertion.

Das geht aber mit jeder Datenstruktur.

Mit trees schiebst Du das rebalancing auf, womit Du dann wiederum die insertion Komplexitaet beeinflusst.

Die andere Frage waere ob das loeschen per key oder per Iterator passiert, weil man natuerlich das Element praktisch nie in worst-case O(1) finden kann. Da kaeme ehestens eine hash map in Frage.

[Quiche Lorraine]

@john-0 sagte in gibt es eine sortierte container Klasse in C++?:

Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1).

Ausbalancierten Bäume?

[SeppJ]

@Quiche-Lorraine sagte in gibt es eine sortierte container Klasse in C++?:

@john-0 sagte in gibt es eine sortierte container Klasse in C++?:

Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1).

Ausbalancierten Bäume?

Immer noch O(1), amortisiert eben.

[Finnegan]

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

@Quiche-Lorraine sagte in gibt es eine sortierte container Klasse in C++?:

@john-0 sagte in gibt es eine sortierte container Klasse in C++?:

Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1).

Ausbalancierten Bäume?

Immer noch O(1), amortisiert eben.

Im englischen Wikipedia-Artikel zum Rot-Schwarz-Baum ist die Argumentation, dass Rebalancing nach Löschen höchstens 3 Rotationen benötigt, das umfärben der Knoten sich aber im Worst Case bis zur Wurzel fortpflanzen kann ($\log n$). Dazu heisst es dort:

The loop is where the problem of rebalancing is escalated $\displaystyle \Delta h=1$ level higher in the tree in that the parent P becomes the new current node N. So it takes maximally h iterations to repair the tree (where h is the height of the tree). Because the probability of escalation decreases exponentially with each iteration the total rebalancing cost is constant on average, indeed amortized constant.

Das ist vielleicht eine interessante Hintergrundinformation. Ich kratze mich zwar gerade noch am Kopf, weshalb die Wahrscheinlichkeit exponentiell abnimmt, aber wenn das gilt, ist amortisiert $\mathcal O(1)$ nachvollziehbar (muss noch etwas draufstarren, es sind dort alle möglichen Konfigurationen in einer Ebene aufgelistet und werden behandelt).

[hustbaer]

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

Ich hab die Frage falsch verstanden.

Oder auch nicht. Fest steht: wir haben die Frage unterschiedlich verstanden