12,548,647 members (54,941 online)
alternative version

76.8K views
17 bookmarked
Posted

Multi Dimensional Arrays using Template Meta Programming

, 20 Mar 2004 CPOL
 Rate this:
A Real Multi-Dimensional Array

Introduction

Multi-dimensional arrays provide a nice mathematical data structure for mathematical and soft computing projects. Tensor is usually the data structure used to store data in multi-dimensional arrays. Helper classes helps in design subscripting operators to select rows, cols, and plates. Helper classes may be implemented by adding constant template arguments describing the state of the array, or sub-array. Refer to "Tensor templates", " 2D Matrix Container with [][] indexing", and "Template-Based Helper Classes: An application to Multidimensional Arrays" for more details. A tensor is a uni-dimensional array with indexing facility that allows manipulation as N-dimensional matrix. Computational cost for accessing a specific element grows exponentially as the number of dimensions increases. Helper classes force many constructors/destructors calls for temporary objects. Actually helper classes provide a nice solution for little projects with short loops.

In mathematics, finding a solution in some space costs a lot. One way to find fast solution is transforming the problem (actually the search space) into a larger space where more dimensions may lead to faster solution.

Now, consider the following piece of code:

```int* pi1=new int[20];
int** pi2=new int*[4];
for(int i=0; i<4; i++)
pi2[i]=new int[5];```

Now, what do you think? How shall I access the element located in 2nd row and 3rd col? How much does it cost for each of them?

Obviously, `pi2[2][3]` is faster than `pi1[2*4+3]`.

How about very large N-dimensional arrays with complex objects!? Can you imagine this!?

"Template-Based Helper Classes: An application to Multidimensional Arrays" provides a nice solution, but subscripting operators cost a lot for computations, costs much if repeated in a very long loop, uses lots of helper temporary classes, and fragments the memory.

Problem Statement

How shall we develop a template class that generates multi-dimensional pointers!!?

```int i;
int* pi;
int** ppi;
int*** pppi;
...```

How shall we add number of dimensions as a template argument!?

Basic Solution

The basic idea makes use of Template Meta-Programming, implementing a template class with argument `M` indicating the number of nested pointers.

Consider the following class:

```template<_sizetype M>
class multi_ptr
{
public:
typedef double T;
typedef multi_ptr<M-1>::pointer* pointer;
};

class multi_ptr<0>
{
public:
typedef double T;
typedef T pointer;
};```

Now, consider how to declare a multi-dimensional pointer:

`multi_ptr<3>::pointer p3;`

Now, more facilities are needed; we need to add class template argument `T` indicating the type of this array.

More Enhancement - Adding Class Template Argument

Template Meta-Programming works only for single argument template classes. Adding a class template argument cannot be achieved directly.

An outer class should be used to pass the template argument through. Consider the following `multi_array` class:

```template<class T, _sizetype N>
class multi_array
{
public:
template<_sizetype M>
class multi_ptr
{
public:
typedef multi_ptr<M-1>::pointer* pointer;
};

class multi_ptr<0>
{
public:
typedef T pointer;
};

typedef multi_ptr<N>::pointer pointer;
typedef const pointer const_pointer;
};```

Class template argument `T` is passed through the outer `multi_array` class with the number of dimensions `N`. The inner `multi_ptr` class makes use of the outer template argument `T` for type specialization.

Now the very important question is:

How shall we allocate this multi dimensional array!? We need to specialize nested allocating loops!!

How shall we build a varying number of nested allocating loops!?

We need a little addition for allocation!!

A simple compile-time loop provides a nice solution for generating a variable number of nested loops. An inner class called `multi_allocator` is responsible for allocating multi-dimensional pointers.

```template<_sizetype M>
class multi_allocator
{
public:
static multi_ptr<M>::pointer alloc(_sizetype* dims)
{
_sizetype i;
multi_ptr<M>::pointer rtn;
rtn=new multi_ptr<M-1>::pointer[dims[0]];
for(i=0; i<dims[0]; i++)
rtn[i]=multi_allocator<M-1>::alloc(dims+1);
return rtn;
}
};

class multi_allocator<1>
{
public:
static multi_ptr<1>::pointer alloc(_sizetype* dims)
{
multi_ptr<1>::pointer rtn;
rtn=new T[dims[0]];
return rtn;
}
};```

Now, fine touches is needed to finalize the `multi_array` class. Constructors, casting operators, and data members should be added.

