Требется создать многомерный масив (например, 2x3 или 4x3x3) во время выполнения программы (run-time),так как размерность массива вычисляется по ходу работы программы (на этапе компиляции неизвестна ни одна размерность). Какую структуру лучше всего использовать для решения этой задачи?

Здравствуйте, NewBayes, Вы писали:

NB>Требется создать многомерный масив (например, 2x3 или 4x3x3) во время выполнения программы (run-time),так как размерность массива вычисляется по ходу работы программы (на этапе компиляции неизвестна ни одна размерность). Какую структуру лучше всего использовать для решения этой задачи?

Например, так:

int **arr = new int* [2];

for (int i = 0; i < 2; ++i)
{
   arr[i] = new int[3];
}

Получается массив указателей на динамические массивы.

Удаляем в обратном порядке.

Здравствуйте, NewBayes, Вы писали:

NB>Требется создать многомерный масив (например, 2x3 или 4x3x3) во время выполнения программы (run-time),так как размерность массива вычисляется по ходу работы программы (на этапе компиляции неизвестна ни одна размерность). Какую структуру лучше всего использовать для решения этой задачи?

Линейный массив, кортеж размерностей и функция трансляции кортежа индексов в линейный индекс.

В качестве и массива, и кортежа можно использовать std::vector'ы.

template<class T>
class hypercube
{
  vector<size_t> sizes_;
  vector<T> items_;

  size_t linear_size() const
  {
    return accumulate(sizes_.begin(), sizes_.end(), (size_t)1, multiplies<size_t>());
  }
  size_t linear_index(vector<size_t> const& indices)
  {
    assert(indices.size()==sizes_.size());
    size_t li = 0;
    for(int i=0, n=sizes_.size(); i!=n; ++i) // по схеме Горнера
      li = li*sizes_[i] + indices[i];
    return li;
  }

public:
  void setsizes(vector<size_t> const& sizes)
  {
    sizes_ = sizes;
    items_.resize(linear_size);
  }
  T& at(vector<size_t> const& indices)
  {
    return items_[linear_index(indices)];
  }
  // и т.д. по вкусу
};

Если количество измерений известно на стадии компиляции — то может подойти просто вектор векторов векторов...

Одномерный вектор размерности x*y*z*... плюс адаптер к нему, принимающий многомерный синтаксис.

NB>Требется создать многомерный масив (например, 2x3 или 4x3x3) во время выполнения программы (run-time),так как размерность массива вычисляется по ходу работы программы (на этапе компиляции неизвестна ни одна размерность). Какую структуру лучше всего использовать для решения этой задачи?

Одномерный массив, и индексировать Y * SizeX + X

Ответ понятен. А вот ещё вопрос: а В-деревья помогут в решении того же вопроса, чтобы избежать пересчёта векторного индекса в линейный?

и ещё, а класс предложенный Вами сможет создать вектор с 5млрд. элементов? Мне кажется я ошибаюсь. А ведь тот куб, который требуется в задаче, может содержать и намного больше элементов.

Здравствуйте, NewBayes, Вы писали:

NB>и ещё, а класс предложенный Вами сможет создать вектор с 5млрд. элементов? Мне кажется я ошибаюсь.

Да ради бога. На 64-битной платформе-то.

NB>А ведь тот куб, который требуется в задаче, может содержать и намного больше элементов.

OLAP? Тогда, может, использовать специализированные инструменты?

Здравствуйте, NewBayes, Вы писали:

NB>Ответ понятен. А вот ещё вопрос: а В-деревья помогут в решении того же вопроса, чтобы избежать пересчёта векторного индекса в линейный?

Помогут не B-деревья, а многоярусные массивы указателей.
Для 4-мерного (x,y,z,t)
px : XSize указателей на (y,z,t) — смещений в pxy
pxy : XSize*YSize указателей на (z,t) — смещений в pxyz
pxyz : XSize*YSize*ZSize указателей на (t) — смещений в pxyz
pxyzt : XSize*YSize*ZSize*TSize элементов нашего гиперкуба

От pxyzt ты никуда не деваешься, но заводишь ещё несколько дополнительных массивов (по сути, табличная функция для пересчёта векторного индекса в линейный).
Мне кажется, что операция умножения не намного медленнее операции разыменования. То есть, лучше сэкономить память.

Другое дело, что если твой гиперкуб разрежен, то лучше применить какие-то особые структуры — с учётом характера разрежения.
При сильном разрежении — да, B-деревья с ключами-векторными индексами.
При умеренном — может быть, BSP-деревья, содержащие, начиная с какого-то уровня, неразреженные гиперкубики.
Если разрежение по слоям (например, по y) — то разреженный массив (y) этих слоёв (xzt).

Здравствуйте, Maxim S. Shatskih, Вы писали:

NB>>Требется создать многомерный масив (например, 2x3 или 4x3x3) во время выполнения программы (run-time),так как размерность массива вычисляется по ходу работы программы (на этапе компиляции неизвестна ни одна размерность). Какую структуру лучше всего использовать для решения этой задачи?

MSS>Одномерный массив, и индексировать Y * SizeX + X

А не легче ли использовать уже готовый valarray и slice. Из STL.
Та же самая идея. К тому же сделан специально для вычислений. Как раз для многомерных массивов

Здравствуйте, NewBayes, Вы писали:

NB>Требется создать многомерный масив (например, 2x3 или 4x3x3) во время выполнения программы (run-time),так как размерность массива вычисляется по ходу работы программы (на этапе компиляции неизвестна ни одна размерность). Какую структуру лучше всего использовать для решения этой задачи?


Используй valarray из STL. С помощью slice как раз организуется многомерный массив. К тому же всё оптимизировано для вычислений