如何在 multimap 中计算重复对的数量

Question

如何计算一个整数对的multimap中重复（键和值相同）的对数？

例如，我的multimap包含{(6,2)，(6,2)，(6,3)和(6,4)}这些对，因此重复计数为1，因为我的multimap中有1个重复的对。我尝试使用find()和count()等方法，但都没有成功。任何帮助将不胜感激！

- Chew Kah Meng

---

我强烈建议你展示你的最佳尝试（以 [mcve] 格式）。它可能只需要进行微小的修正，如果不是这样的话，也能提供一个基线，人们可以在此基础上撰写最符合你目标的答案。另外，不要低估展示你已经花费时间解决问题的社交效益，而不仅仅是期望别人替你完成工作。 - user4581301

感谢您的回复，很抱歉我没有必要的代码，因为这只是我的算法中的一个想法，我不确定它是否有效。然而，我正在考虑比较multimap中的每一对，但我不确定如何做到这一点。 - Chew Kah Meng

使用您的multimap创建std::set: std::set<std::pair<int,int>> s{m.begin(),m.end()};（其中m是multimap），您将得到重复数：m.size() - s.size()。 - rafix07

如果_values_绑定到某个int的小区间，大小为_k_，则可以使用线性复杂度和_O(k)_辅助内存存储快速完成此操作。遍历算法在这里的第二个答案中，要计算特定键的重复项，您只需要一个大小为_k_的数组即可。这可能比使用set / unorered_set更快，其中会发生动态内存分配。 - Daniel Langr

谢谢@rafix07，你应该考虑把那个变成一个答案！ - Chew Kah Meng

实时演示在这里。事实上，它的复杂度是_O(nk)_，但每次迭代中的_k_部分只是重置数组，在实践中将非常快速。 - Daniel Langr

Answer 1

一种常见的方法是使用 std::set。它不能包含重复数据。

我们将尝试使用其范围构造函数将所有数据放入 std::set 中。使用 CTAD 可以使编写更加容易。

然后，我们比较 std::multimap 和 std::set 的大小，并得到所有重复项的数量。

因此，这归结为一个非常简单的程序。请参见：

#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;
}

如果有不同的要求，请反馈给我，我将创建一个额外的解决方案。

- A M