C++ Ist std::map das richtige für diesen Zweck?

T_55 · 26. Juli 2016

Hallo,

ich suche nach einer möglichst passenden std Containerklasse um tabellenähnlich Daten abzuspeichern und aufzurufen.

Es soll eine Tabelle mit 3 Spalten geben. Die erste Spalte ist ein int Wert und die beiden anderen double. Der int Wert ist sozusagen der Schlüsselwert.

Das Programm schreibt immer wieder neue Zeilen mit den 3 Werten und diese werden irgendwann wieder ausgelesen und danach soll die Zeile auch wieder gelöscht werden.

zB:
73645 9.7564 7.534
53540 1.4377 0.002
usw

Ich dachte jetzt als erstes an std::map was ja die gebrauchten Funktionen wie Zeile erstellen und beschreiben und Zeile auslesen und löschen beinhaltet, allerdings bräuchte ich hier wohl zwei maps denn es sind ja zwei double Werte in den Spalten nach dem int Schlüsselwert. Würde heißen der Schlüsselwert würde einmal umsonst Speicher verbrauchen. Oder ist es möglich bei map einem Schlüsselwert mit mehr als einem anderen Wert zu assoziieren?

Grüße

_schaTTen_ · 26. Juli 2016

Das Zauberwort für 2 Werte mit einem Schlüssel ist std:

air. Du erstellst also eine Map mit dem int als Schlüssel und dem Inhalt von Pair das die beiden double Werte enthält.

T_55 · 26. Juli 2016

Danke das kannte ich nicht. Was würde man denn machen wenn es noch mehr Spalten und Dateitypen nach dem Schlüssel geben würde? Könnte man auch ein struct in die map legen?

aroxx · 26. Juli 2016

warum ein

Code:

std::pair

und kein einfaches

Code:

new double[2]

?

http://www.cplusplus.com/reference/map/map/
ja du kannst jede class / struct als value für deine map nehmen

VikingGe · 26. Juli 2016

@aroxx weil das Pair ein Stack-Objekt ist und du da eine Heap-Allokation machst, um die du dich bei jeder späteren Modifikation der Map manuell irgendwie kümmern musst. Im Grunde müsstest du einen Wrapper um die Map herum basteln, nur damit du da Memory Leaks vermeidest.

Für Arrays fester Länge gibt es auch std::array, und für Arrays dynamischer oder unbekannter Länge den berühmten std::vector, der zwar auch seinen Speicher vom Heap nimmt, aber auch automatisch wieder freigibt. new bitte immer vermeiden, wenn nicht klar ist, wie hinterher wieder aufgeräumt wird.

T_55 · 26. Juli 2016

Das mit dem struct wäre prima, denn dann könnte man beliebig viele Spalten mit beliebigen Datentypen nutzen.
Auch das mit dem Array würde für dieses Beispiel passen.
Weiß wer wie man eine Zeile mit drei Werten befüllt? (und dann wieder ausliest)?

Code:

struct Tabelle
{
   double a;
   double b;
};

std::map<int, Tabelle> dieMap;

dieMap.insert(6453, 0.9856, 54.436); // das geht so nicht :-)

VikingGe · 26. Juli 2016

Du musst natürlich eine Instanz von deinem Struct irgendwie erstellen und dann als Argument an die insert-Methode übergeben. Einfach auf die Typen achten - std::map<K, V>::insert verlangt ein K als ersten Parameter und ein V als zweiten Parameter, und V ist in deinem Fall Tabelle.

Code:

Tabelle tabelle;
tabelle.a = 0.9856;
tabelle.b = 54.436;
dieMap.insert(6453, tabelle);

Die Variante ist aus mehreren Gründen etwas unschön:
- Es kann uninitialisierte Werte geben, wenn du etwas vergisst.
- Es sind vier Zeilen Code nötig.

Erster Schritt zur Verbesserung: Wir führen einen Konstruktor ein.

Code:

struct Tabelle {
  // Standardkonstruktor. Initialisiert alle Member
  // mit den angegebenen Standardwerten.
  Tabelle() { }
  
  // Der Konstruktor, den wir wollen. Schreibt einfach
  // die beiden Werte, die du übergibst, in die Member.
  Tabelle(double _a, double _b)
  : a(_a), b(_b) { }

  double a = 0.0;
  double b = 0.0;
};

dieMap.insert(6453, Tabelle(0.9856, 54.436));

Das entspricht nahezu 1:1 dem std:air-Ansatz, nur, dass die Member hier sinnvollere Namen haben können.

Miuwa · 26. Juli 2016

@VikingGe:
1) Dein Code kompiliert nicht (evtl. hast du insert mit emplace verwechselt)
2) Der Konstruktor ist eigentlich unnötig:

Code:

