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;
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);
value + 0x9e3779b9 + (seed<<6) + (seed>>2);?
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;
std::arraycomes with comparison operators (making it usable inmaps), but no hashers.if (cache.find(key) != cache.end()) return cache[key];searches forkeytwice. You should useatfor that, or access the value by the iterator.[]searches for it again, butat()doesn't help either.