Экономия времени и пространства DataStructure для хранения больших данных (порядка 10 ^ 9) и быстрого доступа к ним

Question

В конкурентном кодировании нам, как правило, нужен DS, такой, чтобы сказать для некоторого целого числа i в диапазоне (1 и если я вообще использую концепцию карты, то find () (функция для доступа к моим данным) займет время входа в систему.

1) Массив не занимает мало места, а карта не эффективна по времени с моей точки зрения приложения.

Есть ли лучший DS, чтобы выполнить мою задачу? Любая помощь приветствуется. спасибо:)

Answer 1

std::unordered_map ваш приятель.

В отличие от std::map, он предлагает амортизированный O(1) сложность поиска и времени вставки. Базовая структура данных std::unordered_map - это хеш-таблица - корзина с отдельной цепочкой из двусвязного списка, содержащая записи в обычном случае. С другой стороны, std::map - это сбалансированное бинарное дерево поиска под капотом, которое предлагает логарифмический поиск.

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