4

how can I count the number of duplicate pairs (with same key and value) in a multimap of pairs of integers?

For example, my multimap contains the pairs {(6,2), (6,2), (6,3) and (6,4)} so the duplicate count is 1 as I have 1 duplicate pair in my multimap. I have tried using methods such as find() and count() but to no avail. Any help will be greatly appreciated!

Chew Kah Meng
  • 227
  • 1
  • 10
  • 3
    I strongly recommend you show your best attempt (in [mcve] format). It might only need a small correction and if not, it provides a baseline around which people can compose answers that best fit your goals. Plus do not discount the social benefits of demonstrating you've invested time in solving the problem and aren't simply expecting to get others to do your work for you. – user4581301 Feb 21 '20 at 16:03
  • Thanks for the reply, apologies for not having the necessary code as this is just an idea in my algorithm and I am not sure whether it'll work. However, I was thinking along of the lines of comparing every pair in the multimap but I am unsure how to do so. – Chew Kah Meng Feb 21 '20 at 16:11
  • 6
    Make `std::set` from your multimap, `std::set> s{m.begin(),m.end()};` (where `m` is multimap) and number of duplicates you will get by : `m.size() - s.size()`. – rafix07 Feb 21 '20 at 16:13
  • 1
    If the _values_ are bounded to some **small interval** of `int`, say of size _k_, you can do this quickly with linear complexity and _O(k)_ auxiliary memory storage. Traversal algorithm is [here in the second answer](https://stackoverflow.com/q/9371236/580083), to count duplicates for a particular key, you just need an array of size _k_. It might be then much faster than using a set/unorered_set, where dynamic memory allocations occur. – Daniel Langr Feb 21 '20 at 16:25
  • Thank you @rafix07, you should consider making that an answer! – Chew Kah Meng Feb 21 '20 at 16:25
  • The live demo is [here](https://wandbox.org/permlink/ngXdR0gQguUuuDqd). In fact, it's complexity is _O(nk)_, but the _k_ part in each iteration just resets the array, which will be extremely quick in practice. – Daniel Langr Feb 21 '20 at 16:36

1 Answers1

2

One common approach is to use a std::set. This cannot contain duplicate data.

We will try to put all data into the std::set using its range constructor. Using CTAD makes writing easier.

Then we compare the size of the std::multimap with that of the std::set and have the number of all duplicates.

So it boils down to a very simple program. Please see:

#include <iostream>
#include <map>
#include <set>

int main()
{
    // Source data
    std::multimap<int, int> mm = { {6, 2}, {6, 3}, {6, 2}, {6, 4} };

    // Use range constructor and CTAD to put the data into a set
    std::set s(mm.begin(), mm.end());

    // Show result
    std::cout << "Number of duplicates: " << mm.size() - s.size() << "\n";

    return 0;
}

If there are different requirements, then please feedback and I will create an additional solution.

A M
  • 14,694
  • 5
  • 19
  • 44