Здравствуйте.

Для реализации некоторого автоматного алгоритма требуется организация больших объёмов однобитных данных (boolean, если угодно), скорость работы с которыми сильно критична.
Более точно, эти данные можно представить в виде двумерного массива, i-ый столбец которого состоит из (const*i) элементов. Причём играет роль высокая скорость добора до значений элементов, находящихся в соседних столбцах и соседних строках, как показано на рисунке : ( в клетках указаны индексы элементов массива)



или, в более сложном случае :



Дополнительное условие состоит в том, что этот массив данных должен быть динамическим в плане добавления новых столбцов и содержаться в некотором классе.

Понятно, что bool **bArray и дальнейшее выделение памяти операцией new является доступным и популярным решением. Но, может, существуют какие-то специфические приёмы эффективной органиации таких данных по скорости? = какие-то тИповые или программные решения, может быть засовывание однобитных данных в более ёмкие и работа с ними, может быть какое-то внутреннее расслоение, хеш и т.п., а может быть вообще следует отказаться от array-ной топологии и применить что-то другое?? Посоветуйте, пожалуйста, кто компетентен в этой области.

Можно выделить память под весь массив сразу, используя каждый бит, а далее подобно тому, как делается в растровых изображениях. Здесь, я так понял, каждый следующий столбец содержит на const элементов больше, чем предыдущий? Так всегда? Тогда выборка может осуществляться с использованием формул прогрессии.

Чего не хватает в этом интерфейсе?


Является ли операция добавления нового столбца критичной к скорости?

Согласен, что следует назначить некоторую начальную размерность массива, и затем увеличивать её.



Да, всегда. Для четырёхугольной клетки - на 8 больше предыдущего, для треугольной - на 12 и т.п. Проще, чем прогрессия.

Наверно, я похо задал вопрос: суть не в интерфейсе, а в его реализации, соответствующей означенным характеристикам. Например, с использованием специфического вида матрицы, пытаться вычислить адрес требуемого элемента быстрее, чем это сделает система. Или что-то ещё...



В принципе, не является. Но добавленные элементы не должны сильно проигрывать в скорости добора элементам априорно заданной матрицы.

причем переход к более емким ( чем bool ) типам -- очень желателен ( в идеале int ) -- такие массивы компъютеру гораздо проще обрабатывать.