Multi Dimensional Arrays using Template Meta Programming

Mo Hossny

Rate me:

3.05/5 (8 votes)

20 Mar 2004CPOL3 min read

87K

465

A Real Multi-Dimensional Array

Download source files - 2.74 Kb

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.

As described in linear algebra, adding more dimensions fastens the access to data elements.

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!!

Little Enhancement - Adding Allocators

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:).

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By

Mo Hossny

Engineer

Australia

This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

int getat(int* p1, int i, int j, int k, int l) { return p1[l*60+k*12+i*4+j]; } DEBUG CODE GENERATION mov eax, DWORD PTR _l$[ebp] imul eax, 60 ; 0000003cH mov ecx, DWORD PTR _k$[ebp] imul ecx, 12 ; 0000000cH add ecx, DWORD PTR _j$[ebp] add ecx, eax mov edx, DWORD PTR _i$[ebp] lea eax, DWORD PTR [ecx+edx*4] mov ecx, DWORD PTR _p1$[ebp] mov eax, DWORD PTR [ecx+eax*4] RELEASE OPTIMIZED CODE GENERATION mov eax, DWORD PTR _l$[esp-4] mov ecx, DWORD PTR _k$[esp-4] lea edx, DWORD PTR [ecx+eax*4] mov ecx, DWORD PTR _i$[esp-4] add eax, edx lea edx, DWORD PTR [ecx+eax*2] mov ecx, DWORD PTR _j$[esp-4] add eax, edx lea edx, DWORD PTR [ecx+eax*4] mov eax, DWORD PTR _p1$[esp-4] mov eax, DWORD PTR [eax+edx*4]

int getat(int**** p2, int i, int j, int k, int l) { return p2[i][j][k][l]; } DEBUG CODE GENERATION mov eax, DWORD PTR _i$[ebp] mov ecx, DWORD PTR _p2$[ebp] mov edx, DWORD PTR [ecx+eax*4] mov eax, DWORD PTR _j$[ebp] mov ecx, DWORD PTR [edx+eax*4] mov edx, DWORD PTR _k$[ebp] mov eax, DWORD PTR [ecx+edx*4] mov ecx, DWORD PTR _l$[ebp] mov eax, DWORD PTR [eax+ecx*4] RELEASE OPTIMIZED CODE GENERATION mov eax, DWORD PTR _i$[esp-4] mov ecx, DWORD PTR _p2$[esp-4] mov edx, DWORD PTR [ecx+eax*4] mov eax, DWORD PTR _j$[esp-4] mov ecx, DWORD PTR [edx+eax*4] mov edx, DWORD PTR _k$[esp-4] mov eax, DWORD PTR [ecx+edx*4] mov ecx, DWORD PTR _l$[esp-4] mov eax, DWORD PTR [eax+ecx*4]

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.