std::hash specialization remains unused by std::unordered_map

Question

I am trying to extend std::hash<T> by supplying a specialization for const char, so that I can use const char* as key type in std::unordered_map.

This is what I tried:

#include <unordered_map>
#include <functional>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

namespace std
{
    template<>
    struct hash<const char*>
    {
        size_t operator()(const char* const& s) const
        {
           size_t h = 0;
           const char* tmp = s;

           while (*tmp)
              h = (h << 5) + h + (unsigned char)toupper(*tmp++);

           printf("hash of '%s' is (%ld)\n", s, h);
           return h;
        }
    };
}

int main(int argc, char* argv[])
{
   const char* name1= "Mark Nelson";
   const char* name2= strdup(name1);

   std::unordered_map<const char*, int> map;

   printf("Insert (%s)\n", name1);
   map[name1]= 100;

   printf("Lookup (%s)\n", name1);
   printf("map[%s](name1) = %d\n", name1, map.find(name1) != map.end() ? map.find(name1)->second : -1);
   printf("Lookup (%s)\n", name2);
   printf("map[%s](name2) = %d\n", name2, map.find(name2) != map.end() ? map.find(name2)->second : -1);

   return 0;
}

What the output is:

Insert (Mark Nelson)
hash of 'Mark Nelson' is (121066894705597050)
Lookup (Mark Nelson)
hash of 'Mark Nelson' is (121066894705597050)
hash of 'Mark Nelson' is (121066894705597050)
map[Mark Nelson](name1) = 100
Lookup (Mark Nelson)
hash of 'Mark Nelson' is (121066894705597050)
map[Mark Nelson](name2) = -1

So to me it seems, std::unordered_map is using my provided hash implementation for both the insertion as well as the lookup. But for some reason, it does not find the value via name2, which seems like it is still using pointer comparison instead.

What is wrong here? I am using GCC 4.8.2, and the file was compiled with g++ -std=c++11 main.cc

@Lingxi I agree to a certain degree, but you NEED to overload templates in their specific namespaces. — набиячлэвэли, May 14 '15 at 22:03

score 5 · Accepted Answer · edited May 23 '17 at 11:43

5

You need two things for an unordered map (ref):

A hash function
A comparison function for equality

So you have (1) which appears to work but then the map has to check the const char * for equality which devolves into a pointer comparison. To do this you can specify a custom comparator (ref):

struct cmp_str
{
   bool operator()(char const *a, char const *b)
   {
      return std::strcmp(a, b) == 0;
   }
};

std::unordered_map<const char*, int, std::hash<const char *>, cmp_str> BlahBlah;

edited May 23 '17 at 11:43

Community

1
1

answered May 07 '15 at 12:53

uesp

6,194
20
15

Thanks. I have implemented `std::equal_to` and now it works as expected. – user826955 May 07 '15 at 13:08
3

@user826955 You are only allowed to add specializations to `std` if it depends on a user-defined type, on pain of undefined behavior; neither your `hash` nor `equal_to` depends on one. Write your own hasher and comparator type rather than hijacking the standard ones. – T.C. May 08 '15 at 08:01
Problem really is, that when I define my hasher and compare function, I agree that the same thing is achieved, but the usage gets way more uncomfortable if you intend to work with wrappers around the STL. e.g. `template class FoobarMar` as propietary implementation which *uses* the `std::map`. Exending `std` namespace will just make it work, while supplying functions will complicate the API (especially when using inheritance). Note that we generally do not use `std` namespace. – user826955 May 18 '15 at 07:05

std::hash specialization remains unused by std::unordered_map

1 Answers1