HashMap in C++

[Gast]

Hi, ich suche eine Klasse oder Variable für C++, die der HashMap in Java gleicht.

Also einfach ein Datenpool, in den ich Zeugs reinwerfen kann.

Es geht um ein Spiel, ich habe ganz viele Sprites, und möchte das Sprite Objekt und die y Position des Sprites in die HashMap eintragen, dann möchte ich in der Main-Game-Schleife diese HashMap nach aufsteigender X Position der Sprites sortieren, und die Sprites in der Reihenfolge blitten.

Kennt jemand eine solche Variable/Klasse?

[Coda]

Ich verstehe gerade nicht für was du eine Hashmap brauchst für sowas. Das ist totaler Quatsch.

std::vector<Object*> und dazu std::sort mit entsprechendem Predicate Functor müsste völlig genügen.

[Gast]

Also im Prinzip geht es darum, dass ich eine Menge habe (Schlüssel und Wert von jedem Element), und da zu jedem Zeitpunkt neue Elemente hinzufügen kann, also von unbegrenzter Grösse.

Geht das mit einem Vektor?
Wenn ja, kannst du mir eine Vektor Einführung zeigen? Ich finde dazu nicht viel.

[Coda]

Warum brauchst du Schlüssel und Wert? Kannst du y nicht einfach als Membervariable der Klasse speichern?

std::vector ist sowas wie Vector in Java. Also ein dynamisch vergrößerbares Array. Ich weiß jetzt nur nicht ob dass das ist was du brauchst.

[micki]

oder std::map, hätte etwa das verhalten was du suchst.

[maximAL]

also genau passen würde std:map (oder auch multimap). da kannst du über einen schlüssel ein objekt eintragen.
lass dir aber gesagt sein, dass die objekte beim auslesen über den schlüssel erst in der map gesucht werden müssen (da sie in einem suchbaum gespeichert werden). das kann bei großen datenmengen schnell langsam werden (bei ein paar sprites egal, bei ein paar tausend schon weniger).
ansonsten lieber eine list als einen vector. wenn du häufig elemente hunzufügst (und evtl. entfernst) ist der vector ziemlich lahm.
hmm, vielleicht könnten man auch einen der qeues missbrauchen...gibt viele möglichkeiten.
generell sollte man wissen, was die STL so zu bieten hat: gutes, kostenloses e-book (http://www.informatik.hs-bremen.de/~brey/stlb.html) . lies die mal den teil mit den datencontainern durch.

[Coda]

oder std::map, hätte etwa das verhalten was du suchst.Das hätte ich jetzt auch gesagt, aber mir ist der Sinn dahinter nicht ganz klar.

das kann bei großen datenmengen schnell langsam werden (bei ein paar sprites egal, bei ein paar tausend schon weniger).Da der Baum bei std::map immer ausbalanciert ist (Red-Black-Tree) ist der Zugriff O(log n). Das ist auch bei großen Datenmengen schnell genug eigentlich.
Bei 1000 Elementen sind im Schnitt also maximal 10 Speicherzugriffe nötig, bei 10000 14. Du siehst, es ist nicht so schlimm ;)

ansonsten lieber eine list als einen vector. wenn du häufig elemente hunzufügst (und evtl. entfernst) ist der vector ziemlich lahm.
hmm, vielleicht könnten man auch einen der qeues missbrauchen...gibt viele möglichkeiten.Hm, dann ist die std::map vielleicht doch besser. Da könnte man die Objekte auch schnell hinzufügen und entfernen und die Menge ist trotzdem immer sortiert.

[Gast]

map hab ich inzwischen auch entdeckt, scheint das Äquivalent zum HashMap zu sein, so wie set das entsprechende zum HashSet.

Vielen Dank.

[Gast]

Achja, die map sortiert zwar standardmässig inkrementell nach Index, wenn zwei Indexe identisch sind, wird eines der Elemente vom Iterator ignoriert.

Weiss jemand, was ich da machen kann? Kein Element darf wegfallen, auch nicht bei gleichem Index.

[Gast]

Hab mich geirrt, es ist eher folgendes:
Mein Index ist die Y Position, Wert ist ein Sprite Objekt.

So:

map<int, Sprite*> map_sprites;


Dann packe ich in einer Schleife all meine Sprites darein:

while (...) {
sprite pos = sprite01.GetPos();
map_sprites[sprite_pos.y_pos] = sprite01;
map_sprites[sprite_pos.y_pos] = sprite02;
}


...
etc.

Ist jetzt aber die Y Position der beiden gleich, spreche ich denselben Index an... so:


map_sprites[100] = sprite01;
map_sprites[100] = sprite02;


Und das geht natürlich nicht, nehme ich also das Sprite Objekt selbst als Schlüssel, und die Position als Wert.
Fehlt mir noch eine Möglichkeit, (ohne BubbleSort, wenn möglich Methode) alles aufsteigend nach yposition zu sortieren.

Fällt jemandem ein besserer Datentyp ein, oder gibt es in C++ so etwas wie eine sort Methode, die für alle Container Klassen funktioniert?

[micki]

du mußt ne multimap (std::mmap, ist im selben include) nehmen, dann kannst du mehrere entries mit selbem key haben, zum iterieren solltest du den Iterator nehmen damit du die doppelten keys auch bekommst. du kannst natürlich auch for_each benutzen damit es schneller geht.

MfG
micki

[Coda]

Achja, die map sortiert zwar standardmässig inkrementell nach Index, wenn zwei Indexe identisch sind, wird eines der Elemente vom Iterator ignoriert.

Weiss jemand, was ich da machen kann? Kein Element darf wegfallen, auch nicht bei gleichem Index.std::multimap (nicht std::mmap, wie kommst du drauf micki?)

map hab ich inzwischen auch entdeckt, scheint das Äquivalent zum HashMap zu sein, so wie set das entsprechende zum HashSet.Nein. Eine Hashmap ist nicht sortiert und funktioniert auch sonst ganz anders.

[Gast]

Danke euch allen, die multimap ist genau das, was ich gesucht habe.

[micki]

wie kommst du drauf micki?
20h am stück arbeiten und ich bekomm hallos :ucrazy3:
mein körper wird alt

pardón @gast

MfG
micki