I implemented a search caching results that consist of keys of type State (a class with 7 short ints) and values of type Score
(a class of 3 doubles.) Using unordered_map was at least 20 times slower than map. Why?
Edit: Darn it! My hash function was
namespace std {
size_t hash<State>::operator()(State const& s) const {
size_t retval = hash<short>()(s.s[0]);
for (int i = 1; i < R; i += 2) { // 1 3 5
int x = (static_cast<int>(s.s[i + 1]) << 16)
+ (static_cast<int>(s.s[i]));
hash_combine(retval, x);
}
}
}
I forgot to return retval
, so it was all colliding! I wish unordered_map had a hash_function_quality() function that reports the average number of collisions.
std::map
still. It's just about 19 operations to access an element. Any computer performs 19 operations real quick. Even the prototypical computers from the 1950s. – wilhelmtell Jan 31 '11 at 1:22