Sign in to follow this  
Arreis

Using vectors in C++

Recommended Posts

Hi everyone, newbie game programmer here. As many people before me, I'm starting from the bottom, I already finished the obligatory Tetris(tm) and just moved to the Arkanoid clone, but I'm puzzled about something. Thought you might be able to help me ;) OK, first, I'm using SDL with C++. That being said, in my screen there are a ship, a ball, and a group of blocks. The blocks are stored like this:
std::vector<Block> blocks;
Block *temp;
for (int i = 0; i < LINES_PER_LEVEL; i++)
{
  for (int j = 0; j < BLOCKS_PER_LINE;  j++)
  {
    temp = new Block(...);
    blocks.push_back(*temp);
  }
}
Each block has a draw() method which uses standard SDL functions to blit an image on screen. It works perfectly... until I destroy a block.
int Game::logic()
{
  (...) // This code moves the ball and the ship

  static int blockToDelete = -1;
  for (int i = 0; i < blocks.size(); i++)
  {
    // getCollBox returns an SDLRect with the collsion box dimensions,
    // and checkCollision returns true if the boxes overlap
    if (checkCollision(ball->getCollBox(), blocks.at(i).getCollBox()))
    {
      blockToDelete = i;
    }
  }
  if (blockToDelete != -1)
  {
    blocks.erase(blocks.begin() + blockToDelete);
    blockToDelete = -1;
  }
}
I know, there are better ways to do this, but I prefer to do the optimising once everything works to an acceptable degree. The thing is, every frame, I do the previous logic, then draw the screen like this:
for (int i = 0; i < blocks.size(); i++)
{
  blocks.at(i).draw();
}
(...) // Draw ship and ball
but, for some reason, as soon as a block is destroyed, the program exits. I ran some checks, and the program ends when trying to draw the last block of the vector. Say I have 10 blocks, numbered from 0 to 9, and that I destroy block 5. The program draws blocks 0, 1, 2, 3, 4, 6, 7, 8, and exits when drawing block 9. If I change the code to never draw the last block, it doesn't exit, but starts behaving erratically after the first collision (music stops, doesn't exit, feels similar to entering an infinite loop, but the ship still moves). The draw() method just calls SDL_BlitSurface() with appropiate arguments, that's all. I know I'm being kind of vague here, but after a weekend of thinking this code over and over, I just don't know what could be wrong. Maybe I missed something completely obvious, maybe not. If you guys could help me with this, I'd really appreciate it. Also, if you need any other part of the code, just ask. Thanks in advance, everyone.

Share this post


Link to post
Share on other sites
The STL uses non-pointer types; if you want a container of pointers use boost::ptr_vector<Block> or std::vector<boost::shared_ptr<Block>>. You can have a std::vector<Block*>, but it won't delete them for you.

A few notes:

std::vector<Block> blocks;
for (int i = 0; i < LINES_PER_LEVEL; i++)
{
for (int j = 0; j < BLOCKS_PER_LINE; j++)
{
// temp = new Block(...); // Allocate a Block
// blocks.push_back(*temp); // Push a copy of the Block pointed by temp onto "blocks"

// The location of the allocated memory for temp will be overwritten (forgotten) on the next iteration of this loop

blocks.push_back( Block( ... ) ); // Push a copy of a temporary object onto "blocks"
}
}



Then to iterate through a vector in looking to delete elements:

for ( std::vector<Block>::iterator it = blocks.begin(), end = blocks.end(); it != end; /* no inc */ )
if ( /* collision */ )
it = blocks.erase( it );
else
++it;



Quote:

If I change the code to never draw the last block, it doesn't exit, but starts behaving erratically after the first collision (music stops, doesn't exit, feels similar to entering an infinite loop, but the ship still moves).


It sounds like you've got some memory leaks, memory buffer overruns, and/or other miscellaneous BadThings(TM). Could you post some more information?

What compiler are you using?

Share this post


Link to post
Share on other sites
Well, thanks for the fast reply! And thanks for pointing out that using "new" when adding objects to a vector is a memory leak, I thought vectors called destructors when erasing objects.

I just tried your points. When doing the "blocks.push_back( Block( ... ) )" thing, something really weird happened: suddenly, all the blocks were exact copies of the first object I add to the vector! The coordinates were correct, but the collision box coords and the colors were all the same as the first block I created...

