Intersection of two unordered_maps

Question

Basically my question is the same as Intersection of two STL maps, but with two unordered_maps:

std::unordered_map<Key, Value> A;
std::unordered_map<Key, Value> B;

I'd like get the intersection, something similar to

std::unordered_map<Key, std::pair<Value, Value>> C;

where the keys are the values in both A and B and the value is a pair of the values from A and B respectively.

What is the fastest way to achieve this? Currently I iterate over the smallest of both and query for the key in the second. Fortunately often my key type is quite simple to hash, but I did not find a means to get the hash value of my key of the iterated map to spare the computation of the hash for the second (to be clear: I don't know how to recover the hash without recomputing it again, and where to find something like find with a computed hash as argument [1]).

Thanks.

[1] Yeah, I know, early optimization is the root of plenty of diseases. Yet I'd like to know if this is possible, not an explanation about how this would be a can of bugs. And actually, in some cases, depending on user input, the keys can be complex and costly to hash.

Answer 1

I know you don't want to hear it, but I'm going to say it anyway: you should cache the hash value on the instances so that hashing reduces to simple member lookup. If the instances are immutable (or at least, the parts that go into the hash function are immutable), then the easiest way to do this is to compute the hash in the constructor.

Answer 2

If the key was really expensive to hash, you could avoid one of the hashing at the expense of having A and B of type std::unordered_map<Key, std::pair<Value, Value>> from the beginning.(with the pair.second to a default constructed Value)

Supposing you don't need the original A and B once the intersection has been computed, you could just iterate through the smallest of the 2 (Assume B is the smallest) :

--> Move B in C

 for (auto it = C.begin(); it != C.end();it++ ) {
   auto res = A.find(it->first);
    if(res == A.end() )
        {               
            //Can't call C.erase(it) here as it would cause problem in the loop                 
            v.push_back(it); 
        }
        else
        {
            // Assign the second value of the pair to the value obtained in A.
            it->second.second = res->second.first;
        }     
  }
for( auto it : v)
  C.erase(it);

This would leave you with C filled with pairs where the pair.first is the value that was in B, and pair.second is the value that was in A

If you need to keep A and B untouched, instead of Moving B in C, just copy B in C.