std::map mit Einfuegereihenfolge ?

[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?