Hashtable в C++?

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

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

источник

2008-09-25 Marcos Bento

Если вы используете C++ 11, у вас есть доступ к заголовкам и <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.

источник

2008-09-25 14:15:41

В GCC вы должны использовать имена заголовков и . Это причуда GCC. :-) –

VS2008 Feature Pack заменен пакетом обновления 1 (SP1). – Ferruccio

IIRC VC9 Feature Pack и SP1 tr1 :: unordered_ * реализованы версии с выпуском предупреждений о недостаточной производительности.Я бы предположил, что это будет исправлено в конечном итоге. – jwfearn

-1

std::hash_map

источник

2008-09-25 14:14:20 Dima

См std::hash_map от SGI.

Это также входит в комплект поставки STLPort.

источник

2008-09-25 14:14:29

Он может быть включен в STLPort, но это по-прежнему не «стандарт», как вопрос, который требуется. Нет класса _standard_, называемого hash_map; вместо этого он называется unordered_map, и он находится в TR1. –

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

источник

2008-09-25 14:15:52

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

источник

2008-09-25 14:17:51

Если у них такой же интерфейс, довольно просто сделать реализацию, которая поддерживает оба из них, используя псевдонимы пространства имен и некоторую работу перед процессором. –

Я знаю, я знаю, это устаревшие вещи. Не каждый коллега может быть убежден переключиться на VS 2008 или установить Boost. Так вот хороший трюк о том, как получить их вместе: 'патезрасе { #ifdef __GNUC__ \t с использованием пространства имен __gnu_cxx; #elif \t using namespace stdext; #endif } ' – ypnos

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

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

источник

2008-09-25 14:20:31

Он может быть широко поддержан, но он не является« стандартным », как задавал вопрошающий. Только объекты TR1 можно считать стандартными. –

То, что я делал, это то, что если все поставщики компилятора поддерживают его (или, возможно, поставщики stdlibC++, в зависимости от ситуации), то это может быть достаточно хорошей заменой «стандартным». BTW, TR1 пока не является «стандартным». Это принято для следующего стандарта, которого достаточно, чтобы заставить продавцов реализовать его (моя точка ...) –

Я думаю, что это просто для libstdC++ version> = 4.0? – rogerdpack

Если у вас еще нет unordered_map или unordered_set, они являются частью boost.
Here's the documentation for both.

источник

2008-09-25 14:28:21

Yay for Boost, обеспечивающий _maximal portability_ еще раз. :-) См. Http://stackoverflow.com/questions/131445 для другого экземпляра этого. –

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

источник

2008-09-25 14:28:32 MSalters

станд :: tr1 :: unordered_map, в <unordered_map>

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

источник

2009-03-25 14:58:45 rlbond

Hashtable в C++?

ответ

Смежные вопросы