Q:

Algorithm: Merging std::unordered_maps

I have the following problem:
I have n hashmaps (Let's call them A.1, A.2, ..., A.n) that maps from std::string to boost::variant and I want to merge them into a single hashmap (Let's call that one B) as follows:

If A.1, A.2, ... A.n contains the same value for key K, then B should contain the same value for key K.
If there exists some key K which is not present in one of the maps A.1, A.2, ... A.n, then B should contain a mapping from key K to value boost::blank. 
If there exists some value for key K in A.1, A.2, ... A.n that differs from the other values, then B should contain a mapping from key K to value boost::blank. 

I have to do this quite a lot, and I know it will become a bottleneck.  What is the most efficient way to achieve this?  Any library support for merging hashmaps like this? 
Edit: If another datastructure is more appropriate, please let me know.  I do, however, require O(1) lookups

A:

If I am reading this correctly you are looking for an O(N log N) solution.   Without having the C++ experience to write a proper implementation what you want to do is something along these lines:  
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

