算法：合併的std :: unordered_maps

Question

我有以下問題：

我有n個包含HashMap（我們姑且稱之爲A.1，A.2，...，An）的，從的std :: string映射到boost :: variant，我想把它們合併成一個hashmap（讓我們稱之爲B）如下：

1. 如果A.1，A.2，... An包含相同的鍵值K ，那麼B應該包含與關鍵字K相同的值。
2. 如果在映射A.1，A.2，... An之一中不存在某個關鍵K，則B應該包含從鍵K值boost :: blank。
3. 如果A.1，A.2，... A.n中的鍵K存在一些與其他值不同的值，那麼B應該包含從鍵K到值boost :: blank的映射。

我必須這樣做很多，我知道它會成爲一個瓶頸。什麼是最有效的方法來實現這一目標？任何圖書館支持合併這樣的hashmaps？

編輯：如果其他數據結構更合適，請讓我知道。但是，我確實需要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 

Answer 2

這裏是我的算法中（剛剛超過所有元素迭代）：

1. std::unordered_map<string, variant> result
2. 選號地圖中的大部分條目都是O（n）。
3. 迭代通過最大地圖的每個元素 - > O（M）
   1. result[current_key] = current_value
   2. 對於彼此地圖 - > O（N-1）
      1. 查找鍵 - > O（1）
      2. 如果缺席 - >result[current_key] = blank。到最大的地圖中的下一個項目。
      3. [重要禮物] If current_value != map[key] - >result[current_key] = blank。到最大的地圖中的下一個項目。
      4. [關鍵的禮物]在最大的地圖中得到下一個項目。

這就是全部。你有O（n）+ O（m * n），它等於O（m * n）。由於@ Woot4Moo的算法的步驟（2）需要O（m * n）* log（m * n），這似乎不像@ Woot4Moo的算法。

我不確定是否有可能以直接的方式比O（m * n）更快。我想你會需要一些實時處理來更快地完成這項工作。但！！！這些緩存不是很安全。所以，首先考慮簡單的算法。也許它不會阻礙你的應用程序。