In STL-speak, a "set" is an ordered, deduplicated collection of elements. So naturally, a "multiset" is an ordered, non-deduplicated collection of elements! Its memory layout is exactly the same as the layout of std::set; only its invariants are different. Notice in the following diagram that std::multiset allows two elements with value 42:
![](https://static.packt-cdn.com/products/9781787126824/graphics/assets/3a1c1ec6-5407-4b6d-9def-a3ee77aa1a6c.png)
std::multiset<T, Cmp> behaves just like std::set<T, Cmp>, except that it can store duplicate elements. The same goes for std::multimap<K, V, Cmp>:
std::multimap<std::string, std::string> mm;
mm.emplace("hello", "world");
mm.emplace("quick", "brown");
mm.emplace("hello", "dolly");
assert(mm.size() == 3);
// Key-value pairs are stored in sorted order.
// Pairs...