CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 15
  1. #1
    Join Date
    Apr 2009
    Location
    Netherlands
    Posts
    91

    [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?

  2. #2
    Join Date
    Oct 2002
    Location
    Austria
    Posts
    1,284

    Re: Question regarding the use of a 2 dimensional array

    Quote Originally Posted by AlastrionaAdair View Post
    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.

  3. #3
    Join Date
    Apr 2009
    Location
    Netherlands
    Posts
    91

    Re: Question regarding the use of a 2 dimensional array

    Quote Originally Posted by ZuK View Post
    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.

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    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.

  5. #5
    Join Date
    Apr 2009
    Location
    Netherlands
    Posts
    91

    Re: Question regarding the use of a 2 dimensional array

    Quote Originally Posted by Lindley View Post
    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?

  6. #6
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    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))
    {}

  7. #7
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Question regarding the use of a 2 dimensional array

    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%.
    Last edited by superbonzo; April 18th, 2009 at 01:55 PM. Reason: added Corrigendum

  8. #8
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    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?

  9. #9
    Join Date
    Apr 2009
    Location
    Russia, Nizhny Novgorod
    Posts
    99

    Re: Question regarding the use of a 2 dimensional array

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

  10. #10
    Join Date
    Oct 2008
    Posts
    1,456

    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

  11. #11
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Question regarding the use of a 2 dimensional array

    Quote Originally Posted by superbonzo View Post
    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

  12. #12
    Join Date
    Apr 2009
    Location
    Russia, Nizhny Novgorod
    Posts
    99

    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

  13. #13
    Join Date
    Aug 2007
    Posts
    858

    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).

  14. #14
    Join Date
    Oct 2008
    Posts
    1,456

    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.

  15. #15
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Question regarding the use of a 2 dimensional array

    Quote Originally Posted by superbonzo View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured