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, In English,

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

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem Statement:

You start with an empty list and you are given three types of queries.

  1. Insert to the list a string.

  2. Delete from the list a single appearance of a string (if exists).

  3. Print "yes" if a string appears to the list at least once, otherwise "no".

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This can be done using map, then what was the need for creating multiset?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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).