如何在unordered_map向量中检测重复项？ [英] How to detect duplicates in a vector of unordered_map?

问题描述

给出一个 vector 的 unordered_map< u_int，int> ，
我想检查一下向量包含任何重复的值。如果两个unordered_maps的所有键及其对应的值都相等，则将其视为重复的。
我知道 unordered_maps 存在比较运算符，但是我想避免每个元素之间的成对比较。一种经典的解决方案是将 vector 的值插入到 set 中，然后比较元素中的元素数量。 set 和 vector 。
但是，这里的问题是要插入到 set 中的对象必须重载比较运算符。在 unordered_set 的情况下，必须为复杂对象重载要使用的哈希函数。为了重载，我需要从 std :: unordered_map 派生一个类。然后，我需要重载比较运算符或哈希函数。我可以想到的另一种解决方案是将所有键值对连接为一个字符串，然后按键对字符串进行排序并检测这些字符串上的重复项。我想知道什么是解决此问题的最佳解决方案。

示例数据

Given a vector of unordered_map<u_int,int>, I would like to check if the vector contains any duplicated values. Two unordered_maps are considered duplicated if all of their keys and their corresponding values are equal. I know the comparison operator exists for unordered_maps, but I would like to avoid the pairwise comparison of each element with each other. One classical solution is to insert the values of the vector into a set, then to compare the number of elements in the set and the vector. However, the problem here is that the object to be inserted into the set must have the comparison operators overloaded. In case of the unordered_set, the hash function to be used must be overloaded for the complex object. In order to overload, I need to derive a class from the std::unordered_map. Then I need to overload either the comparison operator or the hash function. Another solution that I could think of is to concatenate all of the key value pairs into a string, then sort the string by the keys and detect the duplicates on those strings. I wonder what would be the best solution for this problem.
Example data:

using namespace std;
typedef unordered_map<u_int,int> int_map;
int_map a = { {1,1}, {2,4}, {3,5} };
int_map b = { {1,1}, {2,-1}, {4,-2} };
int_map c = { {1,1}, {3,5} };

vector<unordered_map<u_int,int>> my_vec;

my_vec.push_back(a);
my_vec.push_back(b);
my_vec.push_back(c);

my_vec 的内容为：

 { { 1 => 1, 2 => 4, 3 => 5 }, 
 { 1 => 1, 2 => -1, 4 => -2 }, 
 { 1 => 1, 3 => 5 } }

如果问题不清楚，请随时提出/建议/编辑。
任何帮助将不胜感激。

Please feel free to ask/commend/edit if the question is not clear enough. Any help would be appreciated. Thank you in advance!

推荐答案

如果您可以为std :: unordered_map获得良好的哈希函数，那么您应该这样做可能：

If you can get a good hash function for std::unordered_map then you should do it like this probably:

bool has_distinct_values(const std::vector<std::unordered_map<u_int, int>> v)
{
  std::unordered_map<int, std::list<int>> hash_to_indexes_map; 
  for(auto i = 0u; i < v.size(); ++i)
  {
    auto empl_result = hash_to_index_map.emplace(custom_hash(v[i]), {i});
    if (!empl_result.second)
    {  
       for (auto index : empl_result.first->second)
       {
         if (v[index] == v[i]) return false;
       }
       epmpl_result.first->second.push_back(i);
    }
  }
  return true;
}

算法简单明了：将映射哈希值映射到列表索引，每当进行成对映射比较哈希值相等。
这样，您可以避免复制整个地图，并获得O（N）（主要取决于您提供的哈希函数的质量）的时间复杂度，通常情况下很好。

The algorithm is straightforward: map hashes to list indexes, doing pairwise map comparison whenever hashes are equal. This way you avoid copying the entire maps, get O(N) (depending mostly on the quality of the hash function you provide) time complexity and generally are good to go.

这篇关于如何在unordered_map向量中检测重复项？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！