Выбрать наиболее оптимальную структуру для хранения и поиска данных по значению(С++)
Всем добрый день. Помогите пожалуйста определится: какая структура данных в языке С++ наиболее оптимально подойдет для хранения большого количества десятизначных целых положительных чисел, если подразумевается только хранение этих чисел в выбранной структуре и поиск числа по значению. Важно , чтобы выбранная структура данных занимала как можно меньше объема памяти. Количество чисел 100'000'000'. Диапазон значений элемента - [0, 9 999 999 999].Добавление/удаление элемента не предусматривается.Заранее благодарен.
Ответы (2 шт):
Если количество чисел заранее известно, то std::array. Если нет ― std::vector.
Если "Добавлять/удалять/изменять не нужно" - теоретически можно использовать идеальное хеширование, тогда к минимальному объему добавится максимально быстрый поиск... Но это достаточно сложный путь.
Так что, думаю, проще всего - обычный массив. Только вот для представления такого диапазона чисел нужно 34 бита, так что обычного 4-байтового числа не хватит. Если память критична - можно соорудить 5-байтовые числа, и занять примерно 477 мегабайт. Если же 763 мегабайта - некритично, то можно воспользоваться массивом 8-байтовых unsigned long long. Вариант с упаковкой битов от разных чисел, чтоб использовать только 405 мегабайт, не рассматриваем - можно, но слишком сложно, будет тормозить поиск.
Можно разбить на 4 массива, в которых хранить по 4 младших байта чисел, а номер массива от 0 до 3 - это старшие 2 бита. Получится неплохая экономия, до 382 мегабайт...
Конечно же, для применения бинарного поиска массив должен быть отсортирован.
Можно использовать array - он не добавляет накладных расходов на косвенное обращение.