Пересечение двух unordered_maps

Question

В основном мой вопрос такой же, как Intersection of two STL maps, но с двумя unordered_maps:

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

Я хотел бы получить перекресток, нечто похожее на

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

где ключи значения как в A, так и в B, а значение представляет собой пару значений из A и B соответственно.

Каков самый быстрый способ достичь этого? В настоящее время я перебираю самый маленький из них и запрашиваю ключ во втором. К счастью, мой ключевой тип довольно прост для хэша, но я не нашел способ получить хэш-значение моего ключа итерированной карты, чтобы избавиться от вычисления хеша для второго (яснее: я не знаю как восстановить хэш без повторного его повторения и найти что-то вроде find с вычисленным хэшем в качестве аргумента [1]).

Спасибо.

[1] Да, я знаю, ранняя оптимизация - это корень многих болезней. Тем не менее, я хотел бы знать, возможно ли это, а не объяснение того, как это может быть проблема с ошибками. И фактически, в некоторых случаях, в зависимости от пользовательского ввода, клавиши могут быть сложными и дорогостоящими для хеша.

Answer 1

Я знаю, что вы не хотите его слышать, но я все равно скажу: вы должны кэшировать значение хэша на экземплярах, чтобы хэширование сводилось к простому поиску элемента. Если экземпляры являются неизменяемыми (или, по крайней мере, части, которые входят в хеш-функцию, неизменяемы), тогда самый простой способ сделать это - вычислить хэш в конструкторе.

Answer 2

Если ключ был действительно дорогой хэш, вы могли бы избежать одной из хэширования за счет наличия А и В типа std::unordered_map<Key, std::pair<Value, Value>> с самого начала. (С pair.second по умолчанию строится значение)

Предположив вам не нужен оригинал а и в, как только пересечение было вычислено, можно просто перебирать наименьшее из 2 (Предположим, что B является наименьшим):

-> Переместить B в 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); 

Это оставило бы вас с C, заполненным парами, где пара. Первая - это значение, которое было в B, а пара - это значение, которое было в A

Если вам нужно сохранить A и B нетронутыми, вместо этого Перемещение B в C, просто скопируйте B в C.