std::set der Container der Wahl

[mekakic]

Ich möchte eine Datenstruktur, die mit den Werten 1...65536 vorinitialisiert ist (beispielsweise). In diesem Bereich kommen dann Anfragen mit einem bestimmten Wert und der soll dann aus der Datenstruktur rausgestrichen werden. D.h. das set sollte nur noch verfügbare Werte beinhalten und mit der Zeit leerer werden. Dazwischen soll dann immer besondere Anfragen kommen, die den kleinsten noch verfügbaren Wert im set bekommen. Als drittes soll der kleinste gemeinsame Wert aus zwei parallelen Sets bestimmt werden -- also im Prinzip eine Schnittmenge, wobei immer nur der kleinste noch verfügbare Wert interessiert.

Ist das set hier bereits die richtige Datenstruktur für mich? Insbesondere das Vorinitalisieren ist etwas lästig, da man die Werte wohl erstmal alle einzelnd reinlegen muß, bevor man sie rausstreichen kann. Gibt es da vielleicht einen schnellen Weg? Bei der Schnittmenge denke ich, dass es wohl einfacher ist die verfügbaren Werte der Reihe nach zu iterieren bis zwei gleiche dabei sind, vorallem da die Unterschiede nicht massiv sind, wird dies in den meisten Fällen wohl am Schnellsten sein.

[Gast]

Aus deiner Aufgabe kann ich nicht erkennen, wozu du ein Set benötigst. Wo ist eine Set-Operation? Der kleinste Wert zweier Mengen ist nicht über die Schnittmenge zu erhalten.

Nimm einen std::vector und fertig. Wenn es nicht auf Performance ankommt, dann legst du alle Werte mit einer kleinen for-loop an beginnend mit dem Wert 1.

init:


std::vector<int> v;

for (int i = 1; i <= 65536; ++i) {
v.push_back(i);
}



remove: Laufzeit O(1)


int valueToRemove = 100;

v[valueToRemove - 1] = -1;



find min: Laufzeit O(n)


int min = -1;

for (int i = 0; i < 65536; ++i) {
if (v[i] != -1) {
min = v[i];
break;
}
}


Den Vergleich des kleinsten Wertes zweier Mengen, wirst du ja selbst hinbekommen.

[Gnafoo]

Ich sollte genauer lesen X-(. Hat schon alles der Gast gesagt.

Man könnte sich allerdings noch den minimalen Index != -1 zusätzlich zum vector merken. Dann geht min auch in konstanter Zeit.

[Gast]

Machs doch umgekehrt:
Merk dir in einem Set, welche Anfragen schon kamen.

Dann hast du:

init: 0

remove: je nach Set

Minimum finden: O(n) - wobei es Sinn machen würde, sich Zwischenergebnisse zu merken

Man gewinnt also bei Initialisierung und (imho) Übersichtlichkeit des Programms.

[maximAL]

Ich seh nicht, inwiefern ein Vector hier sinnvoller als ein Set sein soll. Er mag zwar Speichereffizienter und schneller zu befüllen sein, aber die Suche ist lahm und letztendlich ist er einfach nur unelegant.
Natürlich wäre ein HashSet eigentlich noch besser als ein Set, aber das gehört ja blöderweise nicht zum Standard...

[Aquaschaf]

Naja, die Problembeschreibung ist etwas zu ungenau um zu sagen was du brauchst:

- Sind die Mengen aus denen du Werte entfernst beliebig, oder sind es immer zusammenhängende Zahlenfolgen wie in deinem Beispiel?
- Werden alle Mengen mit dem gleichen Inhalt initialisiert?
- Entfernt die Operation mit der du zwischendurch den kleinsten Wert aus einer Menge zurückgibst den Wert gleichzeitig daraus?

Natürlich wäre ein HashSet eigentlich noch besser als ein Set, aber das gehört ja blöderweise nicht zum Standard...

Wie wärs mit boost::unordered_set ;)

[Coda]

Ja, entweder das oder std::tr1::unordered_set (gibt's bei GCC und Microsoft).

Ich würde das aber gleich auf std::unordered_set typedefen, dann braucht man irgendwann nur den boost- mit dem Standard-Header ersetzen.

[DocEW]

Noch ein Vorschlag:

Zwei int-Arrays, mit 0 initialisiert.
Streichen von i entspricht array[i]++.
Drei "Merker": In beiden arrays einen für das kleinste Element sowie einen für das kleinste Element, was in beiden Sets vorkommt.

Beim Streichen werden die "Merker" aktualisiert (einfach per Schleife zum nächst größeren hochlaufen, was die jeweiligen Bedingungen erfüllt).

Dann läuft alles außer Streichen in O(1). Und beim Streichen werden pro Programmlauf alle Elemente auch nur konstant oft angefasst, da der Wert aller "Merker" monoton wächst.

Hoffe ich hab nix übersehen. =)

[Gast]

Ich seh nicht, inwiefern ein Vector hier sinnvoller als ein Set sein soll. Er mag zwar Speichereffizienter und schneller zu befüllen sein, aber die Suche ist lahm und letztendlich ist er einfach nur unelegant.
Natürlich wäre ein HashSet eigentlich noch besser als ein Set, aber das gehört ja blöderweise nicht zum Standard...

Ein Set ist ja eigentlich nur ein ADT. Ein HashSet ist die mögliche Implementierung eines Sets. Eine weitere Implementierung eines Sets kann ein TreeSet sein.

[zgep]

ähnlich DocEWs Vorschlag:
zwei bool-Arrays mit Größe 65536 (oder whatever), initialisiert mit true
wenn ein Wert aus einem Array gestrichen wird: ArrayN[Value-1] = false;
kleinster Wert beide:unsigned int i;
for(i = 0; !(Array1[i] && Array2[i]); ++i);
return i;kleinster Wert von einem ist wohl einfach genug...

Nachteile: Speicherbedarf wird durch streichen nicht geringer, nur für sets gleicher Größe und gleichem Inhalt (bei Initialisierung) anwendbar

mfg,
zgep

[zgep]

schwerer Bug:
hab vergessen, dass bei meinem Code der Index bei leeren Arrays bis irgendwohin laufen würde, wo er nix verloren hat... . Bitte um Vergebung ;)

mfg,
zgep