Sign in to follow this  
PureSnowX

Dynamic 2-D array de-allocation input.

Recommended Posts

PureSnowX    275
Hello all, I have been tinkering with a small game and decided to make a tile-map system that supports maps of different sizes seeing as the tutorials out there are all using a constant size for every map.

The solution would be a dynamic allocated array with the correct map size for the loaded map, this was not the easiest thing to make sure it was memory safe.

I think I'm de-allocating the memory right but I want to make sure that is the case seeing as I'm a tad confused by the pointer-to-pointer-to-value concept. Also I'm not sure but if someone knows if a can move the "listed initialization" into the .cpp file of the class instead of having code inside the header file since I'm trying to avoid it.

Here is the code anyways for allocation inside the constructor inside the .hpp/h file:
[CODE]
class Map
{
public:
Map(int width, int height): MAP_WIDTH(width), MAP_HEIGHT(height) {
tiles = new int*[MAP_HEIGHT];
for(int i = 0; i < MAP_HEIGHT; i++)
tiles[i] = new int[MAP_WIDTH];
for(int y = 0; y < MAP_HEIGHT; y++)
{
for(int x = 0; x < MAP_WIDTH; x++)
{
tiles[y][x] = 0;
}
}
};
~Map();
private:
int** tiles;
const int MAP_WIDTH;
const int MAP_HEIGHT;
};
[/CODE]

and here is the code for de-allocation inside the .cpp:
[CODE]
Map::~Map()
{
for(int i = 0; i < MAP_HEIGHT; i++)
delete [] tiles[i];
delete [] tiles;
}
[/CODE]

Share this post


Link to post
Share on other sites
Cornstalks    7030
I'd probably be using [font=courier new,courier,monospace]std::vector[/font] or something like that, but yes, what you have is correct.*

That semicolon after the [font=courier new,courier,monospace]}[/font] at the end of the definition of the Map constructor is unnecessary. To move the constructor's code to the .cpp you just... move it just like you've got the destructor (i.e. put [font=courier new,courier,monospace]Map(int width, int height);[/font] in the header and the just copy 'n' paste the constructor into the .cpp (prefixing it with [font=courier new,courier,monospace]Map::[/font] of course)).

[size=2]*I say correct because there isn't anything immediately wrong with it, however it's not [i]totally[/i] correct. The reason is that you allocate memory in the constructor several times. If one of the allocations succeeds, and then one fails after it and a std::bad_alloc exception is thrown, the allocated memory will be leaked because it will never be deleted (the destructor will not be called if the constructor fails and throws an exception). That's why it's nice to use something like std::vector that automatically and safely handles the ugliness of directly dealing with allocating and deallocating memory.[/size] Edited by Cornstalks

Share this post


Link to post
Share on other sites
As Cornstalks said, it's correct.

I would just add that you can initialize everyting to zero with memset, rather than looping through everything:

[source lang="cpp"]for (int i = 0; i < MAP_HEIGHT; ++i){
tiles[i] = new int[MAP_WIDTH];
memset(tiles[i], 0, sizeof(int) * MAP_WIDTH); // initialize each tile to 0
}[/source] Edited by Goran Milovanovic

Share this post


Link to post
Share on other sites
Cornstalks    7030
[quote name='Goran Milovanovic' timestamp='1341178965' post='4954662']
I would just add that you can initialize everyting to zero with memset, rather than looping through everything:
[/quote]
That's a good point, but it's the C way of doing things. C++ would use [url="http://www.cplusplus.com/reference/algorithm/fill/"]std::fill[/url] (or [url="http://www.cplusplus.com/reference/algorithm/fill_n/"]std::fill_n[/url]).

But again, if I was using [font=courier new,courier,monospace]std::vector[/font], I'd let the constructor do it for me.

Share this post


Link to post
Share on other sites
PureSnowX    275
So how would this look like with an std::vector<T>?
Someone care to elaborate and maybe change my code above fitted for an std::vector<T>?
It would help tons and be visual enough for me to follow :)

Share this post


Link to post
Share on other sites
rip-off    10976
You could have a vector of vectors:
[code]
class Map
{
public:
Map(int width, int height): width(width) {
std::vector<int> row(width, 0);
tiles.resize(height, row);
}

// Not required for current implementation.
// ~Map();
private:
int width;

// Can be derived from tiles.size()
// int height

// The space between the two angle brackets here might be required on older compilers.
std::vector<std::vector<int> > tiles;
};

[/code]

It would be better to use a dedicated 2D storage class for this, unless you want to support jagged rows. You could use boost::multi_array, though I find it is unwieldy (maybe too general purpose), so I tend to provide my own simpler version as a wrapper around std::vector.

Something like the following:
[code]
template<class T>
class array2d
{
public:
array2d(unsigned w, unsigned h, const T &t = T())
:
storage(w * h, t),
width_(w)
{
}

unsigned width() const { return width_; }
unsigned height() const { return storage.size() / width_; }

T &operator()(unsigned x, unsigned y)
{
return storage[index(x,y)];
}

const T &operator()(unsigned x, unsigned y) const
{
return storage[index(x,y)]);
}

private:
std::vector<T> storage;
unsigned width_;

unsigned index(unsigned x, unsigned y) const
{
return (y * width_) + x;
}
};
[/code]
The index() helper function uses the same maths the compiler does when you use a raw multi-dimensional array.

The map becomes:
[code]
class Map
{
public:
Map(int width, int height)
:
tiles(width, height, 0)
{
}

// Not required for current implementation.
// ~Map();
private:
// Can be derived from tiles.width()
// int width;

// Can be derived from tiles.height()
// int height

array_2d<int> tiles
};
[/code] Edited by rip-off

Share this post


Link to post
Share on other sites
PureSnowX    275
Vector of a vector seems to work fine, but I have some questions.
But do I access the elements with vector[x][y] or vector[y][x]?

Testing the case it seems I'm accessing the elements of the 2D matrix this way:
vector[y][x], it's a bit odd using reversed access coordinates how would I go about changing that?

EDIT:
What I'm trying to say is that when using the 2D Vector code above the coordinates which to access the elements is now reversed, this feels a bit odd and how would I go about changing this so I'm accessing it using the (x,y) instead of (y,x) as coordinates? Edited by Moonkis

Share this post


Link to post
Share on other sites
rip-off    10976
Accessing x,y vs y,x is a an arbitrary convention. Just like row major and column major. The main thing is to choose complementary conventions, otherwise you'll incur lots of unnecessary cache misses. The processor likes sequential access.

So if you are storing the data as [i, j], then you should loop for(i ...) { for(j ...) { /* ... */ } }, regardless of which dimensions you are mapping onto i and j.

Share this post


Link to post
Share on other sites
PureSnowX    275
[quote name='rip-off' timestamp='1341234455' post='4954890']
Accessing x,y vs y,x is a an arbitrary convention. Just like row major and column major. The main thing is to choose complementary conventions, otherwise you'll incur lots of unnecessary cache misses. The processor likes sequential access.

So if you are storing the data as [i, j], then you should loop for(i ...) { for(j ...) { /* ... */ } }, regardless of which dimensions you are mapping onto i and j.
[/quote]
Wow that is a lot of fancy English words.
So basically this piece of code has nothing to do with in which order I access my data?
[CODE]
Map::Map(int width, int height): MAP_WIDTH(width), MAP_HEIGHT(height)
{
std::vector<int> row(MAP_WIDTH, 0);
backgroundLayer.resize(MAP_HEIGHT, row);
}
[/CODE]

So if I'd like to access my elements in x,y order then the loop should be:
[CODE]
for(int x = 0; x < MAP_WIDTH; x++)
{
for(int y = 0; y < MAP_HEIGHT; y++)
{
std::cout << backgroundLayer[x][y] << std::endl;
}
}
[/CODE]

Have I gotten this correct or did I understand it wrong?

EDIT:
[quote][color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif][size=3][left][background=rgb(250, 251, 252)][b]arbitrary convention[/b]. Just like [b]row major and column major[/b]. The main thing is to choose [b]complementary conventions[/b], otherwise [b]you'll incur lots of unnecessary cache misses. The processor likes sequential access.[/b][/background][/left][/size][/font][/color]
[/quote]
Maybe you could explain the bolded parts a bit further in simpler English? Just so that I know for future references Edited by Moonkis

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this