Проблема хеш-объекта в C ++ - PullRequest
Новая
       17

Проблема хеш-объекта в C ++

0 голосов
/ 19 декабря 2009

В некоторых программах на C ++ у меня есть два класса - Abc и Xyz . Класс Abc содержит целочисленный член Foo , как показано в следующем листинге: 

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

Я использую карту <<em> Abc , Xyz >, но производительность крайне низкая. Вот почему я хотел бы использовать hash_map <<em> Abc , Xyz > (библиотеки расширений Dev-Cpp) и некоторые хитрые хэши. Давайте предположим, что следующий AbcHash объект унарной функции будет хорошо работать как генератор хеша: 

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

Для совместимости с STL я также реализовал AbcCmp компаратор: 

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

Я протестировал классы Abc и Xyz , когда я наконец захотел использовать hash_map. Это моя главная : 

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
}

Последняя строка вызывает некоторые странные ошибки компиляции: 

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

Я понятия не имею, что здесь может быть не так. Как это можно исправить?

Ответы [ 2 ]

4 голосов
/ 19 декабря 2009

Мой первый подход - определить, почему производительность карты низкая. Карты на самом деле довольно хороши во всех отношениях - в некоторых случаях они могут превзойти хэш-таблицы. Менять контейнеры, не зная проблемы, не очень хорошая идея.

Тогда я бы выбросил DevC ++. Этот антиквариат чрезвычайно глючный и больше не находится в активной разработке - я бы особенно сомневался в том, чтобы использовать любые библиотеки, которые были в комплекте. Я бы переключился на ночную сборку Code :: Blocks , Twilight Dragon сборку GCC и (если я все еще хотел хеш) либо на TR1, либо на хеш-таблицу Boost реализации.

0 голосов
/ 19 декабря 2009

Чтобы объяснить первую ошибку, мне нужно посмотреть, как вы напечатали hash_map. (Ты сделал typedef, не так ли?).

Причина, по которой вы получаете вторую ошибку, заключается в том, что ваши объявления AbcHash и AbcCmp должны объявлять свои функции operator () как const: 

size_t operator() (const Abc &a) const

bool operator() (const Abc &a1, const Abc &a2) const

Однако я должен согласиться с Нилом, что использование активно разработанной библиотеки было бы намного мудрее.

...