C++: hashtable - Why won't this compile?

Question

I have the following C++ code:

#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;
}

As you can see, I'm implementing a hash table using Google's sparsehash library.

I am using integers as the key and strings as the value.

But I keep getting the following compilation error that I can't get to the bottom of:

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

It seems very verbose and I can't make any sense of it.

I should add that when I use strings as the key and integers as the value, it works fine:

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

Anyone got any ideas?

Many thanks in advance,

Edit: got it working now!

#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;
}

Totally forgot about editing the eqstr struct to accomodate the new data types... bangs head off desk

The complaint is that eqstr should expect the key type, and the key type is not const char*. I don't know enough about the type to say what the key type is (unsigned int?) based on your declaration. — antlersoft

Alexander Gessler Alexander Gessler · Accepted Answer · 2011-07-29T13:51:21

As you pointed out by yourself, it works if you use const char* as key. The hashmap indeed requires a hashing function to hash the keys to buckets and a comparison function to establish a strict weak ordering within the buckets - all this for the key type, the value type is just stored! So to make it work, define a comparison function for int (I don't know whether const int is fine with google::dense_hash_map, I think it should be int).

C++: hashtable - Why won't this compile?

1 Answers