Каков наилучший способ использовать HashMap в C++?

Я знаю, что у STL есть HashMap API, но я не могу найти хорошую и исчерпывающую документацию с хорошими примерами по этому поводу.

Любые хорошие примеры будут оценены.

Источник

4 ответа

Решение

Стандартная библиотека включает в себя упорядоченную и неупорядоченную карту (std::map а также std::unordered_map) контейнеры. В упорядоченной карте элементы сортируются по ключу, вставка и доступ осуществляется в O(log n). Обычно стандартная библиотека внутренне использует красные черные деревья для упорядоченных карт. Но это только деталь реализации. В неупорядоченную карту вставьте и получите доступ в O(1). Это просто другое название хеш-таблицы.

Пример с (заказал) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Выход:

23
Ключ: привет Значение: 23

Если вам нужен порядок в вашем контейнере и вы согласны со временем выполнения O(log n), просто используйте std::map,

В противном случае, если вам действительно нужна хеш-таблица (O(1) вставка / доступ), проверьте std::unordered_map, который имеет аналог std::map API (например, в приведенном выше примере вам просто нужно найти и заменить map с unordered_map).

unordered_map Контейнер был представлен со стандартной версией C++ 11. Таким образом, в зависимости от вашего компилятора, вы должны включить функции C++ 11 (например, при использовании GCC 4.8 вы должны добавить -std=c++11 к CXXFLAGS).

Еще до выхода C++ 11 GCC поддерживал unordered_map - в пространстве имен std::tr1, Таким образом, для старых компиляторов GCC вы можете попробовать использовать его следующим образом:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

Это также является частью boost, т.е. вы можете использовать соответствующий boost-header для лучшей переносимости.

Источник

hash_map является более старой нестандартной версией того, что для целей стандартизации называется unordered_map (в настоящее время доступен как часть TR1 и будет включен в C++0x). Как следует из названия, это отличается от std::map в первую очередь в неупорядоченности - если, например, вы перебираете карту из begin() в end()вы получаете элементы в порядке по ключу1, но если вы перебираете unordered_map от begin() в end()Вы получаете предметы в более или менее произвольном порядке.

unordered_map как правило, ожидается, что будет иметь постоянную сложность. То есть вставка, поиск и т. Д., По существу, занимают фиксированное количество времени, независимо от того, сколько элементов в таблице. std::map имеет сложность, которая является логарифмической по количеству сохраняемых элементов - что означает, что время для вставки или извлечения элемента увеличивается, но очень медленно, по мере увеличения карты. Например, если поиск одного из 1 миллиона элементов занимает 1 микросекунду, то можно ожидать, что для поиска одного из 2 миллионов элементов потребуется около 2 микросекунд, 3 микросекунды для одного из 4 миллионов элементов, 4 микросекунды для одного из 8 миллионов. предметы и т. д.

С практической точки зрения, это еще не все. По своей природе простая хеш-таблица имеет фиксированный размер. Адаптировать его к требованиям переменного размера для контейнера общего назначения несколько нетривиально. В результате операции (потенциально) увеличивающие или уменьшающие таблицу (например, вставка и удаление) часто являются относительно медленными. Поиск, который не может изменить размер таблицы, как правило, намного быстрее. В результате большинство таблиц на основе хеш-функции имеют тенденцию работать лучше, когда вы выполняете много поисков и сравнительно мало вставок и удалений. В ситуациях, когда вы вставляете много данных, затем просматриваете таблицу один раз, чтобы получить результаты (например, подсчитав количество уникальных слов в файле), есть вероятность, что std::map будет так же быстро, и, возможно, даже быстрее.

1 Где порядок определяется третьим параметром шаблона при создании карты, std::less<T> по умолчанию.

Источник

Вот более полный и гибкий пример, который не пропускает необходимые включения для генерации ошибок компиляции:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

Все еще не особенно полезно для ключей, если они не определены как указатели, потому что соответствующее значение не подойдет! (Однако, поскольку я обычно использую строки для ключей, замена "string" вместо "const void *" в объявлении ключа должна решить эту проблему.)

Источник

Как использовать пользовательский класс и хэш-функцию сunordered_map

Этот ответ гласит: C++ unordered_map с использованием пользовательского типа класса в качестве ключа

Выдержка: равенство:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Хэш-функция:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}
Источник

Для тех из нас, кто пытается понять, как хешировать наши собственные классы, все еще используя стандартный шаблон, есть простое решение:

  1. В вашем классе вам необходимо определить перегрузку оператора равенства ==. Если вы не знаете, как это сделать, у GeeksforGeeks есть отличный учебник https://www.geeksforgeeks.org/operator-overloading-c/

  2. В стандартном пространстве имен объявите структуру шаблона с именем hash с вашим именем класса в качестве типа (см. Ниже). Я нашел отличный пост в блоге, который также показывает пример вычисления хэшей с использованием XOR и битового сдвига, но это выходит за рамки этого вопроса, но он также включает подробные инструкции о том, как выполнить хеш-функции https://prateekvjoshi.com/2014/06/05 / использование-хеш-функции-в-c-для-определяемых пользователем-классов /

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}
  1. Итак, чтобы реализовать хеш-таблицу с использованием вашей новой хеш-функции, вам просто нужно создать std::map или std::unordered_map так же, как вы обычно делаете и используете my_type в качестве ключа стандартная библиотека будет автоматически использовать хэш-функцию, которую вы определили ранее (на шаге 2), для хеширования ваших ключей.
#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}
Источник
Другие вопросы по тегам