C ++ структура данных с lookuptime O (1), как хешмап Java в stl

Question

Есть ли такая структура в стандартной библиотеке c ++? У меня нет доступа ни к чему другому, поэтому unordered_map в tr1 нельзя использовать (и повысить и т. Д.).

То, что у меня есть, - это большое количество пользовательских элементов класса 100000+, которые мне нужно хранить, и очень быстро получить к ним доступ O (1). Я не могу использовать массивы / векторы, так как элементы будут храниться случайным образом, и я не знаю положение элемента.

Является ли моя единственная альтернатива реализации собственной реализации hashmap с доступной только стандартной библиотекой c ++?

Answer 1

Если вы действительно ограничены std:: и не можете использовать что-либо еще, std::map - ваш лучший выбор. Это дает вам только логарифмическое время поиска, а не постоянное, но по сравнению с массивами / векторами оно будет невероятно быстрым. Также я предполагаю, что только для 100000 элементов логарифмический поиск будет достаточно быстрым, и вы не выиграете много, используя хеш-таблицу.

При этом, скорее всего, ваша реализация уже включает некоторую реализацию хеш-таблицы. Так что если std::map действительно недостаточно быстро, попробуйте

#include <tr1/unordered_map>
std::tr1::unordered_map<int,int> test;

или

#include <hash_map>
stdext::hash_map<int,int> test;

или даже

#include <boost/tr1/unordered_map.hpp>
std::tr1::unordered_map<int,int> test;

Answer 2

Проблема в том, что поиск O (1) не является стандартным. Я не уверен в том, что имеет boost, но некоторые реализации STL (например, sgi) имеют hash_map. Это то, что вам нужно.

Вот документация .

Просто попробуйте:

#include <hash_map>

Имейте в виду, если это работает, оно не переносимо ... но, может быть, пока это нормально, и позже вы можете найти обходные пути.

Answer 3

Почему вы не можете использовать Boost? Библиотека Unordered collection - это «Только заголовок», что означает, что вам не нужно загружать процесс сборки и установки BJam в Boost. Вы можете просто взять файлы .hpp и добавить их в свой проект.

Answer 4

hash_map является частью расширения SGI до STL. В GCC вы можете использовать его, выполнив следующие действия; Я не знаю о других реализациях:

#include <ext/hash_map>

using __gnu_cxx::hash_map;

hash_map<int,string> foo; // or whatever

unordered_map является частью TR1. В GCC вы можете использовать его, выполнив следующие действия; Я не знаю о других реализациях:

#include <tr1/unordered_map>

using std::tr1::unordered_map;

unordered_map<int,string> foo; // or whatever

Answer 5

Стандартный STL в текущем стандарте не имеет O (1) поисковых контейнеров.

Answer 6

Вы можете использовать контейнер unordered_map. Это в tr1 и будет в следующем полном стандарте. Visual Studio имеет его реализацию в , а документацию можно найти здесь: http://msdn.microsoft.com/en-us/library/bb982522.aspx

Answer 7

Как и hash_map в некоторых STL, ищите unordered_map (это то, что он будет называться и / или вызываться в версии C ++ TR1).