Hashtable в С++?

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

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

Ответы

Ответ 1

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

Ответ 7

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

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

Ответ 8

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