C++ Hash function for string in unordered_map

Question

It seems as if C++ does not have a hash function for strings in the standard library. Is this true?

What is a working example of using a string as a key in an unordered_map that will work with any c++ compiler?

Solution 1

C++ STL provides template specializations of std::hash for the various string classes. You could just specify std::string as key type for std::unordered_map:

#include <string>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> map;
    map["string"] = 10;
    return 0;
}

Solution 2

I ran into this today (actually with wstring, not string, but it's the same deal): using wstring as a key in an unordered_map generates an error about no hash function being available for that type.

The solution for me was to add:

#include <string>

Believe it or not, without the #include directive I still had the wstring type available but apparently NOT the ancillary functions like the hash. Simply adding the include above fixed it.

Solution 3

Actually, there is std::hash<std::string>

But there it is how you can use another hash function:

struct StringHasher {
    size_t operator()(const std::string& t) const {
          //calculate hash here.
    }
}

unordered_map<std::string, ValueType, StringHasher>

Solution 4

If you have a CustomType and you want to plug into the STL infrastructure this is what you could do.

namespace std
{
//namespace tr1
//{
    // Specializations for unordered containers

    template <>
    struct hash<CustomType> : public unary_function<CustomType, size_t>
    {
        size_t operator()(const CustomType& value) const
        {
            return 0;
        }
    };

//} // namespace tr1

template <>
struct equal_to<CustomType> : public unary_function<CustomType, bool>
{
    bool operator()(const CustomType& x, const CustomType& y) const
    {
        return false;
    }
};

} // namespace std

If you then want to create say a std::unordered_map<CustomType> the STL will find the hash and equal_to functions without you having to do anything more with the template. This is how I like to write my custom equality comparer that support unordered data structures.

View more solutions

Comments

[Michael Burr]

I'm curious what gave you the idea that the standard library (at least a library that supported unordered_map) didn't support a hash function for std::string?

[MirroredFate]

"error C2338: The C++ Standard doesn't provide a hash for this type." when I try to use string.

[Michael Burr]

Perhaps this SO answer might be related to what's happening to you: stackoverflow.com/a/11157019/12711 Are you using basic_string<> directly instead of through the std:string typedef? You might be able to use basic_string<> for some purposes without a compiler error because another header happens to be pulling in xstring (which gives you basic_string<>, but not std::hash<string>)

[Michael Burr]

So the bottom line is - make sure you have a #include <string> if you're trying to use strings in an unordered_map<> - actually, any time you're using std::string. Unfortunately, the compiler will sometimes let you get away without the include because of side effects from other includes. then when you add a use that actually requires the string header you get a mysterious, non-obvious error from the compiler.

[Valar Morghulis]

What happens to me sometimes is the IDE incorrectly change my #include <unordered_map> to #include <bits/unordered_map.h>. So make sure you have included the correct lib.

[John Leidegren]

This is the implicit behavior from the type constructor, is it not? Specifying std::hash<std::string>> when you already have an std::unordered_map<std::string> is just redundant.

[Nevin]

Note: unary_function is deprecated. Better to provide the typedefs result_type and argument_type yourself.

[Bloodmoon]

I think this should be compiled with option "-std=c++0x"?

[awesoon]

@Bloodmoon, Yes (I'd say, with -std=c++11), unordered_map is a C++11 feature.

[Admin]

This answer most directly addressed my issue (not including <string>)