Fragen zur STL Map template

[SeppJ]

Sowas findest du in guten C++ Büchern.

Wenn du schon C++ kannst, dann auch hier:
http://linuxsoftware.co.nz/containerchoice.png
Das setzt jedoch voraus, dass du schon so ungefähr weißt, worum es geht.

Eine map verbindet einen Schlüssel mit einem Wert. Das heißt, es ist so ähnlich wie ein vector, aber man kann als Index beliebige (sortierbare) Objekte nehmen, anstatt nur Ganzzahlen. Und falls man Ganzzahlen möchte, brauchen diese auch nicht von 0 bis N zu gehen, sondern es können beliebige Schlüsselzahlen gewählt werden.

Man kann sich das wie eine Art Minidatenbank vorstellen. Anwendungen gibt es viele, map ist vermutlich der von mir am zweithäufigsten genutzte STL-Container (nach vector und knapp vor set). Künstliches Beispiel:

#include <map>
#include <iostream>

using namespace std;

int addieren(int a, int b) {return a+b;}
int subtrahieren(int a, int b) {return a-b;}
int multiplizieren(int a, int b) {return a*b;}
int dividieren(int a, int b) {return a/b;}

typedef int (*funktionszeiger)(int , int );

int main()
{
  map<char, funktionszeiger> aktionen;
  aktionen.insert(make_pair('+', &addieren));
  aktionen.insert(make_pair('-', &subtrahieren));
  aktionen.insert(make_pair('*', &multiplizieren));
  aktionen.insert(make_pair('/', &dividieren));

  int a,b;
  char rechenzeichen;
  while (cin >> a >> rechenzeichen >> b)
    cout << a << ' ' << rechenzeichen << ' ' << b << " = " << aktionen[rechenzeichen] (a,b) << '\n';
}

Eingabe und Ausgabe:

[b]1+4 [/b]
1 + 4 = 5
[b]5*6[/b]
5 * 6 = 30
[b]8/2[/b]
8 / 2 = 4
[b]5-6[/b]
5 - 6 = -1

Eine andere haufige Nutzung von maps ist, das Vorkommen von Objekten in einer Menge zu zählen (z.B. map<klasse, int>).

[test123]

Welche Vorteile hat es gegenüber der Std::Vector ?

[Gast]

Also ein Nachteil ist die Performance.

[cooky451]

Hacker schrieb:

Also ein Nachteil ist die Performance.

w00t?

test123 schrieb:

Welche Vorteile hat es gegenüber der Std::Vector?

Du meinst wohl, welchen Vorteil es zu std::vector<std::pair<.., ..>> in Kombination mit std::find hat.
Nun, die std::map hält ihre Elemente sortiert, wodurch man eine binäre Suche durchführen kann. Bei sehr vielen Elementen ist das (enorm(!)) viel schneller, als eine lineare Suche. Bei wenig Elementen ist das dagegen nicht so toll, da die Daten bei einer std::map verschachtelter sind. Nur hat man bei wenigen Elementen selten Performanceprobleme, insofern kann man hier ruhig das praktischere Werkzeug nutzen.

[dahateinerahnung]

Hacker schrieb:

Also ein Nachteil ist die Performance.

@cookie: Man kann den Vektor auch sorieren und drauf std::binary_search ausführen, das ist etwa gleich schnell wie bei der map. Und wenn du oft anhängen und wenig suchen musst, macht selbst die lineare Suche den (enormen(!)) Overhead beim Einfügen in die map wett.

[Gast]

Edit: gelöscht

[cooky451]

dahateinerahnung schrieb:

@cookie: Man kann den Vektor auch sorieren und drauf std::binary_search ausführen, das ist etwa gleich schnell wie bei der map.

Bei <int, int> ist das sogar in etwa doppelt so schnell. Aber das hilft dir leider nicht, denn selbst wenn du erst nach ~5000 "Anhängen" wieder etwas suchen willst, ist die map wieder wesentlich schneller. Und das ist schon ein ziemlich übertriebenes Verhältnis.

[Ethon]

binary_search und map haben doch O(log(n)) beim Suchen?
Naja, im Zweifelsfall unordered_map.

[seldon]

Wenn wir schon von Performance reden, darf std::unordered_map nicht unterschlagen werden. Dabei handelt es sich um eine Hashtable, bei der mit vernünftigen Parametern (insbesondere einer vernünftigen Hashfunktion und einer realistischen Auslastungsobergrenze) alle Operationen in konstanter bzw. amortisiert konstanter Zeit passieren. Gerade bei großen Datenmengen lassen sich damit ganze Größenordnungen einsparen, denn auch binäre Suche (egal in welcher Form) ist Ω(log(n)).

Caveat implementor: Man muss gelegentlich etwas Hirnschmalz auf eine dem eigenen Anwendungsfall angemessene Hashfunktion verwenden, und allgemein darf man sich die Schlüssel für Hashtabellen nicht aus vertrauensunwürdigen Quellen geben lassen. Beides wird mitunter nicht so richtig ernst genommen; das macht man auf eigene Gefahr. Wie sich eine Laissez-Faire-Haltung in dieser Sache auswirken kann, wurde zum Beispiel auf dem 28C3 beschrieben.

Was die vector/map-Geschichte angeht: Es ist zwar richtig, dass man auf einem sortierten Vektor eine binäre Suche anstellen kann und da mitunter auch schneller ist als in einem RB-Baum (als solcher ist std::map üblicherweise implementiert), aber die Sortierung des Vektors gibt es nicht für lau. In einen sortierten Vektor so einzufügen, dass die Sortierung erhalten bleibt, kostet Ω(n), das Einfügen in den Baum ist dagegen O(log(n)). Wenn man vorsortierte Daten hat oder man mit einem über weite Strecken statischen Datenbestand arbeitet, der nach einmaliger Sortierung praktisch nur noch gelesen werden muss, kann der sortierte Vektor von Vorteil sein, einen allgemeinen Ersatz für std::map stellt er allerdings nicht dar.

[Ethon]

In einen sortierten Vektor so einzufügen, dass die Sortierung erhalten bleibt, kostet Ω(n), das Einfügen in den Baum ist dagegen O(log(n)).

Naja, hängt von den Daten ab. Die Stelle zum Einfügen findet man auch mit O(log(n)), den Rest verschiebt man im Optimalfall mit einem optimiertem memcpy nach hinten. Ich denke dass man einiges an Speicher verschieben kann in der Zeit, in der man sich durch Pointer hangelt

[seldon]

Auch memcpy braucht Ω(n), um n Werte zu verschieben, und durchschnittlich muss der halbe Vektor verschoben werden. Dementsprechend ist die Laufzeitkomplexität des Einfügens in einen sortierten Vektor bei Erhaltung der Sortierung Ω(log(n) + n) = Ω(n).

Völlig unabhängig davon, welche konstanten Faktoren zwischen Baum und Vektor unterscheiden: Je größer n wird, desto schlechter scheidet jede Ω(n)-Lösung gegenüber jeder O(log(n))-Lösung ab.

[Ethon]

Hmm, wollte es mal testen, leider wird std::map/std::unordered_map immer wegoptimiert, die vector-Version läuft.

Interessant finde ich dass bei 1.000.000 Elementen durch ein reserve() am Anfang gerade mal 60ms gespart werden, das Vergrößern des vectors scheint echt billiger zu sein als ich dachte ...

[Ethon]

Auch memcpy braucht Ω(n), um n Werte zu verschieben, und durchschnittlich muss der halbe Vektor verschoben werden.

Bin mit der Notation nicht ganz vertraut, aber angenommen es sind nur einzelne Bytes, wäre es dann nicht eher Ω(n / 16) wenn das memcpy 128bit Register nutzt?

[seldon]

Es handelt sich um Landau-Symbole. Konstante Faktoren fallen weg - Ω(n / 16) = Ω(n).

Ω meint eine Untergrenze, O eine Obergrenze. Bei einem Algorithmus in Ω(n) steigt die benötigte Laufzeit mit der Anzahl der Datenelemente (mindestens etwa) linear - er braucht für 2x Datenelemente (mindestens etwa) doppelt so lange wie für x Elemente. Bei einem Algorithmus in O(log(n)) steigt die benötigte Laufzeit (höchstens etwa) logarithmisch. Unabhängig davon, welche konstanten Faktoren dabei noch eine Rolle spielen, gerät die lineare Variante gegenüber der logarithmischen ab einem gewissen n ins Hintertreffen.

[Test123]

vielen dank für die Antworten