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

Question

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?

You probably need to implement your own specialization of std::hash. — Some programmer dude
– Some programmer dude, Commented Sep 5, 2012 at 10:05

ecatmur · Accepted Answer · 2012-09-05 10:28:03Z

3

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.

edited Sep 5, 2012 at 10:28

answered Sep 5, 2012 at 10:06

ecatmur

158k28 gold badges311 silver badges387 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kerrek SB · Accepted Answer · 2012-09-05 10:06:25Z

0

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

answered Sep 5, 2012 at 10:06

Kerrek SB

480k96 gold badges904 silver badges1.1k bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related