Sortierung einer Map

wob

sonst ist mir noch nie etwas untergekommen, wo eine list wirklich gut war.

Ich kenne noch den Fall, dass in einer Liste parallel möglichst schnell gelöscht/eingefügt werden soll. Jedes List-Element hat in diesem Anwendungsfall neben den "Nutzdaten" noch einen Mutex. Man braucht dann nur die entsprechenden Elemente locken, die man bearbeiten will (bzw. beim Löschen muss man auch den Vorgänger und Nachfolger locken, da man deren Zeiger umbiegt. Dies ist aber ein äußerst spezialisierter Anwendungsfall (HFT-Bereich), bei dem es auf jede ns ankommt. Im Normalfall ist vector eine gute Wahl (und es gibt ja auch noch deque, das man gerne mal übersieht)

Es gibt einen dritten Template-Parameter für std::map bei dem du angeben kannst, ob auf- oder absteigend sortiert werden soll.

SeppJ

@wob sagte in Sortierung einer Map:

(und es gibt ja auch noch deque, das man gerne mal übersieht)

Die oft auch das gleiche Problem wie list hat. Gutes theoretisches Konzept, aber die nicht-Lokalität der Daten tötet die Performance in der Praxis. Man muss wieder einen Fall haben, bei dem man oft die Stärken der deque bedient, aber eher selten "normal" mit den Daten arbeitet, damit die deque besser als vector wird. Wobei der Performanceunterschied hier weit weniger krass ist, als bei list vs. vector.

DocShoe

@seppj
Das hat mich bei std::deque auch gewundert. Jeder Knoten ist in meiner Implementation 16 Bytes(!) groß, d.h. bei großen Datentypen verhält sich das Ding wie std::list. Ich fände es gut, wenn man da irgendeine Granularität angeben könnte, dann wäre das echt nützlich.

hustbaer

Naja im Gegensatz zu std::list hat man trotzdem noch effizienten random access, und im Gegensatz zu std::vector hat man effizientes push_back und push_front.

Aber ja, die Page-Size angeben zu können wäre sehr praktisch. Ich verwende daher manchmal die Deque aus der Boost. Da kann man die Page-Size zwar auch nicht angeben, aber sie ist unabhängig vom Compiler und wesentlich grösser als 16 Byte.

Columbo

Die Pagesize soll 16 Byte sein? War die nicht mal 8KB oder so?

DocShoe

Dinkumware64 sagt:

#define _DEQUESIZ (sizeof (value_type) <= 1 ? 16
: sizeof (value_type) <= 2 ? 8
: sizeof (value_type) <= 4 ? 4
: sizeof (value_type) <= 8 ? 2
: 1) /* elements per block (a power of 2) */

hustbaer

@Columbo Wir reden hier von der Pagesize der Deque, nicht von der der CPU/MMU. Und 8kB bei der Deque wäre schon ziemlich krass. Die Klasse kann ja dummerweise nicht wissen ob die Instanz die man gerade erzeugt/befüllt die eine grosse Deque in dem Programm ist wo es wörscht wäre 8kB oder sogar 8MB zu verschwenden, oder ob es trillionen Instanzen geben wird und jedes Byte zählt.

Columbo

@hustbaer Mir war schon klar, wovon wir sprechen. Ich habe immer angenommen, die waere im Kilobyte Bereich. Mit 16 Byte hat man davon ja quasi ueberhaupt nichts.

SeppJ

@columbo sagte in Sortierung einer Map:

@hustbaer Mir war schon klar, wovon wir sprechen. Ich habe immer angenommen, die waere im Kilobyte Bereich. Mit 16 Byte hat man davon ja quasi ueberhaupt nichts.

Was dann, wie schon gesagt, genau meine Beobachtung zu deque in der Praxis ist. Man sagt immer, deque wäre beim Wachsen dem vector überlegen. Aber sofern man nur hinten anfügt ist der Unterschied so klein, dass man ihn sofort wieder eingebüßt hat, sofern man über die Daten auch nur ein oder zwei Mal iteriert.

Beim vorne Anfügen ist die deque natürlich haushoch überlegen, aber das ist halt ein recht seltener Anwendungsfall. Meistens wird sich für deque entschieden, weil in irgendwelchen Ratschlägen steht, dass sie bei wildem Wachstum nach Hinten so gut wäre. Der Unterschied ist in der Praxis jedoch nichtig.

(Gemessen habe ich dies das letzte Mal vor geschätzt 3 Jahren. Vermutlich wird mit neuen Computern der vector ein noch besserer Default sein)