Dynamic 2D and 3D arrays with "[]" interface (C++)

[arras]

Simple dynamic 2d and 3d arrays which can be created on runtime and accessed like ordinary arrays:

Code: Select all

// simple dynamic 2d and 3d arrays which can be created on runtime and accessed
// like ordinary arrays

// author: Michal Švantner
// date: 4.3.2007
// license: you are free to use this code on your own risk :)

/*------------------------------ example code ----------------------------------

array2d<int> my2darray(10,5);
my2darray[1][3] = -2;
my2darray[2][5] = 240;

array3d<float> my3darray(2,12,3);
my3darray[0][9][0] = 0.456f;
my3darray[1][1][3] = -24.4f;

------------------------------------------------------------------------------*/

#ifndef DYNAMICARRAYS_H
#define DYNAMICARRAYS_H

template <class T> struct arrayData
{
    T* data;
    T& operator [](int index) {return data[index];}
};

template <class T> struct arrayData2d
{
    arrayData<T>* data;
    arrayData<T>& operator [](int index) {return data[index];}
};

// dynamic two dimensional array
template <class T> class array2d
{
    arrayData<T>* data;
    int w, h;

public:
    array2d(int iwidth, int iheight) : w(iwidth), h(iheight)
    {
        data = new arrayData<T>[w];
        for(int i=0; i<w; i++) data[i].data = new T[h];
    }
    
    ~array2d()
    {
        for(int i=0; i<w; i++) delete [] data[i].data;
        delete [] data;
    }
    
    arrayData<T>& operator [](int index) {return data[index];}
    
    int width() {return w;}
    
    int height() {return h;}
};

// dynamic three dimensional array
template <class T> class array3d
{
    arrayData2d<T>* data;
    int w, h, d;

public:
    array3d(int iwidth, int iheight, int idepth) : w(iwidth), h(iheight), d(idepth)
    {
        data = new arrayData2d<T>[w];
        for(int i=0; i<w; i++) data[i].data = new arrayData<T>[h];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++) data[i][j].data = new T[d];
    }
    
    ~array3d()
    {
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++) delete [] data[i][j].data;
        for(int i=0; i<w; i++) delete [] data[i].data;
        delete [] data;
    }
    
    arrayData2d<T>& operator [](int index) {return data[index];}
    
    int width() {return w;}
    
    int height() {return h;}
    
    int depth() {return d;}
};
#endif

download at http://members.lycos.co.uk/arras1/downl ... icarrays.h or find it on my page.

Please report any problems you would find.

[BlindSide]

This looks useful, can you please explain benefit over irrlicht's arrays?

Thank you

[arras]

It is similar to Irrlicht corre::array in that it allocate memory dynamicly and in [] interface so you can use it as ordinary array.

core::array is however much more complex, in fact it is kind of kontainer. In my array2d and array3d you canot realocate memory once object is created. You have to stick with size you defined at the begining.

Benefit ower core::array is that while core::array is only one dimensional array2d and array3d are 2 and 3 dimensional.

I ofthen used C like dynamic 2d and 3d arrays like:

Code: Select all

SomeClass** array;
array = new SomeClass*[sizeX];
for(int i=0; i<sizeX; i++) array[i] = SomeClass[sizeY];
...
// than you may use it like ordinary array:
array[x][y].somefunction();
...
// and than at the end or in destructor:
for(int i=0; i<sizeX; i++) delete [] array[i];
delete [] array;

I was using this kind of code ofthen in classes where user can define size of array at creation of object. For example my terrain class use this kind of array for indexing tiles. In my space flight demo I needed dinamic 3d array to represent field of debrees flying around ship.

my aray2d and array3d puts this C code in to C++ classes while keeping array like [][] interface. This was bit tricky to code since to overload operator [] is simple as core::array do. But you cant overload this operator in [][] or [][][] way so I needed to find some workaround.

So basicly array2d and array3d are C code build in C++ class where object asure proper inicialization and cleanup of memory on destruction. It also keep track of its size. And finaly unlike C code it can be initialized on single line like you would do with ordinary array.

[Klasker]

This will fragment the memory, and it has to follow three pointers to find an entry. I always use the operator() instead, and keep the memory in one big chunk.

Have you tested the destructors properly? I think the destructor for array3d will crash, because it deletes the 1D arrays, and then the array2d destructor tries to delete the same 1D arrays again.

[arras]

Here is test I did before I was posting code here in order to find out if destructor works:

Code: Select all

#include<iostream>
using namespace std;

#include"dynamicarrays.h"

struct A
{
    int i;
    A(){i = -1; cout << "create" << endl;}
    ~A(){cout << "delete " << i << endl;}
};

int main()
{
    {
    array3d<A> a(2,2,2);
    
    int n = 1;
    for(int k=0; k<a.depth(); k++)
        for(int j=0; j<a.height(); j++)
            for(int i=0; i<a.width(); i++)
                {a[i][j][k].i = n; n++;}
    
    for(int k=0; k<a.depth(); k++)
    {
        for(int j=0; j<a.height(); j++)
        {
            cout << "[";
            for(int i=0; i<a.width(); i++) cout << a[i][j][k].i << " ";
            cout << "] ";
        }
        cout << endl;
    }
    }
    
    while(1);
    return 1;
}

If you find something wrong please post it here.

In order to keep memory in one piece you would need to calculate 1 dimensional index out of 2D or 3D index. I think that gona be much slower than to use 2-3 pointers.

True you gona end with fragmented memory but that is true for original C code as well so I don't see any disadvantages.

