“multiset” & “multimap” – Was ist der Sinn?

Lesezeit: 3 Minuten

Benutzer-Avatar
Sebastian Dressler

Wie die Frage schon sagt … verstehe ich den Punkt nicht multisets / multimaps.

Also, was ist der Zweck?

Einige Anwendungsfälle:

multimap

  • Mit Postleitzahl als Schlüssel alle Personen, die diese Postleitzahl haben
  • Mit Konto-ID als Schlüssel alle offenen Bestellungen dieser Person/des Kontos
  • Ein Lexikon, mit pro Stichwort diversen Erklärungen

Multiset

ist im Wesentlichen eine Karte mit einem Schlüssel und einer ganzzahligen Anzahl.

  • Der Bestand eines Shops, alle Produkte haben ihren Schlüssel und die noch verfügbare Menge ist der Wert
  • kumulierte Verkaufsdaten eines Shops, jedes Mal, wenn ein Produkt verkauft wird, wird die Produkt-ID dem Multiset hinzugefügt, wodurch die verkaufte Menge erhöht wird

Der wichtigste Vorteil der Verwendung eines Multisets gegenüber einem Vektor/einer Liste (oder einem anderen Container) ist die zeitliche Komplexität der Suchoperation. Die durchschnittliche Fallzeitkomplexität für Multiset ist O(logn) und unordered_multiset ist O(1). Dasselbe gilt für multimap undordered_multimap.

Ein Beispiel, bei dem eine Multimap nützlich wäre, wenn Sie eine Situation hätten, in der die Schlüssel die meiste Zeit eindeutig sind, aber manchmal nicht.

Wenn Sie beispielsweise eine Cache-Klasse erstellen, die einen Hash als Schlüssel verwendet. Meistens haben zwei verschiedene Objekte nicht denselben Hash, sodass die Schlüssel eindeutig sind. Es ist jedoch möglich, dass Sie Hash-Kollisionen für verschiedene Objekte erhalten, daher möchten Sie, dass eine Multimap diese Situation abdeckt.

Ein weiteres Beispiel wäre jede Art von nicht eindeutigem Index (wie in einer Datenbank).

Was ein Multiset betrifft – ich denke, das wäre weniger nützlich. Das einzige, was mir einfällt, wäre, es als eine Art automatisch sortierte Liste zu verwenden.

Ein Multiset oder eine Multimap ist einfach für Situationen gedacht, in denen mehrere Elemente eines bestimmten Elements vorhanden sein können. Angenommen, Sie möchten einen Index für ein Buch erstellen. Sie würden den Text durchgehen, alle wirklich gebräuchlichen bedeutungslosen Wörter (“ein”, “eine”, “der” usw.) wegwerfen und dann eine Liste aller anderen erstellen und die Stelle im Buch angeben, an der sie sich befinden aufgetreten.

Nicht wenige der Wörter erscheinen auf mehr als einer Seite, in diesem Fall haben Sie mehrere Einträge, die von einem Wort auf verschiedene Seiten abgebildet werden. Eine Möglichkeit, damit umzugehen, wäre eine Multimap von Wörtern zu Seitenzahlen.

http://www.cplusplus.com/reference/stl/multimap/

Maps sind eine Art assoziative Container, in denen Elemente gespeichert werden, die durch die Kombination eines Schlüsselwerts und eines zugeordneten Werts gebildet werden, ähnlich wie Map-Container, aber zulassen, dass verschiedene Elemente denselben Schlüsselwert haben.

Es ist eine Art Registrierung, in der Elemente einen Schlüssel gemeinsam nutzen können. Sie können an Unternehmen und Mitarbeiter denken. Adresse ist ein Schlüssel und Mitarbeiter sind Werte.

Benutzer-Avatar
entspannen

Hier ist was Wikipedia sagt über die Verwendung:

  • In einem Studentenregistrierungssystem, in dem Studenten gleichzeitig in mehreren Klassen eingeschrieben sein können, kann es eine Zuordnung für jede Einschreibung eines Studenten in einen Kurs geben, wobei der Schlüssel die Studenten-ID und der Wert die Kurs-ID ist. Wenn ein Student in drei Studiengängen eingeschrieben ist, gibt es drei Assoziationen mit demselben Schlüssel.
  • Der Index eines Buchs kann eine beliebige Anzahl von Referenzen für einen gegebenen Indexbegriff melden und kann somit als Multimap von Indexbegriffen zu einer beliebigen Anzahl von Referenzpositionen codiert werden

Benutzer-Avatar
Erich

Verwenden Sie Multimap, wo immer Sie eine Baumstruktur verwenden möchten.

  • [This answer was flagged automatically as a “late answer to an old question, provided by a new user. This comment is in that context.] Diese Antwort scheint keine Begründung zu geben oder irgendeinen Forschungswert zu haben. Erwägen Sie daher, die Antwort entweder erheblich zu erweitern oder vollständig zu löschen. Vielen Dank!

    – danfuzz

    5. November 2012 um 23:11 Uhr

1012120cookie-check“multiset” & “multimap” – Was ist der Sinn?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy