SRC: многомерные массивы
От: Кодт Россия  
Дата: 23.09.02 15:07
Оценка: 171 (14)
Как реализовать многомерный массив динамического размера?
Один из подходов — разворачивание его на одномерный массив, то есть задача сводится к проекции вектора индексов на множество целых чисел.

Тема возникла по результатам треда http://www.rsdn.ru/forum/?mid=104547
Автор: Harut
Дата: 23.09.02


Для 2- и 3-мерных случаев
class index2d
{
  size_t m_sizeX, m_sizeY;

public:
  index2d(size_t sizeX, size_t sizeY): m_sizeX(sizeX), m_sizeY(sizeY) {}

  // размер линейного массива
  size_t sizeTotal() const { return m_sizeX * m_sizeY; }

  // линейный индекс
  size_t operator() (size_t x, size_t y) const { return x * m_sizeY + y; }
};

class index3d
{
  size_t m_sizeX, m_sizeY, m_sizeZ;

public:
  index3d(size_t sizeX, size_t sizeY, size_t sizeZ): m_sizeX(sizeX), m_sizeY(sizeY), m_sizeZ(sizeZ) {}

  // размер линейного массива
  size_t sizeTotal() const { return m_sizeX * m_sizeY * m_sizeZ; }

  // линейный индекс
  size_t operator() (size_t x, size_t y, size_t z) const { return (x * m_sizeY + y) * m_sizeZ + z; }
};


способ применения:
index2d i2d(10, 15); // объект-хелпер

std::vector<int> vec; // контейнер данных
vec.setsize(i2d.sizeTotal()); // установка размера

vec[i2d(2, 3)] = 100; // доступ к элементам


Для произвольной размерности: используем синтаксис с переменным числом параметров (...)
#include <stdarg.h>
#include <assert.h>

template <size_t Arity> // "арность", т.е. число измерений
class indexNd
{
  size_t m_sizes[Arity];

public:
  indexNd(const size_t *sizes)
  {
    assert(Arity > 0);
    assert(sizes != NULL);
    for(size_t n = 0; n < Arity; n++)
    {
      assert(sizes[n] > 0);
      m_sizes[n] = sizes[n];
    }
  }

  indexNd(size_t size0, ...)
  {
    assert(Arity > 0);
    va_list args;
    va_start(args, size0);
    initv(size0, args);
  }

  static size_t arity() { return Arity; }

  size_t sizeTotal() const
  {
    size_t t = 1;
    for(size_t n = 0; n < Arity; n++) t *= m_sizes[n];
    return t;
  }

  size_t operator()(const size_t* indices) const
  {
    assert(indices != NULL);
    assert(indices[0] < m_sizes[0]);
    size_t t = indices[0];
    for(int n = 1; n < Arity; n++)
    {
      assert(indices[n] < m_sizes[n]);
      t *= m_sizes[n-1];
      t += indices[n];
    }
    return t;
  }
  size_t operator()(size_t index0, ...) const
  {
    va_list args;
    va_start(args, index0);
    size_t t = indexv(index0, args);
    va_end(args);
    return t;
  }

protected:
  indexNd() {} // только для наследников
  void initv(size_t size0, va_list args)
  {
    assert(size0 > 0);
    m_sizes[0] = size0;
    for(size_t n = 1; n < Arity; n++)
    {
      m_sizes[n] = va_arg(args, size_t);
    }
    va_end(args);
  }

  size_t indexv(size_t index0, va_list args) const
  {
    assert(index0 < m_sizes[0]);
    size_t i = index0;
    for(int n = 1; n < Arity; n++)
    {
      size_t indexN = va_arg(args, size_t);
      assert(indexN < m_sizes[n]);
      i *= m_sizes[n-1];
      i += indexN;
    }
    return i;
  }
};


и способ применения:
indexNd<4> i4d( 10, 20, 30, 40 );

std::vector<int> vec;
vec.setsize(i4d.sizeTotal());

vec[i4d(1, 2, 3, 4)] = 1234;

Можно сделать арность параметром не шаблона, а экземпляра объекта.

Наконец, индексатор можно срастить с контейнером:
template<class TYPE, size_t Arity>
class vectorNd : private indexNd<Arity>
{
  std::vector<TYPE> m_vec;

public:
  vectorNd(size_t size0, ...)
  {
    va_list args;
    va_start(args, size0);
    initv(size0, args);
    va_end(args);
    m_vec.setsize(sizeTotal());
  }

  TYPE& operator()(size_t index0, ...) // увы, круглые скобки вместо квадратных
  {
    va_list args;
    va_start(args, index0);
    TYPE& v = m_vec[indexv(index0, args)];
    va_end(args);
    return v;
  }
  const TYPE& operator()(size_t index0, ...) const
  {
    va_list args;
    va_start(args, index0);
    TYPE& v = m_vec[indexv(index0, args)];
    va_end(args);
    return v;
  }
};



Благодарности:
Harut — за вопрос
Bell — за первотолчок
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.