C ++: группировка целых чисел по общему основанию для экономии памяти

Question

Рассмотрим (отсортированный) вектор беззнаковых значений типа int.

std::vector<unsigned int> data = {1234,1254,1264,1265,1267,1268,1271,1819,1832,1856,
                                  1867,1892,3210,3214,3256,3289};

Предполагая, что каждое целое число без знака имеет длину 4 байта, этот вектор из 16 элементов будет занимать не менее 64 байтов ОЗУ.

Я думаю, что было бы возможно уменьшить использование памяти, группируя эти значения по общему основанию.Рассмотрим, например, представление данных вида

data =
{
   {12..
      ..34, ..54, ..64, ..65, ..67, ..68, ..71
   },
   {18..
      ..19, ..32, ..56, ..67, ..92
   }
   {32..
      ..10, ..14, ..56, ..89
   }
};

. В приведенном выше примере я сгруппировал значения по блокам по 100. Было бы более логично сгруппировать данные по группе 2 ^ 8 = 256или 2 ^ 16 = 65536.

Есть ли тип данных (в std :: или boost :: или др.), Который может сделать для меня такую ​​хитрость, или мне нужно для этого написать собственный тип контейнера?Это звучит как потенциально хорошая идея?

Answer 1

Это работоспособная идея для конкретных входных данных в очень ограниченных сценариях.Увы, std :: не предоставляет такую ​​структуру.Ваше конкретное предложение может быть разумно реализовано в виде дерева.

Остерегайтесь общего радикального порядка, поскольку они обычно используют большие списки, следовательно, используют больше памяти, чем обычный вектор.