Tuesday, December 16, 2008

c++: multidimensional arrays in the (dynamic) memory

I know some solutions how to store multidimensional arrays in the (dynamic) memory.
I'd like to share this knowledge because I noticed that not all of the developers understand what is going on in this field.
Let's look at different ways how to create 2-dimension array of objects of the class A which code is below

class A
{
    public:
        void * operator new(size_t size)
        {
            void *p = malloc(size);
            cout << "new, size: " << size << "\n";
            return p;
        }

        void * operator new[](size_t size)
        {
            void *p = malloc(size);
            cout << "new[], size: " << size << "\n";
            return p;
        }

        A() 
        {   
            cout << "A()\n";
            id = ++counter;
        }

        ~A()
        {   
            cout << "~A()\n";
        }   

        void call()
        {   
            cout << "id #" << id << ", " << counter << " times constructor of A was called\n";
        }

        static int counter;
        int id; 
};

int A::counter = 0;
I added some code for tracing operator new, constructor and destructor calls.
Each time the constructor is called value of class static variable counter is incremented by 1 and its new value is assigned to class member variable id.
  • The first method and the simplest.
    Simply to allocate 2x2 array of A on the stack.
    cout << "size of A: " << sizeof(A) << "\n";
    A z[2][2];
    z[1][1].call();
    (z[1]+1)->call();
    (*z+3)->call();
    This piece of code produces
    size of A: 4
    A()
    A()
    A()
    A()
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    ~A()
    ~A()
    ~A()
    ~A()
    4 times constructor was called, 4 times destructor, no calls of operator new.
  • The second, a bit more complex.
    Allocate memory for 2x2 array of A in the heap.
    cout << "size of A: " << sizeof(A) << "\n";
    A (*z)[2] = new A[2][2];
    z[1][1].call();
    (z[1]+1)->call();
    (*z+3)->call();
    delete [] z;
    The output should be
    size of A: 4
    new[], size: 20
    A()
    A()
    A()
    A()
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    ~A()
    ~A()
    ~A()
    ~A()
    
    4 times constructor was called, 4 times destructor, 1 call of operator new[] to allocate memory for all 4 objects.
  • The next method is used to allocate memory in the heap for one-dimension array of size 2 of pointers to A. Then allocate memory for one-dimension 'sub-arrays'.
    cout << "size of A: " << sizeof(A) << "\n";
    A **z = new A*[2];
    z[0] = new A[2];
    z[1] = new A[2];
    
    z[1][1].call();
    (z[1]+1)->call();
    (*z+3)->call();
    
    delete [] z[0];
    delete [] z[1];
    delete [] z;
    size of A: 4
    new[], size: 12
    A()
    A()
    new[], size: 12
    A()
    A()
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    ~A()
    ~A()
    ~A()
    ~A()
    2 times constructor was called after each call to operator new[] to allocate memory for 2 objects, 4 times destructor was called
  • This method is tricky a little bit. We allocate one-dimension array of size 4. Using pointer arithmetics we can simulate two-dimension array.
    cout << "size of A: " << sizeof(A) << "\n";
    A *z = new A[2*2];
    z[2+1].call();
    (z+3)->call();
    delete [] z;
    size of A: 4
    new[], size: 20
    A()
    A()
    A()
    A()
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    ~A()
    ~A()
    ~A()
    ~A()
    
  • 4 times constructor was called, 4 times destructor, 1 call of operator new[] to allocate memory for all 4 objects.
  • This one is a combination of storing 2x2 array in the heap and in the stack. At first one-dimension array of pointers to A is put onto the stack and later memory from heap is used to allocate one-dimension 'sub-arrays'.
    cout << "size of A: " << sizeof(A) << "\n";
    A *z[2];
    z[0] = new A[2];
    z[1] = new A[2];
    
    z[1][1].call();
    (z[1]+1)->call();
    (*z+3)->call();
    
    delete [] z[0];
    delete [] z[1];
    size of A: 4
    new[], size: 12
    A()
    A()
    new[], size: 12
    A()
    A()
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    id #4, 4 times constructor of A was called
    ~A()
    ~A()
    ~A()
    ~A()
    
    2 times constructor was called after each call to operator new[] to allocate memory for 2 objects, 4 times destructor was called
All methods have their '+'s and '-'s. One can take more time but require less memory and the other one can take more memory but could be executed faster. That depends how many calls have been done to allocate memory, where memory was taken to allocate an array, etc. Also you should remember c++ restriction for arrays on the stack that their size must be known during the compile time. The dark side of memory from the heap is that it should be explicitly released when it become unused. Some of them are more expressive for understanding some of them not.
This is upon you.

No comments: