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

As the question states ...开发者_运维百科 I don't get the point about multisets / multimaps.

So, what's the purpose?

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

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.

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.

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.

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.

Here's what Wikipedia says about uses:

• In a student enrollment system, where students may be enrolled in multiple classes simultaneously, there might be an association for each enrollment of a student in a course, where the key is the student ID and the value is the course ID. If a student is enrolled in three courses, there will be three associations containing the same key.
• The index of a book may report any number of references for a given index term, and thus may be coded as a multimap from index terms to any number of reference locations

Use multimap, wherever you want to use tree kind of a structure.