That led me to believe that my problem was inheritance related. You see, my blocks inherit from a custom Sprite class, which holds basic sprite data. I took all the data from the Sprite class, added it into the Block class and removed all the inheritance. Now everythings works perfectly! Apparently my problem was even more basic that I thought. That's what you get when going to C++ from Java: you make lots of assumptions ;)

Well, _fastcall, lots and lots of thanks. Problem solved, to an extent. Now all that remains is figuring out why I was doing the inheritance incorrectly. Let's see...

// In sprite.h
class Sprite
{
(...)
}

// In sprite.cpp
Sprite::Sprite(int x, int y)
{
(...)
}

// In block.h
class Block : public Sprite
{
(...)
}

// In block.cpp
Block::Block(int x, int y, int type) : Sprite(x, y)
{
(...)
}

I didn't post this code before because, well, it is EXTREMELY basic, even though I was obviously doing something wrong here. Any ideas?

As for the compiler, I'm using MinGW under Windows (I know, I know...). Anything else you need, just ask. And thanks. Really :)

PS: What tag do you use for that nifty code embedding effect? Looks great.

Share this post


Link to post
Share on other sites
Here's another thing you can try (with inheritance):


// typedefs make typing easier (among other things...)
typedef std::vector<Block*> BlockContainerType;

BlockContainerTypeblocks;
for (int i = 0; i < LINES_PER_LEVEL; i++)
for (int j = 0; j < BLOCKS_PER_LINE; j++)
blocks.push_back( new Block(...) ); // Push back a *copy of the pointer* to the Block

// When removing a block:
for ( BlockContainerType::iterator it = blocks.begin(), end = blocks.end(); it != end; ++it )
{
if ( /* collision */ )
{
delete *it; // Delete the pointer
it = blocks.erase( it ); // Erase the node
}
}

// On cleanup:
for ( BlockContainerType::iterator it = blocks.begin(), end = blocks.end(); it != end; ++it )
delete *it; // Delete the pointer






Quote:
Original post by Arreis
I thought vectors called destructors when erasing objects.


They do; it calls Block::~Block() for each element. It won't, however, delete dynamically allocated objects (i.e. std::vector<Block*>)

Quote:
Original post by Arreis
suddenly, all the blocks were exact copies of the first object I add to the vector! The coordinates were correct, but the collision box coords and the colors were all the same as the first block I created...

That led me to believe that my problem was inheritance related. You see, my blocks inherit from a custom Sprite class, which holds basic sprite data. I took all the data from the Sprite class, added it into the Block class and removed all the inheritance. Now everythings works perfectly!


There's definitely something beefy with those two classes; I'm not sure it's even possible to have an inheritance related problem since you're storing the most derived class in a vector. Could you post the source?


Quote:
Original post by Arreis
I didn't post this code before because, well, it is EXTREMELY basic, even though I was obviously doing something wrong here.


The code itself fine, but somethings wrong with the code you put in (...) It could be that you're freeing a SDL_Surface* in a destructor of your sprite during a copy constructor or assignment operation.


Quote:
Original post by Arreis
As for the compiler, I'm using MinGW under Windows (I know, I know...). Anything else you need, just ask. And thanks. Really :)


I suggest you try out Microsoft Visual C++ 2008 Express Edition. It's got an awesome debugger to help you solve these kinds of problems.

Quote:
Original post by Arreis
PS: What tag do you use for that nifty code embedding effect? Looks great.


From the FAQ: [source][/source]

[Edited by - _fastcall on May 31, 2009 10:08:21 PM]

Share this post


Link to post
Share on other sites
All right, here's my source.


struct CollisionBox
{
int x;
int y;
int w;
int h;
bool isCircle;
};



class Sprite
{
public:
Sprite(int x, int y);
virtual ~Sprite();
virtual void draw();
virtual struct CollisionBox* getCollBox();
virtual void updateCollBox();

protected:
SDL_Surface *image;
double x, y;
struct CollisionBox *collBox;
};



Sprite::Sprite(int x, int y)
{
image = NULL;
this->x = x;
this->y = y;
collBox = new CollisionBox();
}

Sprite::~Sprite()
{
delete(image);
delete(collBox);
}



class Block : public Sprite
{
public:
Block(int x, int y, SDL_Surface *tileset, int type);
virtual ~Block();

private:
int type;
void selectColor(SDL_Surface *tileset);
};



Block::Block(int x, int y, SDL_Surface *tileset, int type) : Sprite(x, y)
{
this->type = type;
selectColor(tileset);
collBox->x = x + 1;
collBox->y = y + 1;
collBox->w = 29;
collBox->h = 15;
collBox->isCircle = false;
}

Block::~Block()
{
}



That's all the code I can think of that can be related to the problem. I removed declaration and initialization of ints, bools and the like. As for the "selectColor" method, all it does is load an image and assign it to the "image" variable.

Any obvious mistake in sight?

Share this post


Link to post
Share on other sites
Quote:
Original post by Arreis
Any obvious mistake in sight?


Here's a small recreation of the problem:

#include <iostream>
#include <vector>
using namespace std;

class Foobar
{
public:
int* mPointer;

Foobar()
{
this->mPointer = new int;
}

~Foobar()
{
delete this->mPointer;
}
};

int main()
{
std::vector<Foobar> foos;

// Construct
Foobar a;
cout << "Foobar " << &a << " has mPointer " << a.mPointer << '\n';

// Copy construct
Foobar b( a );
cout << "Foobar " << &b << " has mPointer " << b.mPointer << '\n';

// std::vector creates a Foobar and copy-constructs it from b
foos.push_back( b );
cout << "Foobar " << &foos.at(0) << " has mPointer " << foos.at(0).mPointer << '\n';

} // Oops, a.mPointer gets deleted 3 times!






Sample output:

Foobar 0022F9A8 has mPointer 000C25C8
Foobar 0022F99C has mPointer 000C25C8
Foobar 000C26A0 has mPointer 000C25C8


This would explain why all of the Blocks had the same CollisionBox. The simple solution is to provide a copy constructor for your Block, allocating its own CollisionBox (instead of stealing the copy's):


class Foobar
{
public:
// ...

Foobar( const Foobar& copy )
{
// Create a new integer and assign it to the value of what copy.mPointer points to
this->mPointer = new int( *copy.mPointer );
}
};



Sample output:

Foobar 001DF840 has mPointer 00A425C8
Foobar 001DF834 has mPointer 00A426A0
Foobar 00A426E0 has mPointer 00A42720


The other downside is that you have to do this with your image too, and that's a little tricky. So far you have an image allocated and loaded for every Block you create. Not only does this consume more memory than is needed, it also slows down your program as you're loading the images.

There are several things you could try:

1) You could use SDL_CreateRGBSurfaceFrom to create a sub-surface of tileset; it won't copy any pixel data, but be sure to call SDL_FreeSurface when you're done using the sub-surface.
2) You could store a reference to the tileset surface in your Block, and blit just a portion of it (just don't delete tileset when a Block is done with it [smile])
3) You could have an ImageManager class keep track of the Blocks' images, and giving each Block a weak pointer (i.e. a pointer that doesn't have sole ownership) during its existence.

Another note:
Use SDL_FreeSurface instead of delete on your SDL surfaces.

[Edited by - _fastcall on June 1, 2009 2:00:41 AM]

Share this post


Link to post
Share on other sites

static int blockToDelete = -1;
for (int i = 0; i &lt; blocks.size(); i++)
{
// getCollBox returns an SDLRect with the collsion box dimensions,
// and checkCollision returns true if the boxes overlap
if (checkCollision(ball-&gt;getCollBox(), blocks.at(i).getCollBox()))
{
blockToDelete = i;
}
}
if (blockToDelete != -1)
{
blocks.erase(blocks.begin() + blockToDelete);
blockToDelete = -1;
}



Just pointing this out. In this code, where you have blockToDelete = i:
If it's possible to hit 2 blocks at 1 time, you'll probably want to store multiple numbers and then delete them all that way.
OR
If it's not possible to hit 2 blocks at 1 time, just break right after blockToDelete = i. There's no point in going any deeper into the list if you've already found you match. :)

Share this post


Link to post
Share on other sites
_fastcall: OK, first of all, thanks for replying. I'll start from the end of your post.

