"multiset" & "multimap" - What's the point?

Question

As the question states ... I don't get the point about multisets / multimaps.

So, what's the purpose?

Solution 1

Some use cases:

multimap

• With ZIP code as a key, all people which have that ZIP code
• With account ID as key, all open orders of that person/account
• A dictionary, with per keyword various explanations

multiset

is in essence a map with a key and a integer count.

• The inventory of a shop, all products have their key and the amount still available is the value
• accumulated sales data of a shop, every time a product is sold the product id get's added to the multiset thereby increasing the amount sold

Solution 2

The most important benefit of using a multiset over a vector/list(or any other container) is the time complexity of find operation. average case time complexity for multiset is O(logn) and unordered_multiset is O(1). Same is true for multimap and ordered_multimap.

Solution 3

One example where a multimap would be useful if you had a situation where most of the time the keys are unique, but sometimes they aren't.

For example, if you were creating a cache class that used a hash as a key. Most of the time two different objects will not have the same hash, so the keys will be unique. But it is possible that you will get hash collisions for different objects, so you would want a multimap to cover that situation.

Another example would be any sort of non-unique index (like in a database).

As for a multiset - I think those would be less useful. Only thing I can think of would be to use it as a kind of automatically sorted list.

Solution 4

A multiset or multimap is simply for situations where there might be more than one of a particular item. For example, let's say you wanted to create an index for a book. You'd scan through the text, throw out all the really common meaningless words ("a", "an", "the", etc.) and then make a list of all the rest, and the place in the book where each occurred.

Quite a few of the words will appear on more than one page, in which case you'll have multiple entries mapping from one word to different pages. One way to handle that would be a multimap from words to page numbers.

Solution 5

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

Maps are a kind of associative containers that stores elements formed by the combination of a key value and a mapped value, much like map containers, but allowing different elements to have the same key value.

It is kind of registry where elements can share a key. You can think of companies and employees. Street address is a key and employees are values.

View more solutions

Comments

[Amit Kumar Gupta]

can you give any example for multiset

[danfuzz]

[This answer was flagged automatically as a "late answer to an old question, provided by a new user. This comment is in that context.] This answer does not appear to give any rationale or have any research value. As such, please consider either expanding the answer significantly or deleting it entirely. Thanks!