Простая реализация hashmap в С++

Я относительно не знаком с С++. В Java мне легко создать экземпляр и использовать хэш-карту. Я хотел бы знать, как сделать это простым способом на С++, так как я видел много разных реализаций, и ни один из них не выглядел простым для меня.

Ответы

Ответ 1

Большинство компиляторов должны определить std::hash_map для вас; в следующем стандарте C++0x он будет частью стандартной библиотеки как std::unordered_map. Страница 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;

После этого все должно работать как ожидается.

Ответ 2

Использование hashmaps в С++ легко! Это похоже на стандартную карту С++. Вы можете использовать реализацию вашего компилятора/библиотеки 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;
}

Ответ 4

Попробуйте повысить unordered классы.