std::map mit Einfuegereihenfolge ?

[Eric Cartman]

Hallo.
Ich brauche eine map mit strings als Schluessel und Zeiger als Werte, die der Reihenfolge des Einfuegens geordnet sind - laesst sich sowas ohne Zweitcontainer (wie einen vector) regeln?
Im Moment benutze ich unordered_map - aber hier ist keinerlei Reihenfolge garantiert, oder?

[Zagatho_zero87]

Nein, unordered_map ist nicht geordnet.
Warum nimmst du nicht eine std::map oder std::multimap ?

[gamer8o4]

Im Moment benutze ich unordered_map - aber hier ist keinerlei Reihenfolge garantiert, oder?

also soweit ich weiß heißt unordered in dem fall, dass die elemente nicht geordnet werden, also in der reihenfolge des einfügens bleiben.
ohne mehr informationen kann ich jetzt nicht sagen ob du in deinm fall besser std::vector nehmen solltest

EDIT: ups, da war jemand schneller

[cooky451]

Eric Cartman schrieb:

Ich brauche eine map mit strings als Schluessel und Zeiger als Werte, die der Reihenfolge des Einfuegens geordnet sind

WTF, das ist genau das Gegenteil von einer Map. Was soll passieren, wenn du zwei mal den gleichen Schlüssel einfügst? Soll der dann zwei mal vor kommen? Oder soll der alte Wert überschrieben werden?

[XSpille]

http://www.cplusplus.com/reference/unordered_map/unordered_map/

Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average).

Zum Thema Hashing kannst du ja mal bei wikipedia lesen:
http://de.wikipedia.org/wiki/Hashing
oder es sollte genug andere Quellen im Netz geben.

Gruß
XSpille

[*Rewind*]

Für was brauchst du denn die Einfügereihenfolge? Entweder greifst du auf ein Element über seine Position (wie es z.B. bei Vector der Fall ist) oder du machst das über den Key-Wert. Kannst du etwas genauer erklären, was du vorhast?

[Th69]

Ich hatte mir extra dafür eine eigene Klasse geschrieben, welche intern eine Map und List parallel hält. Bei Bedarf kann ich den Source zuhause mal raussuchen...

[knivil]

queue

Bei Bedarf kann ich den Source zuhause mal raussuchen

Nee, erklaer erstmal das Problem. Warum Zweitcontainer? Was willst du machen, nicht wie!

[ipsec]

boost::multiindex bietet sowas (und vielen anderes). Eventuell ist das in diesem Fall aber Overkill.

[lisat]

warum nicht eine list<pair<string, int>> ? oder etwas ähnliches in der Art? Dann kannst Du Dir immer noch Zugriffsfunktionen dafür schreiben. Wobei ich nicht verstehe, warum die Reihenfolge des Einfügens von Bedeutung sind.

[Skym0sh0]

Deshalb fragt hier ja jeder nach dem Sinn bzw. dem Ziel vom TE.

[Eric Cartman]

In dem Container sind Objekte, die auf dem Bildschirm gezeichnet werden. Da sich diese ueberlappen koennen ist die Reihenfolge des Zeichnens wichtig.
Die map Schluessel (als String) sind die Bezeichner der Objekte und werden vom Benutzer selbst festgelegt. Je nach Eingaben des Benutzers muss ich dann per Bezeichner auf die Objekte zugreifen koennen.

Die pair/find Loesung ist zu langsam, da O(n).

@Th69
Das hatte ich auch vor, aber ich hatte doch noch gehofft, dass es eine schoenere Loesung gibt. Naja, dann eben nicht ..

[Skym0sh0]

Naja, die unordered Container müssten eine Zugriffszeit von O(1) haben (weil Hashing), sortieren ist damit aber nicht.

Das hast du aber wieder bei einer normalen std::map, dort müsste die Zugriffszeit bei O(log n) liegen (weil Baum).

Auch genannt wurde ein queue, bzw in dem Fall der priority_queue (ist das Wort queue jetzt eigentlich männlich, weiblich oder beides?!? ich sag nur "Der Kalkül")

Aber du willst Speed, vergleichst aber dann Strings? Widerspricht sich in meinen Augen...

[Ethon]

Skym0sh0 schrieb:

Auch genannt wurde ein queue, bzw in dem Fall der priority_queue (ist das Wort queue jetzt eigentlich männlich, weiblich oder beides?!? ich sag nur "Der Kalkül")

"Die" Warteschlange.

[Nexus]

Ethon schrieb:

"Die" Warteschlange.

Das std::set = das Menge?

Ansonsten geht die direkte Übersetzung von Datenstrukturen aber ziemlich oft mit den Artikeln auf:

• der Vector (Vektor)
• die List (Liste)
• die Deque (doppel-endige Warteschlange)
• die Map (Karte/Abbildung)
• das Array (Feld)
• der Stack (Stapel)
• die Queue (Warteschlange)
• der Tree (Baum)
• der Heap (Haufen)

Bei "Set" könnte das Neutrum daher rühren, dass es bereits deutsche Nomen wie das "Filmset" gibt. Gleiches gilt wohl für den "String"

[lisat]

Eric, Dir ist aber schon klar, dass die Landau Symbole nur das asymptotische Verhalten beschreiben und nichts über den absoluten Bedarf, insbesondere bei geringer Zahl von Elementen aussagen?

Und wie Skym0sh0 bereits geschrieben hat: Stringvergleich (und u.U. das Bilden von Hashes) sind nicht unbedingt die schnellsten Vorgehensweisen beim Adressieren von Elementen in einem Container.

[otze]

Eric Cartman schrieb:

Die map Schluessel (als String) sind die Bezeichner der Objekte und werden vom Benutzer selbst festgelegt. Je nach Eingaben des Benutzers muss ich dann per Bezeichner auf die Objekte zugreifen koennen.

Also: eine her geringe Anzahl von Objekten und der Zugriff über die map wird signifikant seltener eintreten als das Zeichnen?

=> vector<pair<string,Objekt> > mit push_back für neue Elemente. nach namn gesucht wird mit find_if oder ähnlichem.

[Skym0sh0]

Naja, Stringvergleiche sollten in O(n) zu schaffen sein (wobei n die Länge des Strings) und Hashes sollten in O(1) machbar sein (O(n) wäre hier nur nutzbar, wenn n die Größe des Datentyps ist).

Gib deinen Objekten eine z Koordinate mit und ordne sie in deiner map nach eben diesen Koordinaten.

[Ethon]

Skym0sh0 schrieb:

Naja, Stringvergleiche sollten in O(n) zu schaffen sein (wobei n die Länge des Strings) und Hashes sollten in O(1) machbar sein (O(n) wäre hier nur nutzbar, wenn n die Größe des Datentyps ist).

Wobei das auch wieder nur theoretische Betrachtungen sind.
Zb der GCC verwendet builtin strcmp, was sauschnell ist, wenn ein String eine Compilezeitkonstante ist.

In einer Hashmap muss zuerst der KOMPLETTE String gehasht werden, und dann muss nochmal mindestens 1 Knoten an einer linked List gehangelt werden, was nach Cache-misses schreit.

Wenn die Map sehr stark unterschiedliche Strings enthält wie

map<string, int> alter;
alter["Albert"] = 25;
alter["Berta"] = 35;
alter["Christoph"] = 45;
...

int alterVonMarianne = alter["Marianne"];

kann eine naive implementierung über einen Vector relativ lange effizient genug sein.

[Eric Cartman]

Erstmal danke fuer die Vorschlaege.

Skym0sh0 schrieb:

Gib deinen Objekten eine z Koordinate mit und ordne sie in deiner map nach eben diesen Koordinaten.

So hab ichs jetzt gemacht, da so ne z Koordinate sowieso noch eine gute Idee war

Aber wie kann ich sowas am bestem implementieren? map/multimap kann ja nur nach key sortieren...

Ich habs jetzt so gemacht, dass ich mir ne Klasse geschrieben habe welche eine std::multimap abstrahiert die die z Koordinaten als Key verwenden und ein pair aus string und zeiger als mapped_type. Key-Zugriff ist zwar nicht mehr direkt moeglich (sondern es muss nach mit find_if gesucht werden), aber notfalls kann ich noch einen zusaetzlichen unordered_map container verwenden, falls es zu langsam wird... Aber im Moment klappts ganz gut so.

[dot]

Eric Cartman schrieb:

Die map Schluessel (als String) sind die Bezeichner der Objekte und werden vom Benutzer selbst festgelegt. Je nach Eingaben des Benutzers muss ich dann per Bezeichner auf die Objekte zugreifen koennen.

Ich würde mit einer separaten unordered_map arbeiten, die strings auf Objekte abbildet. Insbesondere, da es wohl wesentlich wichtiger ist, schnell über die Objekte iterieren zu können. Der User wird kaum merken, ob der Lookup eines Objektes über seinen Namen jetzt 10 Mikrosekunden oder 100 Mikrosekunden dauert...

Eric Cartman schrieb:

Die pair/find Loesung ist zu langsam, da O(n).

Wieviele zehntausend Objekte sind es denn, dass das zu langsam ist?