Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### utsavsingh899's blog

By utsavsingh899, history, 5 weeks ago, ,

Hi, I recently studied about multisets in C++ STL, but I couldn't find any suitable use case where it may be used. If anyone could suggest some use cases and some problems where multiset or unordered_multiset could be used then it would be highly appreciated. Thanks

• +11

 » 5 weeks ago, # | ← Rev. 4 →   0 Problem Statement:You start with an empty list and you are given three types of queries. Insert to the list a string. Delete from the list a single appearance of a string (if exists). Print "yes" if a string appears to the list at least once, otherwise "no".
•  » » 5 weeks ago, # ^ |   0 This can be done using map, then what was the need for creating multiset?
•  » » » 5 weeks ago, # ^ |   +11 Well, technically speaking you can always simulate multiset with a map. Just keep track of the count of each element. But then it becomes more verbose. For example, removing an element, instead of c.erase(c.find(x)) becomes: auto it=c.find(x); if (it!=c.end()) { it->second--; if (it->second==0) c.erase(it); } And getting the count of a particular element is also more verbose than just c.count(x).In the end, multiset is just what it is — a set which allows duplicate elements. It's just there for convenience. And if you think about it, it is also possible to simulate priority_queue with a map, but I prefer using priority_queue because it is more convenient. Same goes for multiset. (Well, of course the constant in map is a bit higher than in PQ, but for most problems it's not that much of a difference).
•  » » » » 5 weeks ago, # ^ |   0 Thanks