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

Question

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

Answer 1

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

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

Answer 2

Использовать хеш-карты в 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;
}

Answer 3

Взгляните на boost.unordered и его структуру данных .

Answer 4

Попробуйте буст неупорядоченных классов.

Answer 5

Извлечение Простая хэш-карта (хэш-таблица) Реализация на C ++ для базовой хеш-таблицы с парами ключ-значение универсального типа и отдельной стратегией связывания.