Of course, I know using a separate image for each and every block is a waste of memory, and I intend to solve that, but since the code should work nonetheless, I prefer to leave that aside until the rest of the logic works.

Now for the main topic. If I understand correctly, what
blocks.push_back( Block(...) );


does is as follows:

1- Calls the normal constructor of the Block class to create a new object.
2- Calls the copy constructor on that object, and obtain a duplicate.
3- Adds that copy to the end of the vector.

So I create new objects, and the push_back() function creates copies of them, which should be ok as long as the destructor for the original object is not called. However, since all the objects are created on local context, they are deleted sooner or later and the copy is left with several inconsistent pointers. Is that correct? Is that what was happening?

Holland: I'll probably do the first of your solutions as soon as I get some part of the collision detection to work as I want. Thanks for the tip, anyway :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Arreis
Well, thanks for the fast reply! And thanks for pointing out that using "new" when adding objects to a vector is a memory leak, I thought vectors called destructors when erasing objects.
As already said - they do, however the issue actually comes from the fact that that delete is paired with the placement new to allocate it, all inside the vector. Your new is unmatched.
Every new of yours needs a corresponding delete of yours.

I think it's time to introduce you to the rule of three.
"Sprite" should either implement a copy-constructor and assignment operator, or those should both be declared private and left unimplemented. In any code I review, that "should" becomes a "must", otherwise it's a bug IMO. Lately I'm also trying to stress that all three should be removed if they aren't needed.

Share this post


Link to post
Share on other sites
Quote:
Original post by Arreis
And thanks for pointing out that using "new" when adding objects to a vector is a memory leak, I thought vectors called destructors when erasing objects.


They do. They call the destructor of whatever type you store in them.

A pointer's destructor (to the extent that it can be said to exist) does nothing. It certainly does not call 'delete' on whatever is pointed at, because that would cause problems in almost every case. (You can create pointers to things that weren't allocated with new; in fact, you can often create pointers without even really thinking about it.)

The rule is simple: you clean up what you allocate, and the standard library cleans up what it allocates.

Share this post


Link to post
Share on other sites
Quote:
Original post by Arreis
1- Calls the normal constructor of the Block class to create a new object.
2- Calls the copy constructor on that object, and obtain a duplicate.
3- Adds that copy to the end of the vector.



Close, there's a bit more to it ...

In the code: blocks.push_back( Block(...) ); :

1- Create a temporary Block with parameters ...
2- blocks copy-constructs the temporary object
3- blocks adds the new object to the end of the list
4- The temporary Block is destructed when the function exits.

The problem is that during a Block copy-constructor (that your compiler is filling for you automatically), it's also copying the pointer to the sprite and collision box, not the actual sprite and collision box. At the beginning of step three, there are two Blocks that point to one sprite and one collision box. As soon as one of those Blocks are destructed, that one collision box and sprite are deleted, turning the other Block's pointers into invalid pointers.

Quote:
Original post by Arreis
So I create new objects, and the push_back() function creates copies of them, which should be ok as long as the destructor for the original object is not called.


Yup. As the push_back() function exits, the temporary Block object used to create the copy for blocks is destroyed, deleting the pointers, and thus making the copy's pointers invalid. The simplest solution would be for Sprite to allocate a copy of the data held by the copy:


class Sprite
{
public:
Sprite(int x, int y);

Sprite( const Sprite& copy )
{
this->x = copy.x;
this->y = copy.y;
// this->collBox = copy.collBox; // Does not copy the object
// this->image = copy.image; // Does not copy the object

// Now this Sprite class has a collBox to call its own
this->collBox = new CollisionBox( *copy.collBox );

// It'd be safer to create the image here, instead of copying the image directly
this->image = selectColor( /* ... */ );
}
};





Quote:
Original post by Arreis
However, since all the objects are created on local context, they are deleted sooner or later and the copy is left with several inconsistent pointers. Is that correct? Is that what was happening?


If by that you mean that the temporary object passed in to push_back, then yes, that's what happens. Here are a few more things you can try:


1) Provide a copy constructor to deal with those pointers in Sprite (and/or Block, depending if those have pointers as well).
2) Use a level of indirection; use std::vector<Block*> instead of std::vector<Block>. This method would probably be better since is has more of a Java-feel to it:


