2

我想使用一个整数数组作为 unordered_map 的键。基本思想是我有许多不同的问题状态，它们表示为int state[16]。数组的值是从 0 到 15 的数字排列，例如：

a= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; 
b= { 14, 1, 9, 6, 4, 8, 12, 5, 7, 2, 3, 0, 10, 11, 13, 15}; ...

这些将是 unordered_map 中的键（值将是一个包含其他东西的类）。我怎样才能做到这一点？我是否需要实现一个新的哈希函数来比较这些值，或者我可以使用 C++ 提供的一些？我的目标是将其用作哈希表，还有其他更好的选择吗？

4

2 回答 2

3

16！大约为 2*10^13，因此您可以将排列的序数存储在 64 位整数中并将其用作映射键，而无需存储或散列排列。

请参阅http://en.wikipedia.org/wiki/Permutation#Numbering_permutations了解 0 ... N-1 和数字 0 ... N 的排列之间的自然双射！- 1。

或者，您可以只使用std::map; 排列将是有效的字典比较。

第三种选择是使用 astd::string作为键，因为您的值很容易适合 a char; std::hash专门用于std::string.

于 2012-09-05T10:06:31.637 回答
0

您可以hash_range从 Boost 中使用。

namespace std
{
    template <typename T, typename A>
    struct hash<vector<T, A>>
    {
        size_t operator()(vector<T, A> const & v) const
        {
            return boost::range_hash(v.cbegin(), v.cend());
        }
    };
}
于 2012-09-05T10:06:25.273 回答