[RESOLVED] Question regarding the use of a 2 dimensional array

For a game I'm working on I want my terrain to be represented by a 2-d array of TerrainSquare objects. I first started looking at boost::multi_array, but I found the syntax to be somewhat confusing and I also heard it isn't too fast in comparison with a regular 2-d array.

I realised I didn't really need to be able to resize. However I needed to array size to be defined at runtime by means of a constructor. I came across an example of how to do this using a double pointer and I came to the following implmentation:

Code:

---

Terrain.h

#include "TerrainSquare.h"

class Terrain
{
public:
        Terrain(int x, int y);
        ~Terrain(void);       
        TerrainSquare **terrainArray;

};

---

Code:

---

Terrain.cpp

#include "Terrain.h"

Terrain::Terrain(int x, int y)
{       
        terrainArray = new TerrainSquare*[x];
        for (int i=0; i<x; i++)
        {
                terrainArray[i] = new TerrainSquare[y];
        }
}

Terrain::~Terrain()
{
        delete this->terrainArray;
}

---

Code:

---

TerrainSquare.h

class TerrainSquare
{
public:
        TerrainSquare();
        TerrainSquare(int type);
        ~TerrainSquare(void);

        int type;
};

---

Code:

---

TerrainSquare.cpp

#include "TerrainSquare.h"

TerrainSquare::TerrainSquare()
{
        this->type = 0;
}
TerrainSquare::TerrainSquare(int type)
{
        this->type = type;
}
TerrainSquare::~TerrainSquare(void)
{
}

---

My questions are:

1./ Is this a good way to implement a 2-d array for my purposes. I must tell you that this array will be read alot (every render cycle, to draw the terrain), so the access speed is probably the most important aspect.

The data will also frequently be modified, ie. a fire in the game could change the terrain type from forest to wasteland.

2./ Am I deleting the 2-d array in the proper way in the destructor of the Terrain class?

Quote:

---

Originally Posted by AlastrionaAdair

2./[/B] Am I deleting the 2-d array in the proper way in the destructor of the Terrain class?

---

No. It should be

Code:

---

Terrain::~Terrain() {
        for (int i=0; i<x; i++)  // you have to store x and y as class members
                delete [] terrainArray[i];
        delete [] terrainArray;
}

---

Kurt

Quote:

---

Originally Posted by ZuK

No. It should be

Code:

---

Terrain::~Terrain() {
        for (int i=0; i<x; i++)  // you have to store x and y as class members
                delete [] terrainArray[i];
        delete [] terrainArray;
}

---

Kurt

---

Thanks, I had a feeling this wouldn't free all the memory. Storing x and y as class members isn't a problem. I was probably going to do that anyway since when I draw the terrain I will need to know how many times I have to loop. That way i can just ask for terrain->x and terrain->y.

You should also either (a) make the class uncopyable by declaring operator= and the copy constructor as private, or else (b) implement those two functions (carefully!).

To make life a little easier, consider adding two private members

Code:

---

std::vector<TerrainSquare> terrainArray_data;
std::vector<TerrainSquare*> terrainArray;

---

and then doing in the constructor,

Code:

---

Terrain::Terrain(int x, int y): terrainArray(x), terrainArray_data(x*y)
{       
        for (int i=0; i<x; i++)
        {
                terrainArray[i] = &terrainArray_data[i*x];
        }
}

---

That way, you won't have to worry about copy semantics *or* the destructor----all that will be handled automatically by the vector class.

Note, the above assumes that you want to access the 2D array as terrainArray[x][y]. A lot of programs use the convention of indexing first into y and *then* into x instead. Use either one, just make sure you're clear about which it is and stick with it.

Quote:

---

Originally Posted by Lindley

You should also either (a) make the class uncopyable by declaring operator= and the copy constructor as private, or else (b) implement those two functions (carefully!).

---

I assume thats because copying would mean I'm just copying pointers which continue to point to the same adress in memory?

Either way, I'm not sure if I ever need to copy. I'll think about it and choose depeding on the need for copying.

Quote:

---

To make life a little easier, consider adding two private members

Code:

---

std::vector<TerrainSquare> terrainArray_data;
std::vector<TerrainSquare*> terrainArray;

---

and then doing in the constructor,

Code:

---

Terrain::Terrain(int x, int y): terrainArray(x), terrainArray_data(x*y)
{       
        for (int i=0; i<x; i++)
        {
                terrainArray[i] = &terrainArray_data[i*x];
        }
}

---

That way, you won't have to worry about copy semantics *or* the destructor----all that will be handled automatically by the vector class.

Note, the above assumes that you want to access the 2D array as terrainArray[x][y]. A lot of programs use the convention of indexing first into y and *then* into x instead. Use either one, just make sure you're clear about which it is and stick with it.

---

Do I get it right when I think you are describing is the same solution but then with vectors instead of a standard array? That would give the added benefits of the functionality of the vector, althought I find the construction slightly more confusing.

Is there any significant speed difference between an array and a vector in my case? From what I know a vector is just an array with some added functionality, so it shouldn't give any perfomance hit if you use it like an array right? Or are there additional function calls involved in using a vector?

If you don't intend to resize the 2D array, then there shouldn't be any significant difference between using a vector or an array except for the automatic copying and cleanup. You should look at the vector documentation to see what's available, though:
http://www.cppreference.com/wiki/stl/vector/start

