Как использовать целочисленный массив в качестве ключа unordered_map

Я хотел бы использовать массив целых чисел в качестве ключа 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 ++?
Моя цель — использовать это как хеш-таблицу, есть ли другая лучшая альтернатива?

2

Решение

16! примерно 2 * 10 ^ 13, так что вы можете сохранить порядковый номер перестановки в 64-битном целом числе и использовать его в качестве ключа карты, без необходимости сохранять или хешировать перестановку.

Увидеть http://en.wikipedia.org/wiki/Permutation#Numbering_permutations для естественной биекции между перестановками 0 … N-1 и числами 0 … N! — 1

В качестве альтернативы, вы можете просто использовать std::map; Перестановки будет эффективно сравнивать лексикографически.

Третий вариант будет использовать std::string в качестве ключа, так как ваши ценности легко вписываются в char; std::hash специализируется на std::string,

3

Другие решения

Ты можешь использовать 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());
}
};
}
0