Pages

About Me - 关于我

My photo
Madison, WI, United States
Joy Young ~~

2012/07/21

Dynamically creating arbitrary dimensional array in a continuous memory block

This array should support arr[3][2][1][0] and also support (***arr)[100] and (**arr)[10][10] and (*arr) [3][2][1]. That means, in terms of any dimension, it is allocated in a continuous memory block.
 I will post the code and the example below. The code works both on VC10 and GCC 4.7.0.And I have widely used it in many projects. It is tested.
The logic behind the code is to build the array level by level. The content of a pointer is a lower dimensional pointer, and the only the lowest dimensional pointers are pointing to the real data.
Note that the class itself just works like a function -- the only reason I used a class IdealArrBuilder not a function is that in C++, a function does not support partial specialization, which is crucial in this implementation. So it is NOT a container; Neither is it a smart pointer. It is just like a function that takes a set of dimension parameters and returns a high dimensional pointer  -- in fact, a hierarchy of multidimensional pointers, check out the examples of how we use the pointers, and then you may get the picture how the hierarchy is like.
The reason I do not use a container or smart pointer is that I do not need to. In most project (image processing)  I worked on, a light weighted raw pointer hierarchy is more than enough and compilable with old C-style interface.
{
The newest update: I have finished a new code from another angle to achieve the same purpose:
In the new method, I implemented a multi-array class instead of a function-like method to produce an array-like raw pointer hierarchy. I will give detailed explanation of its advantage and usage.
 }

#include <iostream>
#include <vector>
using namespace std;
#define SUCCESS 1
#define PTRERR 0
template<class ElemType, size_t N_Dim> 
class IdealArrBuilder : public IdealArrBuilder<ElemType*, N_Dim-1> {
public:
      typedef typename IdealArrBuilder<ElemType*, N_Dim-1>::FinalType FinalType;
protected:
      template<class RandomAccessIter>
     static FinalType _bldCurDim(size_t sizec, RandomAccessIter size_beg, ElemType lower_dim) { 
            RandomAccessIter cur_iter = size_beg;
            size_t dim_size = 1;
            for (size_t i = 0; i < sizec; ++i)
                  dim_size *= *(cur_iter++);
            ElemType* higher_dim = new ElemType[dim_size];     
            higher_dim[0] = lower_dim;
            for (size_t i = 1; i < dim_size; ++i)
                  higher_dim[i] = higher_dim[i - 1] + *(size_beg+sizec);
            return IdealArrBuilder <ElemType*, N_Dim - 1>::_bldCurDim(sizec - 1, size_beg, higher_dim); 
      }
      static ElemType _freeCurDim(FinalType ptr){
            ElemType * cur_ptr = IdealArrBuilder <ElemType*, N_Dim - 1>::_freeCurDim(ptr);
            if (cur_ptr == NULL) return NULL;
            ElemType lower_ptr = *cur_ptr;
            delete [] cur_ptr;   
            return lower_ptr;
      }

public:
      template<class RandomAccessIter>
      static FinalType ialloc(RandomAccessIter size_beg){
            RandomAccessIter cur_iter = size_beg;
            size_t dim_size = 1;
            for (size_t i = 0; i < N_Dim; ++i) 
                  dim_size *= *(cur_iter++);
            ElemType* base = reinterpret_cast <ElemType*> (operator new (dim_size*sizeof(ElemType)));
            return IdealArrBuilder <ElemType*, N_Dim - 1>::_bldCurDim(N_Dim - 1, size_beg, base);
      }
      template<class RandomAccessIter>
      static FinalType inew(RandomAccessIter size_beg)    {
            RandomAccessIter cur_iter = size_beg;
            size_t dim_size = 1;
            for (size_t i = 0; i < N_Dim; ++i)
                  dim_size *= *(cur_iter++);    
            ElemType* base = new ElemType[dim_size];
            return IdealArrBuilder <ElemType*, N_Dim - 1>::_bldCurDim(N_Dim - 1, size_beg, base);
      }
      static int ifree(FinalType ptr)     {
            if (ptr == NULL) return PTRERR;
            ElemType * cur_ptr = IdealArrBuilder <ElemType*, N_Dim - 1>::_freeCurDim(ptr);
            if (cur_ptr == NULL) return PTRERR;
            operator delete (cur_ptr);
            return SUCCESS;
      }
      static int idelete(FinalType ptr)    {
            if (ptr == NULL) return PTRERR;
            ElemType * cur_ptr = IdealArrBuilder <ElemType*, N_Dim - 1>::_freeCurDim(ptr);
            if (cur_ptr == NULL) return PTRERR;
            delete [] cur_ptr;
            return SUCCESS;
      }


};
template <class ElemType>
class IdealArrBuilder< ElemType, 0> {

protected:
      typedef ElemType FinalType;
      template<class RandomAccessIter>
      static FinalType _bldCurDim (size_t sizec, RandomAccessIter size_beg, ElemType lower_base) { 
            return lower_base; 
      }
      static ElemType _freeCurDim(FinalType ptr){
            return ptr;
      }
};

/***********************************************
USAGE
size_t sizes[] = {2,3,3,3}; //2 is the highest dimension.
MyClass **** my_classes = IdealArrBuilder<MyClass, 4>::inew(sizes) ;
IdealArrBuilder<MyClass, 4>::idelete(my_classes);
**********************************************
MONSTEROUS USAGE//To allocate a 10000-dimensional array, the size of each dimension is the N.O. of current dimension. O(10^40000)
size_t sizes[10000];
for (int i = 0; i < 10000; ++i)
sizes[i] = 10000 - i;
IdealArrBuilder<MyClass, 10000>::FinalType my_classes = IdealArrBuilder<MyClass, 10000>::inew(sizes) ;
IdealArrBuilder<MyClass, 10000>::idelete(my_classes);
***********************************************/
//Example:
struct Foo
{
      int i, j;
};
int main(){
      /*It works too:*/
      //size_t sizes[] = {4, 5, 6, 2};//4 is the highest dimesion
      //Foo ****arr = IdealArrBuilder<Foo, 4>::inew(sizes);
     
      vector<int> sizevec;
      sizevec.push_back(4);
      sizevec.push_back(5);
      sizevec.push_back(6);
      sizevec.push_back(2);
      Foo ****arr = IdealArrBuilder<Foo, 4>::inew(sizevec.begin());
      //IdealArrBuilder<Foo, 4>::FinalType arr = IdealArrBuilder<Foo, 4>::inew(sizevec.begin()); //Or this way
      (****arr).i = 5;
      (***arr)->j = 6;
      arr[2][3][0][0].i = 3;
      arr[2][3][0][1].i = 4;
      const auto &arrref = arr;
      cout<<(****arrref).j<<endl;
      cout<<arrref[2][3][0]->i<<endl;
      cout<<arrref[2][3][0][1].i<<endl;
      cout<<(***arrref)[157].i<<endl; //157 = 2*5*6*2 + 3*6*2 + 0*2 + 1
      cout<<(**arrref)[78][1].i<<endl; // 78 = 2*5*6 + 3*6
      cout<<(*arrref)[13][0][1].i<<endl; // 13 = 2*5 + 3
      cout<<(*arr[2][3])[1].i<<endl;//*arr[2][3] <=> arr[2][3][0]
      cout<<(*(*arr)[13])[1].i<<endl;//(*arr)[13] <=> arr[2][3]
     
     
}

 
Output:
6
3
4
4
4
4
4
4

No comments:

Post a Comment