[edit] btw: array3d doesnt use array2d, it use structure arrayData2d which doesnt have destructor, thats why destructor is not going to crash.

[Klasker]

[edit] btw: array3d doesnt use array2d, it use structure arrayData2d which doesnt have destructor, thats why destructor is not going to crash.

Ahh, an oversight on my behalf.

In order to keep memory in one piece you would need to calculate 1 dimensional index out of 2D or 3D index. I think that gona be much slower than to use 2-3 pointers.

True you gona end with fragmented memory but that is true for original C code as well so I don't see any disadvantages.

I don't agree, but anyways I'm just saying that you are introducing overhead so you can cheat the compiler to let you use the [] operator instead of (). In the end it is just as easy to use the () operator.

[arras]

I don't agree,

in case of 2d array to calculate single index you would need to use: index = indexY * sizeX + indexX ...you think it is faster than going through 2 pointers?

folowing code is going to fragment memory as wel:

Code: Select all

SomeClass** array;
array = new SomeClass*[sizeX];
for(int i=0; i<sizeX; i++) array[i] = SomeClass[sizeY];

you firsth create array of pointers then alocate memory one by one. I dont see principal diference.

I'm just saying that you are introducing overhead so you can cheat the compiler to let you use the [] operator instead of ().

yes you are right but operator overloading is there to make our code to be more readable and easier to understand and use. C++ is "language" afther all. Instead of something == somethingelse you may use something.findIfEqual(somethingelse) but the firsth one just look much more convenient.

Please don't think I am trying to defent my code at all cost ...I just want to find out if you are true ...your critique is welcomed.

[arras]

I did some speed testing to compare diferent 2d arrays:
1. my array2d with [][] interface
2. dynamic 2d array with single chunk of memory and () interface
3. C like dynamic 2d array with () interface
4. normal static 2d array as reference

results on my computer:
1. 94 seconds
2. 80 seconds
3. 74 seconds
4. 63 seconds

So conclusion is that your "single block of memory" aproach is fasther than my array2d but slower than C like dynamic array of 2 pointers. So what makes diference is my "nice" interface rather then number of pointers.
Static array was of course fasthest of all.

testing included diferent 2d arrays of 100x100 size and repeatedly going through each element for seweral loops:

Code: Select all

#include <stdlib.h>
#include <time.h>
#include<iostream>
using namespace std;

#include"dynamicarrays.h"

// dynamic 2d array with single block of memory
template <class T> class altarray2d
{
    T* data;
    int w, h;
    
public:
    altarray2d(int iwidth, int iheight) : w(iwidth), h(iheight)
    {
        data = new T[w*h];
    }
    
    ~altarray2d()
    {
        delete [] data;
    }
    
    T& operator ()(int index1, int index2)
    {
        return data[index2*w+index1];
    }
    
    int width() {return w;}
    
    int height() {return h;}
};

// dynamic C like 2d array
template <class T> class alt2array2d
{
    T** data;
    int w, h;
    
public:
    alt2array2d(int iwidth, int iheight) : w(iwidth), h(iheight)
    {
        data = new T*[w];
        for(int i=0; i<w; i++) data[i] = new T[h];
    }
    
    ~alt2array2d()
    {
        for(int i=0; i<w; i++) delete data[i];
        delete [] data;
    }
    
    T& operator ()(int index1, int index2)
    {
        return data[index1][index2];
    }
    
    int width() {return w;}
    
    int height() {return h;}
};

int main()
{
    int loopcount = 500000;
    
    unsigned int t1;
    unsigned int t2;
    
    time_t seconds;
    
    // my array2d
    array2d<int> a(100,100);
    // dynamic 2d array with single block of memory
    altarray2d<int> b(100,100);
    // dynamic C like 2d array
    alt2array2d<int> c(100,100);
    // normal static array
    int d[100][100];
    
    cout << "running test 1 please wait..." << endl;

    time(&seconds);
    t1 = (unsigned int) seconds;
    
    for(int n=0; n<loopcount; n++)
        for(int j=0; j<a.height(); j++)
            for(int i=0; i<a.width(); i++) a[i][j] = n;
            
        
    time(&seconds);
    t2 = (unsigned int) seconds;
    
    cout << "test 1 lasted " << t2-t1 << " seconds" << endl;
    
    cout << "running test 2 please wait..." << endl;
    
    time(&seconds);
    t1 = (unsigned int) seconds;
    
    for(int n=0; n<loopcount; n++)
        for(int j=0; j<a.height(); j++)
            for(int i=0; i<a.width(); i++) b(i,j) = n;
            
        
    time(&seconds);
    t2 = (unsigned int) seconds;
    
    cout << "test 2 lasted " << t2-t1 << " seconds" << endl;
    
    cout << "running test 3 please wait..." << endl;
    
    time(&seconds);
    t1 = (unsigned int) seconds;
    
    for(int n=0; n<loopcount; n++)
        for(int j=0; j<a.height(); j++)
            for(int i=0; i<a.width(); i++) c(i,j) = n;
            
        
    time(&seconds);
    t2 = (unsigned int) seconds;
    
    cout << "test 3 lasted " << t2-t1 << " seconds" << endl;
    
    cout << "running test 4 please wait..." << endl;
    
    time(&seconds);
    t1 = (unsigned int) seconds;
    
    for(int n=0; n<loopcount; n++)
        for(int j=0; j<a.height(); j++)
            for(int i=0; i<a.width(); i++) d[i][j] = n;
            
        
    time(&seconds);
    t2 = (unsigned int) seconds;
    
    cout << "test 4 lasted " << t2-t1 << " seconds" << endl;
    
    while(1);
    return 1;
}