Hashtable в C ++?

Question

Я обычно использую карту C ++ stdlib всякий раз, когда мне нужно сохранить некоторые данные, связанные с определенным типом значения (значение ключа - например, строка или другой объект) Реализация карты stdlib основана на деревьях, которые обеспечивают лучшую производительность (O (log n)), чем стандартный массив или вектор stdlib.

Мои вопросы: знаете ли вы какую-либо "стандартную" реализацию хеширования C ++, которая обеспечивает еще лучшую производительность (O (1))? Нечто похожее на то, что доступно в классе Hashtable из API Java.

Answer 1

Если вы используете C ++ 11, у вас есть доступ к заголовкам <unordered_map> и <unordered_set>. Они обеспечивают классы std::unordered_map и std::unordered_set.

Если вы используете C ++ 03 с TR1, у вас есть доступ к классам std::tr1::unordered_map и std::tr1::unordered_set с использованием одинаковых заголовков (если только вы не используете GCC, в этом случае заголовки <tr1/unordered_map> и <tr1/unordered_set> вместо).

Во всех случаях имеются также соответствующие типы unordered_multimap и unordered_multiset.

Answer 2

Если у вас еще нет unordered_map или unordered_set, они являются частью boost .
Вот документация для обоих .

Answer 3

Существует объект hash_map , о котором многие здесь упоминали, но он не является частью stl. Это расширение SGI, поэтому, если вы что-то искали в STL, я думаю, вам не повезло.

Answer 4

std :: tr1 :: unordered_map, в <unordered_map>

если у вас нет tr1, получите повышение и используйте boost :: unordered_map в <boost/unordered_map.hpp>

Answer 5

Visual Studio имеет класс stdext::hash_map в заголовке <hash_map>, а gcc имеет класс __gnu_cxx::hash_map в том же заголовке.

Answer 6

Если у вас есть расширения TR1, доступные для вашего компилятора, используйте их. Если нет, то boost.org имеет аналогичную версию, за исключением пространства имен std ::. В этом случае вставьте объявление использования, чтобы вы могли переключиться на std :: позже.

Answer 7

hash_map также поддерживается в GNU's libstdc ++ .

Dinkumware также поддерживает это, что означает, что многие реализации будут иметь hash_map (я думаю, что даже Visual C ++ поставляет с Dinkumware).

Answer 8

См. std :: hash_map из SGI.

Это также входит в дистрибутив STLPort .

Answer 9

станд :: hash_map