Блог пользователя utsavsingh899

Use cases for multiset and unordered_multiset
Автор utsavsingh899, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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).

      → Ответить