Как реализовать многомерный массив динамического размера?
Один из подходов — разворачивание его на одномерный массив, то есть задача сводится к проекции вектора индексов на множество целых чисел.
Тема возникла по результатам треда
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://www.rsdn.ru/forum/?mid=104547Автор: Harut
Дата: 23.09.02
да — кто бы мог подумать, что выродится из такого вопроса =)
Здравствуйте Igor Soukhov, Вы писали:
IS>Здравствуйте Кодт, Вы писали:
К>>Тема возникла по результатам треда http://www.rsdn.ru/forum/?mid=104547Автор: Harut
Дата: 23.09.02
IS>да — кто бы мог подумать, что выродится из такого вопроса =)
Тема вроде бы уже поднималась раньше: как делать многомерные индексы.
То есть это вполне утилитарная задача.
Я ее постоянно решаю с помощью фиксированно-мерных преобразователей индекса.
Еще один способ — это создание оберток, уменьшающих размерность.
На этой основе можно много наворотов сделать, например, устанавливать размер по n-ной координате...
typedef size_t dim_t; // целочисленный тип - номер измерения
// (тут я опускаю все template<> и friend - дабы не засорять вид).
// многомерный контейнер
class vecNd
{
public:
// доступ через обертки
dims& dimensions() { return m_dims; } // из соображений производительности - агрегируем этот объект
const dims& dimensions() const { return m_dims; }
reduce operator[](size_t i) { return reduce(this, 0, 1, i); }
// атрибуты
dim_t getDimensions() const;
void setDimensions(dim_t d);
size_t getSize(dim_t d) const;
void setSize(dim_t d, size_t s);
// данные
T getAt(size_t linear);
void setAt(size_t linear, T value);
private:
dims m_dims;
// а также одномерное хранилище, например, std::vector
};
// обертка к измерениям
class dims
{
public:
size_t operator[](dim_t d) const { return owner->getSize(d); } // чтение
setdim operator[](dim_t d) { return setdim(owner, d); } // запись - через еще одну обертку
operator dim_t() const { return owner->getDimensions(); }
dim_t operator = (dim_t d) { owner->setDimensions(d); } // установка размерности
private:
vecNd* owner;
protected:
dims(vecNd* _owner);
};
// обертка установки измерения
class setdim
{
public:
size_t operator = (dim_t s) { owner->setSize(d, s); }
private:
vecNd* owner;
dim_t d;
protected:
setdim(vecNd* _owner, dim_t _d);
};
// уменьшатель размерности - подпространство
class reduce
{
public:
reduce operator[](size_t i)
{
assert(d < owner->getDimensions());
return reduce(owner, d+1, step * owner->getSize(d), offset * step + i);
}
operator T() const
{
assert(d == owner->getDimensions());
return owner->getAt(offset);
}
T operator = (T value)
{
assert(d == owner->getDimensions());
owner->setAt(offset);
return T;
}
private:
vecNd* owner;
dim_t d;
size_t step; // произведение размеров всех предшествующих измерений
size_t offset; // смещение данного подпространства относительно начала
protected:
reduce(vecNd* _owner, dim_t _d, size_t _s, size_t _o);
};
///////////////////////
// пример использования
vecNd matrix;
// размерность
matrix.dimensions() = 2;
// измерения
matrix.dimensions()[0] = 10;
matrix.dimensions()[1] = 20;
// значения
matrix[0] = 2; // assertion fault: обращение на запись к более-чем-нуль-мерному подпространству
matrix[1][2] = 1; // нульмерное подпространство - все окей
matrix[3][4][5] = 3; // попытка редукции нульмерного подпространства
x = matrix[6]; // невозможно привести подпространство к значению
x = matrix[7][8]; // нульмерное подпространство - все окей
x = matrix[9][10][11]; // снова попытка редукции нульмерного пространства
Перекуём баги на фичи!
* thriving in a production environment *
