C++:哈希表——为什么不能编译？

Question

我有以下 C++ 代码:

#include <iostream>
#include <google/dense_hash_map>
#include <string.h>

using google::dense_hash_map;      // namespace where class lives by default
using std::cout;
using std::endl;
using std::tr1::hash;  // or __gnu_cxx::hash, or maybe tr1::hash, depending on your OS

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
  }
};

int main(void){
  dense_hash_map<const int, const char*, hash<const int>, eqstr> months;

  months.set_empty_key(0);
  months[1234] = "1234";

  cout << "1234:" << months[1234] << endl;
}

如您所见，我正在使用 Google 的 sparsehash 库实现哈希表。

我使用整数作为键，使用字符串作为值。

但我不断收到以下无法深入了解的编译错误:

make all Building file: ../src/Main.cpp Invoking: GCC C++ Compiler g++ -O0 -g3 -Wall -c -fmessage-length=0 -MMD -MP -MF"src/Main.d" -MT"src/Main.d" -o"src/Main.o" "../src/Main.cpp" In file included from /usr/local/include/google/dense_hash_map:104:0, from ../src/Main.cpp:2: /usr/local/include/google/sparsehash/densehashtable.h: In member function ‘bool google::dense_hashtable::KeyInfo::equals(const key_type&, const key_type&) const [with Value = std::pair, Key = int, HashFcn = std::tr1::hash, ExtractKey = google::dense_hash_map, eqstr>::SelectKey, SetKey = google::dense_hash_map, eqstr>::SetKey, EqualKey = eqstr, Alloc = google::libc_allocator_with_realloc

, key_type = int]’: /usr/local/include/google/sparsehash/densehashtable.h:1306:32:
instantiated from ‘bool google::dense_hashtable::equals(const key_type&, const key_type&) const [with Value = std::pair, Key = int, HashFcn = std::tr1::hash, ExtractKey = google::dense_hash_map, eqstr>::SelectKey, SetKey = google::dense_hash_map, eqstr>::SetKey, EqualKey = eqstr, Alloc = google::libc_allocator_with_realloc , key_type = int]’ /usr/local/include/google/sparsehash/densehashtable.h:514:5:
instantiated from ‘void google::dense_hashtable::set_empty_key(google::dense_hashtable::const_reference) [with Value = std::pair, Key = int, HashFcn = std::tr1::hash, ExtractKey = google::dense_hash_map, eqstr>::SelectKey, SetKey = google::dense_hash_map, eqstr>::SetKey, EqualKey = eqstr, Alloc = google::libc_allocator_with_realloc , google::dense_hashtable::const_reference = const std::pair&]’ /usr/local/include/google/dense_hash_map:298:5:
instantiated from ‘void google::dense_hash_map::set_empty_key(google::dense_hash_map::key_type&) [with Key = int, T = const char*, HashFcn = std::tr1::hash, EqualKey = eqstr, Alloc = google::libc_allocator_with_realloc , google::dense_hash_map::key_type = int]’ ../src/Main.cpp:21:25: instantiated from here /usr/local/include/google/sparsehash/densehashtable.h:1293:39: error: invalid conversion from ‘google::dense_hashtable, int, std::tr1::hash, google::dense_hash_map, eqstr, google::libc_allocator_with_realloc

::SelectKey, eqstr, google::libc_allocator_with_realloc , google::dense_hash_map, eqstr, google::libc_allocator_with_realloc > >::SetKey, eqstr, google::libc_allocator_with_realloc , eqstr, google::libc_allocator_with_realloc > >::key_type’ to ‘const char*’ /usr/local/include/google/sparsehash/densehashtable.h:1293:39: error: initializing argument 1 of ‘bool eqstr::operator()(const char*, const char*) const’ /usr/local/include/google/sparsehash/densehashtable.h:1293:39: error: invalid conversion from ‘google::dense_hashtable, int, std::tr1::hash, google::dense_hash_map, eqstr, google::libc_allocator_with_realloc ::SelectKey, eqstr, google::libc_allocator_with_realloc , google::dense_hash_map, eqstr, google::libc_allocator_with_realloc > >::SetKey, eqstr, google::libc_allocator_with_realloc , eqstr, google::libc_allocator_with_realloc > >::key_type’ to ‘const char*’ /usr/local/include/google/sparsehash/densehashtable.h:1293:39: error: initializing argument 2 of ‘bool eqstr::operator()(const char*, const char*) const’ make: * [src/Main.o] Error 1

看起来很冗长，我无法理解它。

我应该补充一点，当我使用字符串作为键并使用整数作为值时，它工作正常:

dense_hash_map<const char*, int, hash<const char*>, eqstr> months;
...
months["february"] = 2;   //works fine

有人有什么想法吗？

非常感谢，

---

编辑:现在开始工作了!

#include <iostream>
#include <google/dense_hash_map>
#include <string.h>

using google::dense_hash_map;      // namespace where class lives by default
using std::cout;
using std::endl;
using std::tr1::hash;  // or __gnu_cxx::hash, or maybe tr1::hash, depending on your OS

struct eqstr
{
  bool operator()(int s1, int s2) const
  {
    return (s1 == s2); //|| (s1 && s2 && strcmp(s1, s2) == 0);
  }
};

int main(void){
  dense_hash_map<int, const char*, hash<int>, eqstr> months;

  months.set_empty_key(0);
  months[1234] = "1234";

  cout << "1234:" << months[1234] << endl;
}

完全忘记了编辑 eqstr 结构以适应新的数据类型......bangs head off desk

Answer 1

正如您自己指出的，如果您使用 const char* 作为键，它就可以工作。 hashmap 确实需要一个散列函数来将键散列到桶和一个比较函数来在桶内建立严格的弱排序——所有这些对于键类型，值类型只是存储!所以要让它工作，为int定义一个比较函数(我不知道const int是否适合google::dense_hash_map，我认为应该是int)。