Hashtable в C++?
Я обычно использую карту stdlib C++ всякий раз, когда мне нужно сохранить некоторые данные, связанные с определенным типом значения (значение ключа - например, строка или другой объект). Реализация карты stdlib основана на деревьях, которые обеспечивают лучшую производительность (O (log n)), чем стандартный массив или вектор stdlib.
Мои вопросы: знаете ли вы о какой-либо «стандартной» реализации хеш-таблицы C++, которая обеспечивает еще лучшую производительность (O (1))? Нечто похожее на то, что доступно в классе Hashtable из Java API.
Ответы 9
Если вы используете 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.
В GCC вместо этого вы должны использовать имена заголовков <tr1 / unordered_map> и <tr1 / unordered_set>. Это причуда GCC. :-)
Пакет функций VS2008 был заменен пакетом обновления 1 (SP1).
IIRC, реализации VC9 Feature Pack и SP1 tr1 :: unordered_map * поставлялись с примечаниями к выпуску, предупреждающими о неоптимальной производительности. Я предполагаю, что со временем это будет исправлено.
Спасибо, Ферруччо! Я включил ваше исправление. (Прошу прощения за неправильное написание вашего имени в комментарии к редактированию, но я не верю, что теперь у меня есть способ исправить это.)
Существует объект hash_map, о котором многие здесь упоминали, но он не является частью stl. Это расширение SGI, поэтому, если вы что-то искали в STL, я думаю, вам не повезло.
Visual Studio имеет класс stdext::hash_map в заголовке <hash_map>, а gcc имеет класс __gnu_cxx::hash_map в том же заголовке.
Если у них одинаковый интерфейс, довольно легко создать реализацию, поддерживающую их обоих, используя псевдонимы пространства имен и некоторую работу препроцессора.
Я знаю, я знаю, что это устаревший материал. Не каждого коллегу можно убедить перейти на VS 2008 или установить Boost. Вот хороший трюк, как собрать их вместе: `namespace std {#ifdef GNUC using namespace __gnu_cxx; #elif using namespace stdext; #endif} `
hash_map также поддерживается в GNU libstdC++.
Dinkumware также поддерживает this, что означает, что многие реализации будут иметь hash_map (я думаю, что даже Visual C++ поставляется с Dinkumware).
Возможно, он широко поддерживается, но он не является «стандартным», как просил спрашивающий. Стандартными можно считать только объекты TR1.
Я хотел сказать, что если все поставщики компиляторов поддерживают его (или поставщики stdlibC++, в зависимости от обстоятельств), то он может быть достаточно хорошей заменой «стандарту». Кстати, TR1 еще не "стандартный". Это принято для следующего стандарта, которого достаточно, чтобы продавцы реализовали его (моя точка зрения ...)
Думаю, это только для libstdC++ версии> = 4.0?
Если у вас еще нет unordered_map или unordered_set, они являются частью способствовать росту.
Вот документация для обоих.
Ура для Boost, снова предоставляющего максимальная переносимость. :-) См. Другой пример этого в stackoverflow.com/questions/131445.
Если у вас есть расширения TR1, доступные для вашего компилятора, используйте их. Если нет, то у boost.org есть версия, которая очень похожа, за исключением пространства имен std ::. В этом случае добавьте объявление using, чтобы вы могли позже переключиться на std ::.
std :: tr1 :: unordered_map в <unordered_map>
если у вас нет tr1, получите ускорение и используйте
boost :: unordered_map в <boost/unordered_map.hpp>
Он может быть включен в STLPort, но все же не является «стандартным», как хотелось бы спросить. Не существует класса стандарт с именем hash_map; вместо этого он называется unordered_map и находится в TR1.