The reason the construction seems slightly more complicated is because I elected to allocate the entire 2D array as one contiguous block and index the rows into it, rather than allocating each row separately. It's a bit more efficient, but it doesn't allow easy resizing.

If I were to copy precisely the same logic you used in vector form, it would simply look like

Code:

---

std::vector< std::vector<TerrainSquare> > terrainArray;
...
Terrain::Terrain(int x, int y): terrainArray(x, std::vector<TerrainSquare>(y))
{}

---

Quote:

---

Originally Posted by AlastrionaAdair

Is there any significant speed difference between an array and a vector in my case? From what I know a vector is just an array with some added functionality, so it shouldn't give any perfomance hit if you use it like an array right?

---

in order to give you a (very) rough estimate of the performance hit of the vector abstraction (and also for personal curiosity :)) consider the following simple code

Code:

---

#include <iostream>
#include <vector>
#include <ctime>
#include <cmath>

int f(int x) { /*...*/ }

int main()
{
        const int                num = 1024, runs = 1000000;
        std::vector<int>        vec( num );
        int*                        arr = new int[ num ];

        // counters
        int                                c,j;
        int*                                pc;
        std::vector<int>::iterator        ic;
        clock_t                                start;

        start = clock();
                for(j=0;j<runs;++j) for(c=0;c<num;++c) arr[c] = f(c);
        std::cout << ( clock() - start ) << std::endl;

        start = clock();
                for(j=0;j<runs;++j) for(c=0;c<num;++c) vec[c] = f(c);
        std::cout << ( clock() - start ) << std::endl;

        start = clock();
                for(j=0;j<runs;++j) for(c=0,pc=arr;c<num;++c,++pc) *pc = f(c);
        std::cout << ( clock() - start ) << std::endl;

        start = clock();
                for(j=0;j<runs;++j) for(c=0,ic=vec.begin();ic!=vec.end();++c,++ic) *ic = f(c);
        std::cout << ( clock() - start ) << std::endl;

        delete[]arr;

        return 0;
}

---

where I considered 4 ways to itarate an array-like structure; here are the results varing the 'f' function:

<EDIT: Corrigendum>
the following results are invalid, since checked iterators are turned on; see the posts below.
the correct results show no difference or even better performance in the vector case
</EDIT>

Code:

---

int f(int x);                                vector[]        array it        vector it

identity                                [347,380]        [187,194]        [1799,1834]
square x*x                                [121,137]        [100,102]        [708,725]
cube x*x*x                                [173,187]        [123,123]        [929,947]
polynomial 2+3*x+2*x*x+5*x*x*x                [163,163]        [108,109]        [476,491]
float sin                                [101,105]        [100,103]        [106,114]
float exp                                [100,107]        [100,103]        [102,104]

---

where [a,b] are respectively the minimum and the maximum percentage timing relative to the [] array iteration.

as you can see, when the operation inside the loop has a timing comparable to the iteration itself the impact of vector abstraction can vary from 10&#37;-100% in the []-case to 100%-1000% in the iterator case (off course, this heavily depends on comiler/system).
Otherwise (see the sin and exp rows) the impact becomes more and more negligible. Even for a 'simple' float exponential the impact is less then 1%.

Those numbers look strange to me. Is that fully optimized and run independent of an IDE?

superbonzo, your results are very strange. What the compiler did you use?

Quote:

---

Those numbers look strange to me. Is that fully optimized and run independent of an IDE?

---

I admit that I've also been surprised of the results (by the way, this is not intended as a rigourous treatment of the problem ...) but the answer to your questions is yes ( the only optimization "disabled" is "favor size or speed = neither", but the main optimization option is set to "Maximize Speed" ... and it's run from the console).

Anyway, remember that those are relative timings ...

what are the results of your system/compiler ? (if you have time and will, off course :) )

ps.: the compiler is VC++2008
pps.: the "runs" constant in the code is not fixed with the respect to "f" and it has to be choosen in order of minimizing the sampling error and the sublinear timing terms...

Quote:

---

Originally Posted by superbonzo

I admit that I've also been surprised of the results

---

Did you specify _SECURE_SCL=0 in the preprocessor?

The reason this is important is that by default, Visual C++ happens to check iterators on release builds. To turn this off, you have to specify the _SECURE_SCL=0 preprocessor constant.

So your results are not valid unless you have that switch set and rebuild your application.

Regards,

Paul McKenzie

try compiling with #define _SECURE_SCL 0 and then watching the results
upd: I'm late :)

Indeed, with checked iterators turned off you'll find that vectors have essentially the same access speed as raw arrays. In fact, running your test program I'm actually getting more than a few results where the vector is faster than the raw array (albeit only by a percent or two).

Quote:

---

The reason this is important is that by default, Visual C++ happens to check iterators on release builds.

---

I didn't know that ! :eek: what evil mind decided to make iterator checks on by default on release ?

Quote:

---

In fact, running your test program I'm actually getting more than a few results where the vector is faster than the raw array

---

yes, and in the f() = x*x case the vector iterator loop results roughly twice as faster... I'll add a corrigendum in my post.

Quote:

---

Originally Posted by superbonzo

I didn't know that ! :eek: what evil mind decided to make iterator checks on by default on release ?

---

Surprised, no? Some programmers wanted to strangle (figuratively, of course) Microsoft for that decision.

Regards,

Paul McKenzie