У меня есть требование сделать поиск на основе большого количества. Число может падать в диапазоне 1 - 2^32. На основании ввода мне нужно вернуть другую структуру данных. Мой вопрос заключается в том, какую структуру данных я должен использовать, чтобы эффективно ее удерживать?Структура данных для поиска большого числа
Я бы использовал массив, дающий мне O (1) поиск, если бы цифры находились в диапазоне, скажем, от 1 до 5000. Но когда мой номер ввода становится большим, становится нереально использовать массив, поскольку требования к памяти будут быть огромным.
Поэтому я стараюсь посмотреть на структуру данных, которая быстро дает результат и не очень тяжелая.
Любые подсказки кто-нибудь?
EDIT:
Это не имело бы смысл использовать массив, так как я могу иметь только 100 или 200 индексов в магазин.
Абхишек
Почему массив становится нереалистичным? требования к памяти полностью зависят от объекта, который вы храните, в этом случае у массива нет накладных расходов. – Giel
Думаю, вы ищете хеш-таблицу. std :: map звучит правильно? http://www.cplusplus.com/reference/map/map/ –
@Giel. Это зависит от плотности. Если числа находятся в диапазоне 1-2^32, и есть только 2 или три элемента, а массив не является решением. Если есть 2^32-2 из них, это так. –