struct Tabelle
{
    double a;
    double b;
};

std::map<int, Tabelle> dieMap;

dieMap.emplace(6453, Tabelle{ 0.9856, 54.436 });

@T_55:
Ob std::map die für dich am besten geeignete Datenstruktur ist hängt von den Nutzungsdetails ab:
Müssen die Daten sortiert sein? Von wie vielen Einträgen reden wir hier? Wie hoch sind die Performanceanforderungen? Hast du sehr viele Inserts oder primär nur lookups? std::map is generell eine relative ineffiziente Datenstruktur, aber wenn sie genau das Interface bietet, das du brauchst und die Anforderungen nicht allzu hoch sind spricht erst mal nichts dagegen sie zu nutzen. Alternativen wären z.B. std::unordered_map oder ein

Code:

 std::vector<std::pair<int,Tabelle>>

der aber ein völlig anderes Interface bietet.

maxwell-cs · 26. Juli 2016

Magogan · 27. Juli 2016

Wenn er Zeilen wieder löschen will, vor allem mittendrin, dann ist ein std::vector vielleicht nicht das Richtige, da dann immer sehr viel kopiert wird, wenn er nicht manuell die letzte Zeile in die zu löschende kopiert und die letzte löscht. Dann geht das Suchen einer Zeile aber nur in Linearzeit statt in logarithmischer Zeit, also deutlich langsamer.

Miuwa · 27. Juli 2016

@Magogan: Ich hab ja auch nicht gesagt, dass er unbeding die besser Wahl wäre, sondern hab nur gesagt, dass er eine Alternative ist und nach dem Nutzungsmuster gefragt.

The Ripper · 27. Juli 2016

Solange man nich weiß, was er genau damit vorhat, kann man alles mögliche empfehlen.

Eventuell wäre auch ne Queue ne Option, falls man einfach nur das älteste Element lessen & löschen möchte.

T_55 · 27. Juli 2016

Besten Dank schon mal! ich habe nun anhand vom Beispiel von Miuwa die Sache hinbekommen. Erstellen klappt wunderbar und löschen und auslesen der Werte hat sogar auch funktioniert, genial!

Um die Fragen noch zu beantworten:

Miuwa schrieb:
Müssen die Daten sortiert sein?

Nein.

Miuwa schrieb:
Von wie vielen Einträgen reden wir hier?

Sehr unterschiedlich von 0 bis ca maximal 300000. Aber ab 20000 ist schon eher seltener.

Miuwa schrieb:
Wie hoch sind die Performanceanforderungen?

Gute Performance wäre schon nicht verkehrt denn dieser Datenpool ist schon permanent in Aktion. Aber mit Performance bezahlt man dann vielleicht an anderer Stelle...

Miuwa schrieb:
Hast du sehr viele Inserts oder primär nur lookups?

Die Lebenszeit eines Eintrags sieht so aus: Erstelle per Schlüssel den Eintrag, dann nach unterschiedlicher Zeit, lese Werte aus Eintrag und lösche Eintrag. Dieser Vorgang passiert dann quer gemischt mit anderen Einträgen die alle immer unterschiedliche Schlüssel haben.

Die Datenstruktur soll so ähnlich funktionieren wie ein Kaufhaus das von Menschen betreten und verlassen wird. Sobald Menschen im Kaufhaus sind bekommen sie einen Eintrag und übergeben Ihre Werte, sobald sie das Kaufhaus verlassen, werden sie wieder gelöscht. Es kann sein das manche niemals ins Kaufhaus gehen und manche hunderte mal. Und es können mal viele Menschen im Kaufhaus sein oder mal wenige oder gar keine und alle Menschen betreten und verlassen zeitlich gesehen das Kaufhaus vollkommen unabhängig voneinander.

Grüße

The Ripper · 28. Juli 2016

Wenn du nur via Schlüssel auf die Elemente zugreifst, hättest mit der unordered map durchschnittlich eine konstante Laufeit beim Einfügen&Löschen.
Für bessere Laufzeit würde mir nur ein vorbereitetes 1:1 array für alle Schlüssel einfallen, geht aber extreme auf den Speicher.

Als Schlüssel nimmst dein Schlüssel und für die doubles entweder nen pair, struct oder class

Suche

C++ Ist std::map das richtige für diesen Zweck?

T_55

Lieutenant

_schaTTen_

Lieutenant

T_55

Lieutenant

aroxx

Lieutenant

VikingGe

Gast

T_55

Lieutenant

VikingGe

Gast

Miuwa

Commodore

maxwell-cs

Lt. Junior Grade

Magogan

Lieutenant

Miuwa

Commodore

The Ripper

Lt. Commander

T_55

Lieutenant

The Ripper

Lt. Commander

Ähnliche Themen