Skip to main content
GameDev.net gamedev.net
🔒 Locked 🎮 Unity

C++ Vector problem

Started by Mr_Threepwood Feb 24, 2008 at 12:46 PM 4 replies 3.1k views
Original Post
Mr_Threepwood
Mr_Threepwood
Hi, I'm having some difficulty with vectors in C++, and I was hoping someone could provide me with some insights. Right now I'm pretty sure that the code I have dealing with vectors is having border cases that cause the problems (like when the iterator is on the last element of the vector), but I'm not 100% sure that's the case. Here's the code that's causing me problems: 

void GameEngine::UpdateSprites()
{
  // Expand the capacity of the sprite vector, if necessary
  if (m_vSprites.size() >= (m_vSprites.capacity() / 2))
    m_vSprites.reserve(m_vSprites.capacity() * 2);

  // Update the sprites in the sprite vector
  RECTFLOAT          rcOldSpritePos;
  SPRITEACTION  saSpriteAction;
  vector<Sprite*>::iterator siSprite;

  for (siSprite = m_vSprites.begin(); siSprite != m_vSprites.end(); siSprite++)
  {
    // Save the old sprite position in case we need to restore it
    rcOldSpritePos = (*siSprite)->GetPosition();

    // Update the sprite
    saSpriteAction = (*siSprite)->Update();

    // Handle the SA_ADDSPRITE sprite action
    if (saSpriteAction & SA_ADDSPRITE)
      // Allow the sprite to add its sprite
      AddSprite((*siSprite)->AddSprite());

    // Handle the SA_KILL sprite action
    if (saSpriteAction & SA_KILL)
    {
      // Notify the game that the sprite is dying
      SpriteDying(*siSprite);

      // Kill the sprite
      delete (*siSprite);

      siSprite=m_vSprites.erase(siSprite);
	 
      continue;
    }

    // See if the sprite collided with any others
    if (CheckSpriteCollision(*siSprite))
      // Restore the old sprite position
      (*siSprite)->SetPosition(rcOldSpritePos);
  }
}
Originally after the line "siSprite=m_vSprites.erase(siSprite);" i had "siSprite--;" which seemed to make it crash less, but still crashes. Another one of my problems is that I don't think I fully know how vectors work, like when I'm doing an erase, does it still leave a NULL element in the vector, or does it "shift" all the elements that are deleted over by one? If it's just leaving it NULL then the problem could be I'm trying to do sprite actions on null elements. Another thing I don't understand is what's going to happen when the loop has to erase the last element of the vector, what is the iterator returned from the "erase" function going to be? Is it undefined?
algumacoisaqualquer
algumacoisaqualquer
As far as I know, when you call siSprite=m_vSprites.erase(siSprite); the vector might be reallocated, so it makes your iterator no longer valid. Actually, why do you have the 'siSprite=' part in that expression? I'm not sure what that part is doing, maybe you should wait until some of the clever guys shows up :D
dalleboy
dalleboy
You should try to use the vector::erase/remove_if pattern:

struct ShouldRemove{   bool operator(T& element) const   {      // TODO: perform extra processing on element.      // TODO: return true if element should be removed, false if it should be kept.   }};std::vector<T> vec;vec.erase(std::remove_if(vec.begin(), vec.end(), ShouldRemove()), vec.end());
Rattenhirn
Rattenhirn
Vector erase returns an iterator to the element after the erased one.
When, in the next for loop, this iterator is incremented and effectively skipping one element.

If the last element was being deleted, the ++ will increment the iterator past the "end()" of the vector, creating all sorts of unpleasent effects.

This is a common mistake and easily fixed:
Remove "siSprite++" from the from the first line and put it at the end of the loop, so that it's only called when no erase has happened.

ToohrVyk
ToohrVyk
Quote:

// Expand the capacity of the sprite vector, if necessary
if (m_vSprites.size() >= (m_vSprites.capacity() / 2))
m_vSprites.reserve(m_vSprites.capacity() * 2);


The vector already does this for you by doubling the capacity whenever there isn't enough room to store all the elements.

Quote:
for (siSprite = m_vSprites.begin(); siSprite != m_vSprites.end(); siSprite++)


This describes a sequential traversal of your sprites vector, which means you cannot remove elements from within. An alternative, using loops, would have been: 

vector<Sprite*>::iterator siSprite = m_vSprites.begin();while (siSprite != m_vSprites.end()){  if (should-erase)    siSprite = m_vSprites.erase(siSprite);  else    ++siSprite;}


However, a typical approach to vector usage is to avoid these loops which can both alter and erase elements. Instead, usage is split into an "update" loop and a "remove" loop. Typically:

// A classic visitor, used to interact with the sprite during// its update to forward the calls to the game engine. The default// behavior is to ignore the callbacks.class Visitor {public:  virtual void AddSprite(class Sprite*) {}  virtual void SpriteDeath(class Sprite*) {}  virtual ~Visitor();};// A classic sprite object definition.class Sprite{public:  void update(Visitor &v); // This function stores the former position of the sprite,                            // computes the sprite's action and executes it internally                            // (except for the deletion of the pointer). The visitor                           // object is notified whenever the object wishes to add another                           // sprite, or when the object dies. If a collision happens,                           // the old position is restored.  bool dead() const; // Returns 'false' unless the sprite has died in the last                     // call to the update function.};// A visitor for the game engine: forwards the visitor calls to the// game engine from within the sprite's update method.class GameEngineVisitor : public Visitor{  GameEngine & g;public:  GameEngineVisitor(GameEngine & g) : g(g) {}  void AddSprite(Sprite *s) { g.AddSprite(s); }  void SpriteDeath(Sprite *s) { g.SpriteDeath(s); }  // Returns a pointer to the sprite (if it's still alive)  // or 'null' if it's not.  Sprite * operator()(Sprite *s)   {     s -> update(*this);     if (s -> dead()) { delete s; return 0; }    return s;  }};// Helper function : is a sprite dead? Deletes the pointer if it's dead.bool is_dead(Sprite *s) { return !s; }// The update-and-remove routine.void GameEngine::UpdateSprites(){  GameEngineVisitor visit(*this);  std::transform(sprites.begin(), sprites.end(), sprites.begin(), visit);  sprites.erase(std::remove_if(sprites.begin(),                                 sprites.end(),                               is_dead),                sprites.end());  CommitAdded();}
Using std::remove_if achieves better performance, because objects are moved to the end and then erased as a block, instead of being erased one by one from the middle of the vector. The method does not introduce any cyclical dependency between the game engine and the sprite, and provides a better interface than the action-flags system you are currently using.

Also, make sure that AddSprite does not modify the sprite vector, but instead adds to a secondary vector which is appended to the main vector when CommitAdded() is called.
Blog — Facebook
Mr_Threepwood
Mr_Threepwood
Thanks for the help, I ended up going with the while loop fix just because that visitor method looked too complicated for now, definitely something I'm going to learn though and use in the future. It turned out I had two problems, that one mentioned, plus I had a sprite being referenced that potentially could not exist if it's cleared the memory it was originally assigned to. The debug tools in VS rock!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.