Sammeldatentyp wie HashMap in Java ?

ichbineinnoob

Hallo,

ich fange gerade mit C++ an und weiß leider nicht mehr weiter.

Ich brauche ein dynamisches Konstrukt, in dem ich mehrere Objekte abspeichern kann. Also kein festes Array. Eine Liste möchte ich auch vermeiden.

In Java hätte ich es mit einer HashMap gemacht.

Gibt es in C++ ein Datentyp, mit dem ich ungefähr (wenn nicht genau das selbe) machen kann?

Ich bin für jeden Rat dankbar!

ichbineinnoob

Ach ja, noch eine kleine Nachfrage.

In C++ gibt es standardmäßig scheinbar nur die primitiven Datentypen + dem String. Oder gibt es eine Kollektion, von ungefähr dem gleichen Umfang, wie er in Java existiert?

http://www.cppreference.com/wiki/

http://www.cplusplus.com/

pumuckl

ichbineinnoob schrieb:

In C++ gibt es standardmäßig scheinbar nur die primitiven Datentypen + dem String.

Welchen String meinst du? C-Strings, d.h. char-Arrays? Oder std::string? Wenn du letzteren kennst, wundert es mich, dass du die zig anderen Typen der Standardbibliothek nicht kennst.
An Containern gibts z.B. std::vector, std::list, std::set, std::map, std::deque. Zumindest vector sollte im C++ Einsteigerbuch deiner Wahl behandelt werden.

Nexus

ichbineinnoob schrieb:

Ich brauche ein dynamisches Konstrukt, in dem ich mehrere Objekte abspeichern kann. Also kein festes Array. Eine Liste möchte ich auch vermeiden.

In Java hätte ich es mit einer HashMap gemacht.

Eine Hash-Map ist schon eine recht spezielle Anforderung. Weit mehr als nur "mehrere Objekte abspeichern". Falls du das wirklich benötigst, kannst du dir z.B. std::tr1::unordered_map anschauen. Allerdings denke ich, du suchst nach anderen STL-Containern, dann könntest du dir für den Einstieg diesen Artikel anschauen. Aber ein gutes C++-Buch brauchst du nebenbei sowieso, hast du das? Z.B. den C++-Primer?

ichbineinnoob

Danke für die vielen Antworten! Es ist leider schon länger her, als ich ein C++ Buch gelesen habe.
Ich habe leider keine Zeit um ein komplettes Buch zu lesen, sondern benötige nur 2-3 Datentypen.

Also es geht um folgendes:

Ich habe einen Haufen an Zuständen (z.B. Koordinaten), diese möchte ich einfach nur irgendwo unsortiert abspeichern. Die Anzahl ist nicht fest und wird mit der Zeit größer. Also wäre ein Container günstig.
Weiterhin habe ich eine Zahl an Aktionen. Die Anzahl ist an sich fest, aber diese würde ich auch gern wie die Zustände abspeichern.

Und nun kommt das größte Problem. Aus einem Zustand + Aktion folgt eine Bewertung. Also muss ich alle Zustände + alle Aktionen + alle Bewertungen ebenso irgendwo abspeichern.
In Java hätte ich das mit einer HashMap gemacht: Zustand x Aktion -> Bewertung
oder ich hätte einfach Zustand x Aktion x Bewertung irgendwo abgespeichert.
Wie man das in C++ macht weiß ich leider nicht.

Was wäre für die beiden Fälle denn am günstigsten?

CStoll

Das kannst du in C++ genauso machen, dazu verwendet man z.B. eine std::map<std::pair<Zustand,Aktion>,Bewertung> (oder entsprechend die std::tr1::unordered_map<>) - das heißt eine Map, die ein Zustand/Aktion-Paar als Schlüssel verwendet.

Für die Aktionen und Zustände wäre je nach Verwendungszweck ein std::vector<>, std::list<> oder std::set<> geeignet (bei den TR1-Containern kenne ich mich nicht so aus, aber afaik gibt es da auch einen mit fest vorgegebener Größe).

