Was ist der Vorteil von Multimap gegenüber der Karte von Vektoren?

72

Ich verstehe nicht, warum Multimap existiert, wenn wir eine Karte von Vektoren oder eine Karte von Mengen erstellen können. Für mich sind nur Unterschiede:

  • Verwendung equal_rangein multimap für Elemente eines Schlüssels und in der Karte von Vektoren bekommen wir einfach nutzen []Operator und Vektor von Elementen haben.
  • Verwendung multimap.insert(make_pair(key,value))in Multimap zum Hinzufügen von Elementen und map_of_vectors[key].push_back(value)in der Karte von Vektoren.

Warum also Multimap verwenden? Für mich ist es besser, einen Vektor als zwei Iteratoren zu haben, um alle Werte eines Schlüssels zu erhalten.

Diese Frage gilt auch für unordered_map von Vektoren und unordered_multimap.

Mariusz Pawelski
quelle
9
Ich muss zugeben, dass ich den Zweck von multimap: /
Matthieu M.
Ich bin etwas spät in der Frage, aber auch Multimap verbraucht aufgrund der zusätzlichen Zeiger viel mehr Speicher als die Karte von Vektoren. Der einzige Grund, warum ich sie verwenden würde, ist, wenn ich den Schlüssel jedes Elements behalten möchte (wenn push_backSie ihn nicht behalten)
Jcao02
Multimap ist ideal, wenn Sie nicht nur doppelte Schlüssel mit unterschiedlichen Werten verfolgen möchten, sondern auch jedes Schlüssel / Wert-Paar kurzfristig löschen möchten. Eine Karte mit Vektoren ist dafür nicht geeignet, und während Sie eine Karte mit Listen verwenden können, ist es bequemer, nur eine Multimap zu verwenden.
Richizy
1
Während ich Ihren Standpunkt sehe (und ich neige auch nicht dazu, Multimap zu verwenden), kann ungefähr dasselbe über map<K, V>vs. gesagt werden, set<pair<K, V>, cmp_first<K, V>>wo cmp_first das .firstMitglied vergleicht .
Lorro
1
Karte der Sätze: stackoverflow.com/questions/8602068/…
Ciro Santilli 法轮功 冠状 病 六四 事件 法轮功

Antworten:

57

Ich würde sagen, es hängt davon ab, ob alle Werte mit demselben Schlüssel eine Beziehung haben, die Sie ansprechen möchten.

Gehen Sie beispielsweise häufig alle Elemente mit der Taste X durch oder übergeben Sie sie an eine Funktion usw. Dann ist es bequemer, sie bereits in einem separaten Container zu haben, den Sie direkt ansprechen können.

Wenn Sie jedoch nur eine Sammlung von Elementen haben, die möglicherweise denselben Schlüsselwert haben oder nicht, warum sollten Sie dazwischen Vektoren verwenden? Es ist bequemer, die Multimap mit Iteratoren zu durchlaufen, als eine verschachtelte for-Schleife für die Karte, Vektorfall.

Eine andere Sichtweise: Wenn mehrere Einträge pro Schlüssel sehr häufig sind, ist Ihre Struktur im Karten- und Vektorfall effizienter. Wenn sie selten vorkommen, ist es das Gegenteil.

ypnos
quelle
3
Vielen Dank. Ihre und Artyoms Antwort zeigte mir ein wenig mehr Unterschiede. Ich glaube jedoch immer noch nicht, dass Multimap im wirklichen Leben so nützlich ist wie eine Karte von Vektoren. Aber das ist meine persönliche Meinung;)
Mariusz Pawelski
Mein praktischer Auszug aus dieser Antwort lautet: multimapSie können einen Iteratorbereich haben, der die gesamte Struktur abdeckt, aber solche Anfangs- / Enditeratoren iterieren Schlüssel- und Wertepaare (was möglicherweise nicht bequem ist). Mit der map<...,vector>Iteration ist die gesamte Struktur komplexer, aber Sie können Anfangs- / Enditeratoren mit gleicher Folge von nur Werten haben.
Jarek C
55

Es gibt viele wichtige Unterschiede zwischen multimap<x, y>undmap<x, vector<y>>

Nachdem Sie einen Wert in Multimap eingefügt haben , wissen Sie, dass der Iterator gültig bleibt, bis Sie ihn entfernen. Dies ist eine sehr starke Eigenschaft. Sie können ihn nicht mit einer Karte von Vektoren haben.

multimap<x,y>::iterator p=mymap.insert(make_pair(a,b));

Der Iterator bleibt gültig, bis er aus der Karte gelöscht wird. Im zweiten Fall wird er jedes Mal ungültig, wenn Sie dem Vektor einen neuen Eintrag hinzufügen.

Beachten Sie auch, dass map<x, vector<y>>möglicherweise ein leerer Wert mit dem vorhandenen Schlüssel festgelegt ist, Multimap jedoch nicht.

Dies sind verschiedene Dinge, die sich unterschiedlich verhalten.

Und um ehrlich zu sein, vermisse ich Multimap in einigen Sprachen, die es nicht in ihrer Bibliothek bereitstellen.

Artyom
quelle
2
Während der Winkel der Iterator-Invalidierung interessant ist, wird Ihre Aussage " jedes Mal ungültig, wenn Sie dem Vektor einen neuen Eintrag hinzufügen". ist praktisch nicht wahr. Der Iterator wird nur ungültig, wenn die Größe des Vektors geändert wird, sonst nicht ... obwohl Sie normalerweise nicht wissen / sich darum kümmern, wann die Größe geändert wird, sollten wir unseren Code nicht um die Größenänderung herum entwerfen und einfach davon ausgehen, dass Iteratoren beim Einfügen ungültig werden!
Nawaz
@Nawaz erwägen, einzufügen (neue hinzuzufügen) und zu löschen
Dawid Drozd