C++ – Hash Object problem in C++

cfunctionhashhashmap

In some C++ program I have two classes – Abc and Xyz. The Abc class contains an integer member Foo, like in the following listing:

class Abc
{
 public:
 int Foo;
 Abc(int f)
 {
  Foo = f;
 }
};
class Xyz{};

I'm using a map<Abc, Xyz> but the performance is extremly poor. That's why I'd like to use a hash_map<Abc, Xyz> (Dev-Cpp extension libraries) and some tricky hashing. Let's assume the following AbcHash unary function object is going to act well as a hash generator:

class AbcHash
{
 public:
 size_t operator() (const Abc &a)
 {
  return a.Foo % 123;
 } 
};

For consistency with STL I've also implemented an AbcCmp comparator:

class AbcCmp
{
 public:
 bool operator() (const Abc &a1, const Abc &a2)
 {
  return (a1.Foo == a2.Foo);
 }
};

I had tested both Abc and Xyz classes, when I wanted to use the hash_map at last. That's my main:

int main(int argc, char *argv[])
{
 hash_map myMap;

 Abc a(10);
 a.Foo = 23;

 Xyz x();

 myMap[a] = x; // this line fails the compilation
}

The last line causes some strange compilation errors:

Compiler: Default compiler
Building Makefile: "C:\user\hdr\hashfunc\Makefile.win"
Executing  make...
make.exe -f "C:\user\hdr\hashfunc\Makefile.win" all
g++.exe -c main.cpp -o main.o -I"C:/Dev-Cpp/lib/gcc/mingw32/3.4.2/include"  -I"C:/Dev-Cpp/include/c++/3.4.2/backward"  -I"C:/Dev-Cpp/include/c++/3.4.2/mingw32"  -I"C:/Dev-Cpp/include/c++/3.4.2"  -I"C:/Dev-Cpp/include"   

In file included from C:/Dev-Cpp/include/c++/3.4.2/backward/hash_map.h:59,
                 from main.cpp:2:
C:/Dev-Cpp/include/c++/3.4.2/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the  header for the  header for C++ includes, or  instead of the deprecated header . To disable this warning use -Wno-deprecated.
main.cpp: In function `int main(int, char**)':
main.cpp:45: error: no match for 'operator=' in '(&myMap)->__gnu_cxx::hash_map::operator[] [with _Key = Abc, _Tp = Xyz, _HashFcn = AbcHash, _EqualKey = AbcCmp, _Alloc = std::allocator](((const Abc&)((const Abc*)(&a)))) = x'
main.cpp:14: note: candidates are: Xyz& Xyz::operator=(const Xyz&)

C:/Dev-Cpp/include/c++/3.4.2/ext/hashtable.h: In member function `size_t __gnu_cxx::hashtable::_M_bkt_num_key(const _Key&, size_t) const [with _Val = std::pair, _Key = Abc, _HashFcn = AbcHash, _ExtractKey = std::_Select1st >, _EqualKey = AbcCmp, _Alloc = std::allocator]':
C:/Dev-Cpp/include/c++/3.4.2/ext/hashtable.h:523:   instantiated from `size_t __gnu_cxx::hashtable::_M_bkt_num(const _Val&, size_t) const [with _Val = std::pair, _Key = Abc, _HashFcn = AbcHash, _ExtractKey = std::_Select1st >, _EqualKey = AbcCmp, _Alloc = std::allocator]'
C:/Dev-Cpp/include/c++/3.4.2/ext/hashtable.h:887:   instantiated from `void __gnu_cxx::hashtable::resize(size_t) [with _Val = std::pair, _Key = Abc, _HashFcn = AbcHash, _ExtractKey = std::_Select1st >, _EqualKey = AbcCmp, _Alloc = std::allocator]'
C:/Dev-Cpp/include/c++/3.4.2/ext/hashtable.h:701:   instantiated from `typename __gnu_cxx::hashtable::reference __gnu_cxx::hashtable::find_or_insert(const _Val&) [with _Val = std::pair, _Key = Abc, _HashFcn = AbcHash, _ExtractKey = std::_Select1st >, _EqualKey = AbcCmp, _Alloc = std::allocator]'
C:/Dev-Cpp/include/c++/3.4.2/ext/hash_map:181:   instantiated from `_Tp& __gnu_cxx::hash_map::operator[](const typename __gnu_cxx::hashtable, _Key, _HashFcn, std::_Select1st >, _EqualKey, _Alloc>::key_type&) [with _Key = Abc, _Tp = Xyz, _HashFcn = AbcHash, _EqualKey = AbcCmp, _Alloc = std::allocator]'
main.cpp:45:   instantiated from here
C:/Dev-Cpp/include/c++/3.4.2/ext/hashtable.h:518: error: passing `const AbcHash' as `this' argument of `size_t AbcHash::operator()(const Abc&)' discards qualifiers

make.exe: *** [main.o] Error 1

Execution terminated

I have completely no idea what can be wrong here. How can it be fixed?

Best Answer

My first approach would be to identify why map's performance is poor. Maps are actually pretty good all round performers - they may wel outperform hash tables in some circumstances. Changing containers without knowing the problem is not a good idea.

Then I would junk DevC++. This antique is extremely buggy and is no longer under active development - I'd be especially dubious about using any libraries that came with it. I'd switch to a nightly build of Code::Blocks, the Twilight Dragon build of GCC, and (if I still wanted a hash) to either the TR1 or the Boost hashtable implementations.

Related Topic