Click here to Skip to main content
Click here to Skip to main content

Multi Dimensional Arrays using Template Meta Programming

, 20 Mar 2004
Rate this:
Please Sign up or sign in to vote.
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.

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

License

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

Share

About the Author

cMoXIV
Engineer
Australia Australia
No Biography provided

Comments and Discussions

 
Generalerror using g++ 4.4.5 Pinmemberaxllaruse10-May-11 2:55 
QuestionDeallocate? PinmemberGregoryBook29-Sep-06 15:50 
AnswerRe: Deallocate? PinmemberMohammed Hossny23-Oct-06 18:27 
Generalinvalid template argument 'N' PinmemberSMJT17-Sep-04 7:31 
GeneralRe: invalid template argument 'N' PinmemberSMJT17-Sep-04 7:38 
GeneralRe: invalid template argument 'N' PinmemberMohammed Hossny17-Sep-04 12:24 
GeneralRe: invalid template argument 'N' PinmemberSMJT17-Sep-04 21:35 
GeneralRe: invalid template argument 'N' PinmemberMohammed Hossny19-Sep-04 9:12 
GeneralCompiler error on VC++.NET 2003 PinmemberRui A. Rebelo8-Apr-04 4:11 
GeneralRe: Compiler error on VC++.NET 2003 PinmemberMohammed Hossny10-Apr-04 22:01 
GeneralRe: Compiler error on VC++.NET 2003 PinmemberMohammed Hossny3-Jun-04 1:56 
Questionpi2[2][3] is faster than pi1[2*4+3] ?? Pinmembersahn021-Mar-04 3:20 
AnswerRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberMohammed Hossny21-Mar-04 3:23 
GeneralRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberTim Smith21-Mar-04 6:14 
GeneralRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberMohammed Hossny21-Mar-04 6:26 
GeneralRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberTim Smith21-Mar-04 7:16 
GeneralRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberDon Clugston21-Mar-04 15:28 
GeneralRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberNitron22-Mar-04 3:16 
GeneralRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberJohn M. Drescher22-Mar-04 3:58 
GeneralRe: pi2[2][3] is faster than pi1[2*4+3] ?? PinmemberMohammed Hossny22-Mar-04 22:58 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140827.1 | Last Updated 21 Mar 2004
Article Copyright 2004 by cMoXIV
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid