如何使用固定数组和整数的unordered_map？

Question

我的代码在我使用 map< array<int,FIXEDSIZE>, int> 时工作正常，但在我使用 unordered_map< array<int,FIXEDSIZE>, int>.

时却不行

它产生了如此庞大的错误列表，所以我真的不知道出了什么问题。诸如 "value" 不是会员，或 "no match for operator[]" 等

这就是我使用地图（我将其命名为 cache）的方式：

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

和

cache[key] = valueToMemoize;

Answer 1

您需要像下面这样定义您的自定义哈希对象：

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;
  }
};

然后将您的 unordered_map 定义为：

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

Live Demo

Answer 2

这基本上就是 boost::hash_combine 归结为：

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

一个简单的容器散列器 - 使用 std::hash 散列它们的所有元素，然后组合它们。

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;
     }
};

使用：

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

为了更便宜的查找，

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

对于 std::map，您可能希望使用 lower_bound 来帮助稍后插入：

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

如何使用固定数组和整数的unordered_map？

How to use an unordered_map of fixed array and int?

c++

arrays

dictionary

unordered-map