c++ - 算法:合并 std::unordered_map

Question

我有以下问题:

我有 n 个从 std::string 映射到 boost::variant 的 HashMap (我们称它们为 A.1、A.2、...、A.n)，我想将它们合并到一个 HashMap (我们称B) 如下:

1. 如果 A.1、A.2、...A.n 包含相同的 key K 值，则 B 应该包含相同的 key K 值。
2. 如果存在某个键 K 不存在于映射 A.1、A.2、... A.n 之一中，则 B 应包含从键 K 到值 boost::blank 的映射。
3. 如果 A.1、A.2、...A.n 中的键 K 存在与其他值不同的某个值，则 B 应包含从键 K 到值 boost::blank 的映射。

我必须经常这样做，而且我知道这会成为瓶颈。实现这一目标最有效的方法是什么？有库支持像这样合并 HashMap 吗？

编辑:如果其他数据结构更合适，请告诉我。然而，我确实需要 O(1) 查找

Answer 1

如果我没看错的话，您正在寻找一个O(N log N) 解决方案。如果没有 C++ 经验来编写正确的实现，您想要做的就是以下几行:

1) Push all of the elements from every map into a `Set`   `O(N) + overhead of checking existence O(1)`  
   A)  define the elements of the set by a hash value generated by `Key + Value`   
      a)  that is `A:hello`  creates a different value than `B:hello`  
2) Perform a merge sort `O(N log N)` based on the values  
3) Start at the beginning of your `sorted set` and iterate over the values.  
   A) If a value is found multiple times this satisfies your `3` step  
   B) Your `2` step can be satisifed in `O(1)` time by looking up the key