typedef std::vector<Block*> BlockContainer;
BlockContainer blocks;

for (int i = 0; i < LINES_PER_LEVEL; i++)
for (int j = 0; j < BLOCKS_PER_LINE; j++)
blocks.push_back( new Block(...) ); // Push back a *copy of the pointer* to the allocated memory

// When accessing:
blocks.front()->collBox;
blocks[0]->collBox;
blocks.at(0)->collBox;

// When removing a block:
for ( BlockContainerType::iterator it = blocks.begin(), end = blocks.end(); it != end; ++it )
{
if ( /* collision */ )
{
delete *it; // Delete the memory
it = blocks.erase( it ); // Erase the node
}
}

// And on cleanup:
for ( BlockContainer::iterator it = blocks.begin(), end = blocks.end(); it != end; ++it )
delete *it; // Delete the rest of them



Hope this helps!

Share this post


Link to post
Share on other sites
It's good for OP to learn about the Rule of Three and all, but in this particular case I really don't see a reason for collBox to be allocated on the heap at all. The whole situation would be much easier to deal with if it was simply held by value.

Share this post


Link to post
Share on other sites
Well, am I glad I came here to help. It's amazing how helpful and newbie-friendly you guys are. I must say, that "Rule of Three" is something I had never heard about. To be honest, as soon as I learned about C++ copy constructors, I decided to use them as little as possible. And of course, the thought of overloading the assignment operator never crossed my mind.

It may be my Java brain speaking, but I don't like handling objects directly, I find it too cumbersome to have two different ways of accessing the same object (directly and through pointer), and since using references you can pass the "real" object as an argument, I have always liked the Java way better (all pointers). I think I'll take your advice, _fastcall, and go for a pointer vector. Actually, I tried that approach before, but changed my mind afterwards. Oh, well, good ideas come and go ;)

So, thanks for your good advice, everyone, and let me ask you guys one more thing. In his first reply, _fastcall mentions that using STL's vectors for storing pointers is not such a good idea. He reccomends using boost::ptr_vector or boost::shared_ptr. The thing is, I have heard extremely good things about the Boost library. Now that you guys know what I'm up to here, more or less, do you reccomend that I use it?

Share this post


Link to post
Share on other sites
Quote:
Original post by Arreis
as soon as I learned about C++ copy constructors, I decided to use them as little as possible.


But you do use them quite a bit; just not explicitly. What's in question is whether you implement the copy constructor, or let the compiler generate a default copy constructor. And the answer to that is "do the work when and only when it needs to be done".

Note that with more sophisticated tools like boost::shared_ptr, you can often avoid doing the work when it would otherwise have been necessary.

Quote:
and since using references you can pass the "real" object as an argument, I have always liked the Java way better (all pointers).


Of course, Java's "pointers" aren't really like C++ pointers; but then, they aren't quite like C++ references, either. And I doubt you'd still like Java so much if you had to write all the *'s and &'s that C++ makes you use to work with pointers. ;)

Quote:
In his first reply, _fastcall mentions that using STL's vectors for storing pointers is not such a good idea.


It isn't.

Quote:
He reccomends using boost::ptr_vector or boost::shared_ptr. The thing is, I have heard extremely good things about the Boost library. Now that you guys know what I'm up to here, more or less, do you reccomend that I use it?


Yes.

Share this post


Link to post
Share on other sites
Using boost's smart pointers rather than trying to manually manage memory or even instead of implementing your own smart pointers is a very good idea and would be highly recommended.

However, storing objects by value is usually the simplest and best method where possible, as theOcelot mentioned.

But you have to understand the main limitation of boost's smart pointers, they are reference counted. This means that if they are used when circular referencing is possible you can get memory leaks.

Learning how to deal with values when coming from Java takes a bit of effort, but I think it will be worthwhile. After all, boost's smart pointers (and other RAII helper classes) work precisely because you manipulate them as values.

Share this post


Link to post
Share on other sites
Well, all decided then. I'm off to read some Boost tutorials ;) And about holding the collBox by value... I suppose you're right, it's probably better that way. Oh, well, I'm still learning, right? I'm supposed to do clumsy things like this! :D

Thanks for all the help, really. See you, guys.

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