CODEWITHSUNDEEP
c++hashstduuidunordered-map
danijar
danijar

Reputation: 34185

How to directly use key as hash for std::unordered_map?

The keys in my std::unordered_map are boost::uuids::uuids, thus 128 bit hashes considered unique. However, the compiler can't know that and therefore says this.

error C2338: The C++ Standard doesn't provide a hash for this type.

How can I make the map use the keys as hashes as they are? By the way, std::size_t is defined as unsigned int __w64 on my system, which I think refers to only 64 bits.

Upvotes: 3

Views: 6062

Answers (4)

danijar
danijar

Reputation: 34185

I found no way to use UUIDs as keys for std::unordered_map since the UUID is 128 bits long while the hash for the map is std::size_t which only can hold 64 bits.

Instead, I dropped real 128 bits UUIDs for only 64 bit ids which can be stored in the uint64_t type and are natively supported by containers of the standard library.

Upvotes: 0

Dietmar Kühl
Dietmar Kühl

Reputation: 153830

You always need to provide a function object mapping the key to a hash value even if this mapping is the identity. You can either define a specialization for std::hash<boost::uuids::uuid> and have the std::unordered_map<K, V> pick this one up automatically or you can parameterize the unordered map with additional template parameter for the function object type. In addition to the hash an equality operation is also needed but the default, using operator==() is probably OK.

That said, the hash value won't accept a 128-bit integer unless your system has a built-in 128-bit integer type. The hash value needs to be a std::size_t to be usable with the standard unordered containers. The complete list of requirements for std::hash<T> specializations is listed in 20.8.12 [unord.hash]:

  1. std::hash<X> needs to be default constructible, copy constructible, and copy assignable.
  2. std::hash<X> needs to be swappable.
  3. It needs to provide two nested types argument_type for the key type and result_type for the type of the hashed value with the latter being the same as std::size_t.
  4. For the function the relation k1 == k2 => h(k1) == h(k2) needs to be true where h is the hashing function object.

So, you will need to define something along the lines of this:

namespace std {
    template <>
    struct hash<boost::uuids::uuid>
    {
        typedef boost::uuids::uuid argument_type;
        typedef std::size_t        result_type;
        std::size_t operator()(boost::uuid::uuid key) const {
            return transform_to_size_t(key);
        }
    };
}

where transform_to_size_t() is the actual transformation you'll need to provide. };

Upvotes: 2

Manu343726
Manu343726

Reputation: 14174

I think the simplest way is to implement an specialization of std::hash for that types, which returns the same input:

namespace std
{
    template<>
    struct hash<Foo>
    {
        Foo operator(const Foo& foo)
        {
            return foo;
        }
    };
}

Supposing that the type, Foo in the example, is implicitly convertible to std::size_t.

In your case, the type is a 128 bits GUID, and std::size_t uses 32 or 64 bits. You could split the 128 bits GUID in parts of 64/32 bits, and combine the values.

Upvotes: 0

CS Pei
CS Pei

Reputation: 11047

you need to provide a hash function for type boost::uuids::uuid. Since it is unique, you can just use stl identity.

Here is the declaration of unordered_map.

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

Upvotes: 1

Related Questions