时间戳

首页 > 解决方案 > 如何检测 unordered_map 向量中的重复项？

c++ - 如何检测 unordered_map 向量中的重复项？

问题描述

给定 a vector，unordered_map<u_int,int>我想检查 是否vector包含任何重复值。如果两个 unordered_map 的所有键和对应的值都相等，则认为它们是重复的。我知道比较运算符存在于unordered_maps，但我想避免每个元素相互之间的成对比较。一种经典的解决方案是将 的值vector插入 a ，然后比较和set中的元素数量。但是，这里的问题是要插入的对象必须具有重载的比较运算符。在 的情况下，必须为复杂对象重载要使用的散列函数。为了重载，我需要从setvectorsetunordered_setstd::unordered_map. 然后我需要重载比较运算符或哈希函数。我能想到的另一个解决方案是将所有键值对连接成一个字符串，然后按键对字符串进行排序并检测这些字符串上的重复项。我想知道这个问题的最佳解决方案是什么。
示例数据：

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

如果问题不够清楚，请随时询问/评论/编辑。任何帮助，将不胜感激。先感谢您！

标签： c++algorithmc++11hashhashmap

解决方案

您可以类似于以下内容：

typedef unordered_map<u_int,int> int_map;

struct my_map_comparator
{
    bool operator()(const int_map& a, const int_map& b) 
    { 
      a_hash = compute_hash_for_a(all keys of a)
      b_hash = compute_hash_for_b(all keys of b)

      return a_hash == b_hash; 
    }
};

std::unordered_set<int_map,std::hash<int_map>, my_map_comparator> map_list();

推荐阅读