Container, um eindeutiges Mapping zu haben
-
Hi,
ich würde gerne einen Container nutzen, um basierend auf einer ID eine Struktur mit diversen Informationen zu erhalten. Jedes Mal das gleiche Problem...
Also map ist für mich nach wie vor das Intuitivste, aber davon wird ja ständig abgeraten (und ich kann mir einfach nicht merken, wieso). Ich habe nun ein set mit einer Struktur verwendet, jedoch kann ich da ja nichts drin finden, ohne dass ich find die gesamte Struktur überreiche. Das passt also hinten und vorne nicht, wenn ich nur die ID habe und den Rest suchen möchte. Und vector ist eigentlich auch unpraktisch, weil ich ja komplett durchiterieren muss oder eben eine binäre Suche anstellen (das sollte eigentlich auch gehen, weil das Vergleichskriterium eine hochzählende ID wäre).
Achso, ich sollte wohl noch dazu sagen, dass im Container ständig Elemente gelöscht werden, die IDs aber gültig bleiben sollen. Sonst hätte ich einfach einen vector mit Index als ID genutzt.
Kleiner Klaps auf den Hinterkopf würde mir sehr helfen, danke.
-
Für mich klingt das wie ein typischer Anwendungsfall für eine map.
-
Für mich auch, aber wann immer ich das denke, sagt irgendjemand "nutz lieber set oder vector". Auf die Begründung komme ich dann nie selbst (habe so was wie enormer Overhead und teilweise schlecht Cache-Lokalität im Kopf), aber wenn die mir hier erzählt wird, verstehe ich sie. Da ich wieder so einen Sachverhalt vermute, frage ich lieber nochmal nach.
-
Set und map sind da kein großer Unterschied, da eine map grob gesehen nicht viel mehr ist als ein set aus key-value-Paaren mit einem speziellen Komparator. In deinem Fall ist also die map einem set vorzuziehen.
Was bei set/map problematisch werden kann ist die Komplexität: So ein Ding zu iterieren heißt Pointergehüpfe, jedes Einfügen ist eine weitere Speicherallokation, jedes Löschen eine Speicherfreigabe, das ist aufwändig (könnte man durch einen eigenen Allokator verbessern).Eisflamme schrieb:
Ich habe nun ein set mit einer Struktur verwendet, jedoch kann ich da ja nichts drin finden, ohne dass ich find die gesamte Struktur überreiche.
Jein, wenn du dem set einen Komparator verpasst, der sich nur im die ID kümmert, dann raicht find eine Struktur, bei der nur die ID ausschlaggebend ist, der Rest ist dann egal.
Und vector ist eigentlich auch unpraktisch, weil ich ja komplett durchiterieren muss oder eben eine binäre Suche anstellen (das sollte eigentlich auch gehen, weil das Vergleichskriterium eine hochzählende ID wäre).
Achso, ich sollte wohl noch dazu sagen, dass im Container ständig Elemente gelöscht werden, die IDs aber gültig bleiben sollen. Sonst hätte ich einfach einen vector mit Index als ID genutzt.
Die Binäre Suche ist genau das was in der map auch im Grunde passiert, das ist nicht das Problem. Das ständige Löschen würde beim vector allerdings zu ständigem herumschieben der Elemente führen.
Was ich nicht ganz verstehe: wie soll die ID gültig bleiben, wenn das zugehörige Element nicht mehr existiert?
Was auch noch denkbar wäre: ein std::vector<std::pair<bool, Elem>>. Die Elemente nicht löschen, sondern nur das Flag umschießen. Die IDs entsprechen den Positionen im vector, das boolsche Flag bestimmt einfach, ob das Element gültig ist oder nicht.
Wenn du uns etwas genauer erzählst, was du erreichen willst, kann man dir bessere Tips geben...
-
Okay, danke, also set/map sind ähnlich/gleich vom Aufwand, der dahintersteckt, das kann ich mir vielleicht Mal merken.
Jein, wenn du dem set einen Komparator verpasst, der sich nur im die ID kümmert, dann raicht find eine Struktur, bei der nur die ID ausschlaggebend ist, der Rest ist dann egal.
Genau, wobei das darauf hinausläuft, dass ich entweder eine zusätzliche Dummy-Vergleichsstruktur bastle (unschön) oder meine normale Struktur mit ID und sonst Dummy-Parametern instanziiere (unschön). Ich finde das daher durchaus unschön, die Lesbarkeit des Codes profitiert nicht gerade davon, wie ich finde.
wie soll die ID gültig bleiben, wenn das zugehörige Element nicht mehr existiert?
Da habe ich mich unklar ausgedrückt. Ich meinte, dass beim Löschen die IDs anderer Elemente gültig bleiben sollten; das wäre bei einem vector ja nicht gegeben, wenn ich ID mit Index im Vector gleichsetzen würde.
Eine nicht-löschende Variante wäre möglich, wollte ich aber wegen unnötiger Speicherzumüllung nicht nutzen, wobei das eigentlich schon okay wäre.
Also ich bastle mir jetzt mittlerweile einen kleinen ThreadPool, der Handles ausschießen soll. Manche Arten von Threads (asynchrone Funktionsaufrufe nenne ich jetzt einfach auch Threads) sollen eben durch Flags gesteuert werden können. Jedes Handle entspricht einem Thread, aber das Flag wird über den Pool verwaltet, weil die Lebenszeit davon natürlich der des Threads entspricht, sodass der Pool das alles handlen soll.
Zusätzlich enthält die Struktur noch Daten darüber, ob der Thread erfolgreich beendet oder durch Abbruch beendet wurde, da dies nicht über den Signal/Slot-Mechanismus, den ich hier nutze, ersichtlich wird.
Meine Map wäre also <ThreadHandle, ThreadData>.
-
Also, ich nehme mal an, dass
(a) die Thread-Deskriptoren (die Flag-Sammlung) nicht besonders groß sein werden
(b) du nicht allzu viele Threads (also < 1000) gleichzeitig haben wirst
(c) die Deskriptoren trivial kopierbar sind (§9)
(d) die Threads auch grob in der gleichen Reihenfolge beendet werden, in der sie gestartet wurden, mit wenigen Ausnahmen.Ich würde dann die Deskriptoren in einem std::vector ablegen, und zwar aufsteigend nach Handle/ID sortiert. Löschen eines Deksriptors wäre dank (a,b,c) relativ billig, da das Aufrücken im vector ein simples memmove überschaubarer Größe wäre. Einfügen liefe einfach per pop_back, dank der aufsteigenden IDs auch gleich sortiert. Suchen wäre dann über binäre Suche auch billig.
Um unnötige Speicherallokationen zu vermeiden, kann man über ein reserve nachdenken, das eine typische Threadzahl vorreserviert. Dank (a) tut das bei Überschätzung nicht weh, dank (b) hat das bei Unterschätzung nicht allzu viele Neuallokationen zur Folge.
Wenn dir das memmove zu häufig kommt, ist eine Variante des vector<pair<bool,Descriptor>> denkbar: normales Löschen ist wie gehabt einfach flag umschießen. Dank (a) entsteht da jedesmal nur ein kleines Bisschen Datenmüll. Alle Nase lang sollte aber aufgeräumt werden. Dank (d) sind die ungültigen Deskriptoren zu größeren Blöcken zusammengefasst worden, es kann also mit einem erase (d.h. unter der Haube einem einzigen memmove) ein ganzer Haufen Müll entsorgt werden. (Hallo Garbage-Collector...)
-
Wow, danke.
Also d) gilt leider nicht wirklich, das kann kunterbunt werden und ist auch der Regelfall. Sonst ändert das nicht viel. Die ID würdest Du dann also mit in die Struktur packen, die im Vector ist?
-
Das ist ganz klar eine map oder ein set.
Set allerdings nur, wenn das "Dummyobjekt" für find() nicht zu Missbrauch einlädt. Also z.B. irgendwelche Klassen-Invarianten verletzt sind.