Sortierung einer Map

[Caligulaminus]

@wob Microsoft akzeptiert auch bidirektionale Iteratoren.
https://msdn.microsoft.com/de-de/library/z02ba27t.aspx

[wob]

@caligulaminus Boah, furchtbare Übersetzung, aber "schlimmste Fall ist O( n (Protokoll N ) 2)" (log = Protokoll, hahaha, selten so gelacht) soll wohl heißen, dass Microsoft dann nicht garantiert in N log N sortiert. Wobei list::sort angeblich "Approximately N log N comparisons, where N is the number of elements in the list.", also auch nur ungefähr. Ich dachte immer, dass man list::sort nimmt, weil man mit BiDis schlechter sortieren kann.

[Columbo]

Eine Option in diesem Fall (ebenfalls nach einem Teil des Werts sortieren) ist Boosts Bimap, die noch eine zweite Datenstruktur verwaltet, die Quasi als eine umgekehrte Map fungiert. Du wirst vielleicht einen Wrapper fuer den Value einsetzen muessen, ich sehe naemlich beim fluechtigen Ueberblicken der Referenz keinen Weg, einen eigenen value comparator einzusetzen.

[Skared]

@wob Die map brauche ich nur für die wxDataViewCtrl map. Die braucht als Key 1-MaxCount.

ich selbst brauche eigentlich nur eine liste die alle Objekte enthält.

@wob sagte in Sortierung einer Map:

Und das geht eben nur über einen Umweg

Könntest du mir den Umweg erläutern?

[firefly]

@skared sagte in Sortierung einer Map:

@wob Die map brauche ich nur für die wxDataViewCtrl map. Die braucht als Key 1-MaxCount.

ich selbst brauche eigentlich nur eine liste die alle Objekte enthält.

Du könntest einen pointer auf diese Objekte in einer zusätzlichen Container speichern, welche du dann nach deinen Kritieren sortierst.
Dadurch musst du aber zwei Container verwalten. z.b. Wenn du ein Element aus der map entfernst, muss das Element auch aus dem 2. Container entfernt werden.

[Skared]

Dann mache ich es via Liste wo die Objekte enthalten sind, sortiere diese Liste je nach bedarf und erstelle daraus die Map für das wxDataViewCtrl.

Vielen Dank an alle, somit ich meine Frage geklärt

Lg Skared

[wob]

@skared sagte in Sortierung einer Map:

@wob Die map brauche ich nur für die wxDataViewCtrl map. Die braucht als Key 1-MaxCount.

Das würde ich gern hinterfragen. Warum ist diese Map so aufgebaut? Warum wurde hier eine Map verwendet?

Zum Sortieren so ähnlich wie das hier:

std::map<int, string> m;
m[1] = "Welt"; m[2] = "Hallo";
std::vector<decltype(m)::value_type*> vit;
vit.reserve(m.size());
std::transform(m.begin(), m.end(), back_inserter(vit), [](auto& p){return &p;});
sort(vit.begin(), vit.end(), [](const auto &a, const auto &b){return a->second < b->second;});
for (auto &p: vit)cout << p->second << '\n';

[Skared]

@wob sagte in Sortierung einer Map:

Das würde ich gern hinterfragen. Warum ist diese Map so aufgebaut?

Es geht auch eine List. Vergiss das ich sagte das es eine map sein muss. Wurde schon geändert und läuft nun wunderbar

[hustbaer]

@skared sagte in Sortierung einer Map:

Es geht auch eine List.

Ich hoffe du meinst damit nen vector.

Kann es sein dass du aus dem Java Umfeld kommst? Oder woher die Liebe zu List? Ich meine, man nimmt aus gutem Grund in C++ kaum jemals std::list.

[Skared]

@hustbaer sagte in Sortierung einer Map:

Kann es sein dass du aus dem Java Umfeld kommst? Oder woher die Liebe zu List? Ich meine, man nimmt aus gutem Grund in C++ kaum jemals std::list.

Ja ich möchte mir jedoch auch einmal c++ anschauen.

Und zu deiner anderen Frage: ist es nicht schneller eine Liste zu bearbeiten(löschen/hinzufügen) als bei einem vector?

Lg Skared

[hustbaer]

@skared sagte in Sortierung einer Map:

Und zu deiner anderen Frage: ist es nicht schneller eine Liste zu bearbeiten(löschen/hinzufügen) als bei einem vector?

Wenn genug Einträge drinnen sind und/oder die Einträge teuer zu kopieren sind, dann geht das in einer Liste schneller, ja. Aber so Fälle hat man halt eher selten. Weswegen "die" default go-to List in Java ja auch die ArrayList ist (bzw. das Generic-Equivalent davon).

[SeppJ]

@skared sagte in Sortierung einer Map:

Und zu deiner anderen Frage: ist es nicht schneller eine Liste zu bearbeiten(löschen/hinzufügen) als bei einem vector?

Die List ist eher ein schönes Konzept für den Informatikunterricht, als eine praxistaugliche Datenstruktur. Das mag nicht immer so gewesen sein, aber heutzutage kommt ein Großteil der Geschwindigkeit eines Computers davon, dass sie wirklich gut darin geworden sind, vorauszusehen, was ein Programm in der nahen Zukunft machen wird. Lineare Datenstrukturen wie vector kommen dem sehr gelegen, wohingegen die list die Vorhersagen ziemlich kaputt macht. Der vector ist daher in so ziemlich jeder Situation schneller als die list, außer in den Gebieten, für die die list optimal ist (hauptsächlich Splicing und mittig Einfügen). Und selbst da ist bei kleinen Datenmengen der vector oft schneller. Besonders wenn man noch was anderes außer Splicing/Einfügen macht, weil alles außer Splicing/Einfügen beim vector viel schneller ist. Wenn man also nicht gerade große Datenmengen hat, auf denen man hauptsächlich die list-optimalen Operationen macht, dann ist list eine schlechte Wahl.

Das ist ein relativ seltenes Anwendungsszenario. Ein paar Fälle aus der fortgeschrittenen 3D-Grafikprogrammierung fallen mir ein, sonst ist mir noch nie etwas untergekommen, wo eine list wirklich gut war.

Das gilt natürlich auch für andere Sprachen, wobei das natürlich nicht an die Worte 'list' und 'vector' gebunden ist (die in anderen Sprachen manchmal eine andere Bedeutung haben), sondern an das Konzept der verketteten Liste gegen das lineare Array.

[wob]

@seppj sagte in Sortierung einer Map:

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)

[Ein ehemaliger Benutzer]

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.