C ++ std :: map против динамического массива
Я пытаюсь создать трехмерный массив логических значений, который сообщает мне, посещал ли я ранее место в трехмерном пространстве для простого алгоритма навигации. Массив может быть довольно большим (что-то вроде 1 000 000 x 1 000 000 x 1 000 000 или, возможно, больше), поэтому мне интересно, будет ли быстрее объявить массив такого размера и установить для каждого логического значения значение false или сделать карта с ключом координаты (x, y, z) и значением типа bool.
Из того, что я понял, массиву потребуется O (1) для поиска или изменения координаты, а карте потребуется O (log n) для поиска или вставки значения. Очевидно, что для доступа к значениям массив быстрее. Однако смещает ли это время, необходимое для объявления такого массива?
Спасибо
Решение
Даже при 1 бите на бул ваш массив будет занимать 2 ** 39 байт. Я бы предложил set если не будет слишком много элементов, которые будут true,
Вы можете использовать класс, чтобы скрыть детали реализации, и использовать одномерный набор.
Другие решения
Вы пытались вычислить, сколько памяти потребуется для такого массива? Много!
Используйте std :: map, если упорядочение точек важно, или std :: unordeded_map, если нет. Также неупорядоченная карта дает вам постоянное время вставки и поиска.
Я думаю, что какое-то дерево поиска, вероятно, то, что вы ищете (например, k-d tree).
Вы собираетесь создать массив, который составляет один эксабайт, предполагая, что вы используете 8 бит на точку? Вау, у тебя много оперативки!
Я думаю, что вы должны переосмыслить свой подход.