Gibt eigentlich viele Lösungen. Eine Idee wäre, je nachdem wie du Zustände, Aktionen und Bewertungen konstuierst:

class Aktion {
std::map<Zustand, Bewertung> bewertungen;
public:
Bewertung getBewertung(Zustand) 
{ 
return bewertungen[Zustand]; 
}

(benötigt operator< für Zustand)

Mit boost und tr1 gibts soweit ich gesehen habe tupel, also ginge sowas wie

vector<tr1::tuple<Zustand, Aktion, Bewertung>

(ka ob der container wirklich "tuple" heißt)
Aleternativ kannst dir ein 3-tupel als template oder auch direkt selbst schreiben z.B. mit

pair<pair<Zustand, Aktion>, Bewertung>

Dann gibt's noch map<pair<Zustand, Aktion>, Bewertung>, dafür musst du dir aber für pair<Zustand, Aktion> auch einen operator< überlegen

ichbineinnoob

Danke bis hierhin für die bisherigen Antworten!
Das hat so weit prima geklappt.

Allerdings habe ich ein weiteres Problem:
Um Speicherplatz zu sparen, wollte ich so etwas machen:

vector<Zustand> zustaende;
vector<Aktion> aktionen;
map<pair<Zustand*,Aktion*>,int> bewertung;

Also in der map sollen Pointer auf die Zustaende und Aktionen sein.

Das Problem ist aber, sobald ich den Vektoren neue Objekte hinzufüge, dann stimmen die Pointer in der map nicht mehr.

Was kann ich da tun?

CStoll

Was für Anforderungen hast du denn an das Zugriffsverhalten und die Elementreihenfolge dieser Vektoren? Wenn du nur am Ende der Vektoren einfügen willst, kannst du mit reserve() genug Platz vorbelegen, damit er nicht im laufenden Betrieb Speicher nachfordern muß. Andernfalls müsstest du einen Container verwenden, der seine Elemente nicht umkopiert (z.B. std::list).

Nexus

In einer std::deque sollten Zeiger auf Elemente nach einem Vergrössern auch gültig bleiben.

asc

ichbineinnoob schrieb:

Allerdings habe ich ein weiteres Problem:
Um Speicherplatz zu sparen, wollte ich so etwas machen:

Und prompt schießt du dir mit Optimierungen in das eigene Bein...

Ein vector ist ein Zusammenhängender Speicherbereich. Was bedeutet, das wenn er vergrößert wird, er in einen neuen Bereich umkopiert wird (in der Regel wird dabei in etwa die Kapazität verdoppelt).

ichbineinnoob schrieb:

Was kann ich da tun?

Entweder prüftst du erst aus, ob du wirklich ein Speicherproblem bekommst, und verzichtest auf Zeiger, oder du nimmst einen Container, auf dem sich die Positionen nicht ändern (z.B. list).

ichbineinnoob

Ich habe es noch einmal mit list versucht und es scheint prima zu funktionieren. Danke für die Hilfe. Allerdings habe ich bislang nur eine begrenzte Zahl an Testelementen ausprobiert.
Ändern sich die Speicherplätze in list nie oder eventuell doch unter speziellen Umständen? (Bevor ich mir alle Mühe umsonst mache)

CStoll

ichbineinnoob schrieb:

Ändern sich die Speicherplätze in list nie oder eventuell doch unter speziellen Umständen? (Bevor ich mir alle Mühe umsonst mache)

Die verändern sich höchstens, wenn du eine nicht standardkonforme Version der STL hat. std::list<> speichert seine Elemente in einer doppelt verketteten Liste, das hat es nicht nötig die Elemente im Speicher umzuordnen, sondern muß nur die Pointer umhängen.

Java steckt ja auch nicht die Pointer in die HashMap, sondern hash values, darum hat jedes Java Objekt eine hashCode() Methode.

std::map ist keine HashMap, aber die Idee kann man da auch anwenden. Einfach zustand.getId() und aktion.getId() einführen und diese Ids als keys für die Map verwenden. Die Id muss eindeutig sein, am einfachsten ein static int hochzählen, wenn du nicht multithreaded bist.