Простая реализация hashmap в C ++
Вопрос
Я относительно новичок в C ++. В Java мне легко создать экземпляр и использовать hashmap. Я хотел бы знать, как сделать это простым способом в C ++, поскольку я видел много разных реализаций, и ни одна из них не выглядела простой для меня.
Решение
Большинство компиляторов должны определять для вас std :: hash_map
; в следующем стандарте C ++ 0x
он будет частью стандартной библиотеки как <код> станд :: unordered_map код> . STL-страница на нем довольно стандартная. Если вы используете Visual Studio, Microsoft имеет страницу на нем.
Если вы хотите использовать свой класс в качестве значения, а не в качестве ключа, вам не нужно делать ничего особенного. Все примитивные типы (такие как int
, char
, bool
и даже char *
) должны просто работать " в качестве ключей в hash_map
. Однако для всего остального вам придется определить свои собственные функции хеширования и равенства, а затем написать " функторы " что обернуть их в классе.
Предполагается, что ваш класс называется MyClass
, и вы уже определили:
size_t MyClass::HashValue() const { /* something */ }
bool MyClass::Equals(const MyClass& other) const { /* something */ }
Вам нужно определить два функтора, чтобы обернуть эти методы в объекты.
struct MyClassHash {
size_t operator()(const MyClass& p) const {
return p.HashValue();
}
};
struct MyClassEqual {
bool operator()(const MyClass& c1, const MyClass& c2) const {
return c1.Equals(c2);
}
};
И создайте экземпляр своего hash_map
/ hash_set
как:
hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map;
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set;
После этого все должно работать как положено.
Другие советы
Использовать хеш-карты в C ++ просто! Это похоже на использование стандартной карты C ++. Вы можете использовать реализацию unordered_map
вашего компилятора / библиотеки или использовать boost или другой поставщик. Вот быстрый пример. Вы найдете больше, если вы перейдете по ссылкам, которые вы дали.
#include <unordered_map>
#include <string>
#include <iostream>
int main()
{
typedef std::tr1::unordered_map< std::string, int > hashmap;
hashmap numbers;
numbers["one"] = 1;
numbers["two"] = 2;
numbers["three"] = 3;
std::tr1::hash< std::string > hashfunc = numbers.hash_function();
for( hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i ) {
std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc( i->first ) << ")" << std::endl;
}
return 0;
}
Взгляните на boost.unordered . и его структура данных . р>
Попробуйте увеличить неупорядоченные классы. р>
Ознакомьтесь с реализацией простой хэш-карты (хэш-таблицы) в C ++ для базовой хэш-таблицы с ключом универсального типа - пары значений и отдельная стратегия сцепления.