Как организовать многомерный массив неизвестной заранее размерности, растущий во все стороны?
Уважаемые Тостеры,
Помогите, пожалуйста, разобраться, как должна быть организована структура данных.
Имеем изначально один элемент. Далее, в зависимости от обрабатываемых данных, имеем необходимость вставлять элементы до или после этого первого. Получаем одномерный массив, тут все понятно. Далее, от того же первого элемента имеем необходимость добавлять элементы до и после, но уже в другом измерении. Получаем двумерный массив с нашим первым элементом где-то в середине. И так далее, неизвестное заранее количество измерений в зависимости от обрабатываемых данных.
Можно ли организовать подобное лаконично и просто, без многочисленного копирования данных, используя, например, контейнеры STL?
Или следует сначала определить индексы всех элементов в будущем многомерном массиве, и лишь потом собирать его, зная размерности?
Но только размер измерений для всех элементов будет одинаковым. Т.е. двумерный массив - только прямоугольник (треугольник не выйдет), трехмерный - параллепипед, четырёхмерный - ну вы поняли :-).
Если вам нужны размерности разной длинны, то я бы посоветовал вам дерево (с неограниченным количеством потомков). Все потомки корня - элементы первой размерности. Все потомки первого элемента (из предыдущего списка) - как раз ответвление. А так, как в дереве список потомков может быть null, то можно делать структуры неправильной геометрической формы (образно).
Смотрите. Проблема не в геометрической форме, не том, что это "гиперпараллилепипед" получится. Именно он и нужен.
Проблема в том, что ему во все стороны расти нужно, то есть перед нулевыми индексами вставлять, а не только после последних добавлять, причем эффективно. В одномерном случае std:vector не очень хорош для решения таких задач. std::list хорошо вставляет и в начало, ему, конечно, все равно куда вставлять. Равно как и некоторые другие контейнеры эффективно работали бы в одномерном случае.
Но boost::multy_array, похоже, пока недостаточно обобщен для того, чтобы использовать другой способ организации. Будь у него возможность задавать тип базового одномерного контейнера в качестве параметра, он не был бы аналогом только std::vector.
Интересно что и функционал развит у него в другом направлении. Очень похоже на гиперкуб из OLAP - можно слайсить. Очень интересный контейнер, хотя и для другой задачи.
fshp: Строго говоря, не дерево нужно, а network со связями вдоль ребер. Видимо, самое разумное сначала все собрать, а многомерный массив использовать лишь для компактного хранения и представления результата.
fshp: А так Вы правы. Даже, немного по-другому взглянув на задачу, понимаю, что даже существуй такой контейнер, он бы не облегчил задачу, а привел бы к новым трудностям, нехарактерным для подхода, основанного на network'ах.
В общем, boost::graph мне в руки, строить network, выяснять элементы многомерного массива. А для хранения идеально подойдет предложенный Вами контейнер - ведь он больше ориентирован не на работу в динамике, а на хранение и дальнейший анализ.
fshp: Хех :) Кстати, понял, что упрекать multi_array в отсутствии у него возможности задать базовый одномерный контейнер как минимум забавно :) Семен Семеныч, он же и так уже array :)))
