c++ - unordered_map<const T, int> 和 map<const T, int> 的区别

Question

#include <string>
#include <map>
#include <unordered_map>
using namespace std;

class Solution {
public:

private:    
    // unordered_map<string, int> mapStrInt;       // Case 1: OK
    // unordered_map<const string, int> mapStrInt; // Case 2: Fail
    // map<string, int> mapStrInt;                 // Case 3: OK
    // map<const string, int> mapStrInt;           // Case 4: OK
};

问题> 为什么 Case 2 不合法？

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;
            template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

基于 http://www.compileonline.com/compile_cpp11_online.php

Compiling the source code....
$g++ -std=c++11 main.cpp -o demo -lm -pthread -lgmpxx -lgmp -lreadline 2>&1

In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable.h:35:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/unordered_map:47,
                 from main.cpp:3:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::_Hash_code_base<const std::basic_string<char>, std::pair<const std::basic_string<char>, int>, std::__detail::_Select1st, std::hash<const std::basic_string<char> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>':
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable_policy.h:1402:10:   required from 'struct std::__detail::_Hashtable_base<const std::basic_string<char>, std::pair<const std::basic_string<char>, int>, std::__detail::_Select1st, std::equal_to<const std::basic_string<char> >, std::hash<const std::basic_string<char> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >'
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable.h:174:11:   required from 'class std::_Hashtable<const std::basic_string<char>, std::pair<const std::basic_string<char>, int>, std::allocator<std::pair<const std::basic_string<char>, int> >, std::__detail::_Select1st, std::equal_to<const std::basic_string<char> >, std::hash<const std::basic_string<char> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >'
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/unordered_map.h:100:18:   required from 'class std::unordered_map<const std::basic_string<char>, int>'
main.cpp:11:38:   required from here
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable_policy.h:1070:12: error: invalid use of incomplete type 'struct std::hash<const std::basic_string<char> >'
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
            ^
In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/basic_string.h:3033:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/string:52,
                 from main.cpp:1:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<const std::basic_string<char> >'
     struct hash;
            ^
In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable.h:35:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/unordered_map:47,
                 from main.cpp:3:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable_policy.h:1070:12: error: invalid use of incomplete type 'struct std::hash<const std::basic_string<char> >'
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
            ^
In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/basic_string.h:3033:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/string:52,
                 from main.cpp:1:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<const std::basic_string<char> >'
     struct hash;
            ^
In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable.h:35:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/unordered_map:47,
                 from main.cpp:3:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable_policy.h:1082:53: error: invalid use of incomplete type 'struct std::hash<const std::basic_string<char> >'
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
                                                     ^
In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/basic_string.h:3033:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/string:52,
                 from main.cpp:1:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<const std::basic_string<char> >'
     struct hash;
            ^
In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable.h:35:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/unordered_map:47,
                 from main.cpp:3:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/hashtable_policy.h:1082:53: error: invalid use of incomplete type 'struct std::hash<const std::basic_string<char> >'
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
                                                     ^
In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/bits/basic_string.h:3033:0,
                 from /usr/local/gcc-4.8.1/include/c++/4.8.1/string:52,
                 from main.cpp:1:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/functional_hash.h:58:12: error: declaration of 'struct std::hash<const std::basic_string<char> >'
     struct hash;
            ^

== 根据评论更新了工作代码 ==

struct HashConstString
{
    long operator()(const string& str) const {
        return hash<string>()(str);
    }
};

class Solution {
public:

private:    
    unordered_map<const string, int, HashConstString> mapStrInt; // Case 2: Now it works
};

Answer 1

从21.6我们了解到该语言提供了四种与字符串相关的哈希函数:

template <> struct hash<string>;
template <> struct hash<u16string>;
template <> struct hash<u32string>;
template <> struct hash<wstring>;

然后从 23.5.2 我们了解到 unordered_map 的默认哈希值是hash<Key>或者在这种情况下 hash<const std::string> .之前我们了解到，实现不需要提供这样的哈希，因此不能保证您的代码可以编译。

template <class Key,
class T,
class Hash = hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T> > >
class unordered_map; 

您可以使用 std::string作为您的 key 或将哈希函数指定为 hash<std::string>而不是依赖默认的模板参数。