CODEWITHSUNDEEP
c++hashtableunordered-map
FrankS101
FrankS101

Reputation: 2135

How to use an integer array as a key of an unordered_map

I would like to use an integer array as a key of an unordered_map. The basic idea is that I have many different states of a problem which are represented as int state[16]. The values of the array are permutations of numbers from 0 to 15, like:

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

and those will be the key in the unordered_map (the value will be a class with other stuff). How can I do that? Do I need to implement a new hash function to compare the values or I can use some provided by C++? My goal is using this as a hash-table, is there any other better alternative?

Upvotes: 2

Views: 2146

Answers (2)

ecatmur
ecatmur

Reputation: 157344

16! is approximately 2*10^13, so you can store the ordinal of the permutation in a 64-bit integer and use that as a map key, without needing to store or hash the permutation.

See http://en.wikipedia.org/wiki/Permutation#Numbering_permutations for the natural bijection between permutations of 0 ... N-1 and the numbers 0 ... N! - 1.

Alternatively, you could just use a std::map; permutations will be efficient to compare lexicographically.

A third alternative would be to use a std::string as the key, since your values easily fit within a char; std::hash is specialized for std::string.

Upvotes: 3

Kerrek SB
Kerrek SB

Reputation: 477040

You can use hash_range from 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());
        }
    };
}

Upvotes: 0

Related Questions