-
April 17th, 2009, 01:16 PM
#1
[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?
-
April 17th, 2009, 04:20 PM
#2
Re: Question regarding the use of a 2 dimensional array
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
Last edited by ZuK; April 17th, 2009 at 04:23 PM.
-
April 17th, 2009, 05:15 PM
#3
Re: Question regarding the use of a 2 dimensional array
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.
-
April 17th, 2009, 06:01 PM
#4
Re: Question regarding the use of a 2 dimensional array
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.
-
April 17th, 2009, 10:12 PM
#5
Re: Question regarding the use of a 2 dimensional array
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.
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?
-
April 17th, 2009, 11:37 PM
#6
Re: Question regarding the use of a 2 dimensional array
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))
{}
-
April 18th, 2009, 11:32 AM
#7
Re: Question regarding the use of a 2 dimensional array
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%-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%.
Last edited by superbonzo; April 18th, 2009 at 01:55 PM.
Reason: added Corrigendum
-
April 18th, 2009, 12:26 PM
#8
Re: Question regarding the use of a 2 dimensional array
Those numbers look strange to me. Is that fully optimized and run independent of an IDE?
-
April 18th, 2009, 12:36 PM
#9
Re: Question regarding the use of a 2 dimensional array
superbonzo, your results are very strange. What the compiler did you use?
-
April 18th, 2009, 12:42 PM
#10
Re: Question regarding the use of a 2 dimensional array
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...
Last edited by superbonzo; April 18th, 2009 at 12:47 PM.
Reason: added pps
-
April 18th, 2009, 01:24 PM
#11
Re: Question regarding the use of a 2 dimensional array
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
-
April 18th, 2009, 01:26 PM
#12
Re: Question regarding the use of a 2 dimensional array
try compiling with #define _SECURE_SCL 0 and then watching the results
upd: I'm late
-
April 18th, 2009, 01:43 PM
#13
Re: Question regarding the use of a 2 dimensional array
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).
-
April 18th, 2009, 01:50 PM
#14
Re: Question regarding the use of a 2 dimensional array
The reason this is important is that by default, Visual C++ happens to check iterators on release builds.
I didn't know that ! what evil mind decided to make iterator checks on by default on release ?
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.
-
April 18th, 2009, 02:09 PM
#15
Re: Question regarding the use of a 2 dimensional array
Originally Posted by superbonzo
I didn't know that ! 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
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|