Finalizing multi_array - Adding constructors and casting operators

```typedef unsigned int _sizetype;

template<class T, _sizetype N>
class multi_array
{
public:
template<_sizetype M>
class multi_ptr
{
public:
typedef multi_ptr<M-1>::pointer* pointer;
};

class multi_ptr<0>
{
public:
typedef T pointer;
};

template<_sizetype M>
class multi_allocator
{
public:
static multi_ptr<M>::pointer alloc(_sizetype* dims)
{
_sizetype i;
multi_ptr<M>::pointer rtn;
rtn=new multi_ptr<M-1>::pointer[dims[0]];
for(i=0; i<dims[0]; i++)
rtn[i]=multi_allocator<M-1>::alloc(dims+1);
return rtn;
}
};

class multi_allocator<1>
{
public:
static multi_ptr<1>::pointer alloc(_sizetype* dims)
{
multi_ptr<1>::pointer rtn;
rtn=new T[dims[0]];
return rtn;
}
};

typedef multi_ptr<N>::pointer pointer;
typedef const pointer const_pointer;
typedef multi_allocator<N> allocator;

operator pointer(){return _pdata;}

multi_array(const _sizetype d1, ...)
{
memcpy(_pdims, &d1, N*sizeof(_sizetype));
_pdata=allocator::alloc(_pdims);
}

multi_array(const _sizetype* pdims)
{
memcpy(_pdims, pdims, N*sizeof(_sizetype));
_pdata=allocator::alloc(_pdims);
}

protected:
pointer _pdata;
_sizetype _pdims[N+1];

};```

Thank You!!

Thanx a lot for your time. I hope you enjoyed this idea!! Hear from you soon:).

Share

 Engineer Australia
No Biography provided

You may also be interested in...

 Pro Pro

 First Prev Next
 error using g++ 4.4.5 axllaruse10-May-11 2:55 axllaruse 10-May-11 2:55
 Deallocate? GregoryBook29-Sep-06 15:50 GregoryBook 29-Sep-06 15:50
 Re: Deallocate? Mohammed Hossny23-Oct-06 18:27 Mohammed Hossny 23-Oct-06 18:27
 invalid template argument 'N' SMJT17-Sep-04 7:31 SMJT 17-Sep-04 7:31
 Re: invalid template argument 'N' SMJT17-Sep-04 7:38 SMJT 17-Sep-04 7:38
 Re: invalid template argument 'N' Mohammed Hossny17-Sep-04 12:24 Mohammed Hossny 17-Sep-04 12:24
 Re: invalid template argument 'N' SMJT17-Sep-04 21:35 SMJT 17-Sep-04 21:35
 Re: invalid template argument 'N' Mohammed Hossny19-Sep-04 9:12 Mohammed Hossny 19-Sep-04 9:12
 Compiler error on VC++.NET 2003 Rui A. Rebelo8-Apr-04 4:11 Rui A. Rebelo 8-Apr-04 4:11
 Re: Compiler error on VC++.NET 2003 Mohammed Hossny10-Apr-04 22:01 Mohammed Hossny 10-Apr-04 22:01
 Re: Compiler error on VC++.NET 2003 Mohammed Hossny3-Jun-04 1:56 Mohammed Hossny 3-Jun-04 1:56
 pi2[2][3] is faster than pi1[2*4+3] ?? sahn021-Mar-04 3:20 sahn0 21-Mar-04 3:20
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? Mohammed Hossny21-Mar-04 3:23 Mohammed Hossny 21-Mar-04 3:23
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? Tim Smith21-Mar-04 6:14 Tim Smith 21-Mar-04 6:14
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? Mohammed Hossny21-Mar-04 6:26 Mohammed Hossny 21-Mar-04 6:26
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? Tim Smith21-Mar-04 7:16 Tim Smith 21-Mar-04 7:16
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? Don Clugston21-Mar-04 15:28 Don Clugston 21-Mar-04 15:28
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? Nitron22-Mar-04 3:16 Nitron 22-Mar-04 3:16
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? John M. Drescher22-Mar-04 3:58 John M. Drescher 22-Mar-04 3:58
 Re: pi2[2][3] is faster than pi1[2*4+3] ?? Mohammed Hossny22-Mar-04 22:58 Mohammed Hossny 22-Mar-04 22:58
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Oct-16 0:06 Refresh 1