How to use an unordered_map of fixed array and int?

Question

My code works just fine when I use map< array<int,FIXEDSIZE>, int> but not when I use unordered_map< array<int,FIXEDSIZE>, int>.

It creates this massive list of errors so I don't really know what's wrong. Things like "value" is not a member, or "no match for operator[]", etc.

This is how I am using my map (which I name cache):

if (cache.find(key) != cache.end()) return cache[key];

and

cache[key] = valueToMemoize;

@101010 Memoization speed. In my experience, whenever unordered_map works, it's always a heck of a lot faster than using a regular map. I am trying to get unordered_map to work so I can compare. — user5613205, Nov 27 '15 at 22:09
You need to write a hasher. `std::array` comes with comparison operators (making it usable in `map`s), but no hashers. — T.C., Nov 27 '15 at 22:11
@T.C. How would I do that for this particular case? I am not familiar with writing hashers or how I'd get it to speak to this datatype / whenever I use it like I've described. — user5613205, Nov 27 '15 at 22:11
As a side note, `if (cache.find(key) != cache.end()) return cache[key];` searches for `key` twice. You should use `at` for that, or access the value by the iterator. — LogicStuff, Nov 27 '15 at 22:16
Unless there is a better way to memoize a small array of integers (with values < 128 each)? — user5613205, Nov 27 '15 at 22:16
@LogicStuff Sorry, I am not familiar. What do you mean using `at`? How is it searching for the key twice when I only use `find()` once? — user5613205, Nov 27 '15 at 22:17
@LogicStuff I assumed it was constant-time lookup when you already know the index. To my knowledge `operator[]` is not a search unless I am really mistaken about how maps work — user5613205, Nov 27 '15 at 22:18
@user5613205 `[]` searches for it again, but `at()` doesn't help either. — T.C., Nov 27 '15 at 22:19
"memoize a small array of integers (with values < 128 each)". `std::string` should work in a pinch. — n. m. could be an AI, Nov 27 '15 at 22:19
@T.C. I mean `at` replacing it all, with catching the exception to determine failure. — LogicStuff, Nov 27 '15 at 22:19
Is there no better way to do a "return value if corresponding key is in cache"? — user5613205, Nov 27 '15 at 22:20

T.C. · Accepted Answer · 2015-11-27T22:31:25.890

2

This is basically what boost::hash_combine boils down to:

void hash_combine(std::size_t& seed, std::size_t value) {
    seed ^= value + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

A simple hasher for containers - hash all of their elements using std::hash, and combine them.

struct container_hasher {
     template<class T>
     std::size_t operator()(const T& c) const {
         std::size_t seed = 0;
         for(const auto& elem : c) {
             hash_combine(seed, std::hash<typename T::value_type>()(elem));
         }
         return seed;
     }
};

Use:

std::unordered_map<std::array<int, 10>, int, container_hasher> my_map;

For cheaper lookup, do

auto r = cache.find(key);
if(r != cache.end()) return r->second;

For std::map, you might want to use lower_bound instead, to help with the later insertion:

auto lb = cache.lower_bound(key);
if(lb != cache.end() && lb->first == key) return lb->second;
cache.emplace_hint(lb, key, valueToMemoize);

edited Nov 27 '15 at 22:31

answered Nov 27 '15 at 22:27

T.C.

133,968
17
288
421

I had found something similar at http://stackoverflow.com/questions/7222143/unordered-map-hash-function-c so I am at least happy to know I was on the right track. Thank you for this! I'll have to study this a little to better understand how it works. – user5613205 Nov 27 '15 at 22:30
Also what is `value + 0x9e3779b9 + (seed<<6) + (seed>>2);`? – user5613205 Nov 27 '15 at 22:31
@user5613205: Note that combining hashes produces low-quality hashing which may perform poorly on certain inputs (and is attackable). While hash combining can be used to make the code "work", there's no substitute for hashing all the ingredient bits of the data in one go -- which is not easy to do with the current library design. – Kerrek SB Nov 27 '15 at 22:42

score 0 · Answer 2 · answered Nov 27 '15 at 22:27

You need to define your custom hash object like below:

template<typename T, std::size_t N>
class arrayHash {
public:
  std::size_t operator()(std::array<T, N> const &arr) const {
    std::size_t sum(0);
    for(auto &&i : arr) sum += std::hash<T>()(i);
    return sum;
  }
};

And then define your unordered_map as:

std::unordered_map<std::array<int, FIXEDSIZE>, int, arrayHash<int, FIXEDSIZE>> umap;

Live Demo

How to use an unordered_map of fixed array and int?

2 Answers2