Хэш-таблица в C ++?
https://stackoverflow.com/questions/133569
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Обычно я использую C ++ stdlib map всякий раз, когда мне нужно сохранить некоторые данные, связанные с определенным типом значения (ключевое значение - напримерстрока или другой объект).Реализация карты stdlib основана на деревьях, что обеспечивает лучшую производительность (O(log n)), чем стандартный массив или вектор stdlib.
Мои вопросы в том, знаете ли вы какую-либо "стандартную" реализацию хэш-таблицы на C ++, которая обеспечивает еще лучшую производительность (O (1))?Что-то похожее на то, что доступно в классе Hashtable из Java API.
Решение
Если вы используете 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 типы тоже.
Другие советы
Если у вас еще нет unordered_map или unordered_set, они являются частью повышение.
Вот документация для обоих.
Существует hash_map - хэш-карта объект, как многие здесь упоминали, но он не является частью stl.Это расширение SGI, так что если вы искали что-то в STL, я думаю, вам не повезло.
std::tr1::unordered_map, в <unordered_map>
если у вас нет tr1, получите boost и используйте
boost::unordered_map в <boost/unordered_map.hpp>
В Visual Studio есть класс stdext::hash_map в заголовке <hash_map>, и gcc имеет класс __gnu_cxx::hash_map в том же заголовке.
Видишь стандартный код::hash_map из SGI.
Это включено в СТЛПорт распространение в том числе.
hash_map также поддерживается в GNU libstdc++.
Посуда также поддерживает это означает, что многие реализации будут иметь hash_map (я думаю, что даже Visual C ++ поставляется с Dinkumware).
Если у вас есть расширения TR1, доступные для вашего компилятора, используйте их.Если нет, boost.org имеет версию, которая очень похожа, за исключением std::пространство имен.В этом случае введите using-declaration, чтобы вы могли переключиться на std::позже.
