Posts Tagged ‘erase-remove idiom’

I heard you’re employing STL vectors in your new shooting videogame and you’re facing a couple of troubles. You have explained me the context, let me try to tell you what I have understood.

Your game has a fixed number of enemies and the number of levels depends on the player’s ability.

At the first level, the player has a certain amount of time to kill as many enemies as he can, but the battlefield is very big, making hard to unearth all the enemies within that time.

When the time expires, a new level begins. It presents again the enemies that the player didn’t kill during the last gunfight. However, the battlefield will be smaller than the previous one and the time reduced. It’s a number-of-enemies-driven game, rather than a classical level-driven one. If the player kills all the enemies at the first level then he’ll take a flood of points, boasting about its success and sharing a nerd message on Facebook.

At the beginning, you decide to store all the enemies in a vector. As the player kills some bad men, these are removed from the vector. This does a fine job of reducing the size of the vector, but it does nothing to reduce its capacity. If your vector held a thousand zombies at some point, its capacity would continue to be at least 1000, even if  later it held only, say, 10. To avoid having your vector hold onto memory it no longer needs, you’d like to have a way to reduce its capacity from the maximum it used to the amount it currenly needs (this can be very useful whenever a new level starts).

Such a reduction in capacity is commonly known as “shrink to fit“. It’s easy to program but the code is less easy than what you think. Meyers’ Effective STL comes to the rescue:


vector<Enemy>(enemies).swap(enemies);

The expression vector<Enemy>(enemies) creates a temporary vector that is a copy of enemies : vector’s copy constructor does the work. However, vector’s copy constructor allocates only as much memory as is needed for the elements being copied, so this temporary vector has no excess capacity. We then swap the data in the temporary with that in enemies, and by the time we’re done, enemies has the trimmed capacity of the temporary, the temporary holds the bloated capacity that used to be in enemies. At that point (the end of the statement), the temporary is destroyed, thus freeing the memory formerly used by enemies. Swap-trick!

Often, small (and apparently simple) pieces of code hide knottier details.

Another matter you’re coping with is about removing elements. You’re confused by the existence of two methods: erase and remove. But even this time, Meyers saves us. The former is a member function, the latter is an STL algorithm. Thus, remove doesn’t know the container it’s supposed to remove things from, and without that container, there’s no way for it to call the member functions that are necessary if one is to really remove something. This is way remove doesn’t “really” remove anything!

But what does it do?

It moves elements in the range it’s given until all the “unremoved” elements are at the front of the range. It returns an iterator pointing one past the last “unremoved” element. This is the “new logical end” of the range. It works by overwriting “bad” elements (it has repercussions when those elements are pointers – be careful!) with “good” succeding elements. The following image shows an example, supposing we want to remove all the elements equal to 3:

Only container member functions can eliminate container elements then you should follow remove by erase if you really want to remove something. The elements you want to erase are easy to identify. They’re the elements of the original range that start at the “new logical end” of the range and continue until the real end of the range:

class Enemy {

public:
    // ...
    Enemy(int hp) : life (hp) { /* ... */ }
    // ...
    operator int() { return life; }
    // ...
private:
    // ...
    int life;
    // ...
};
// ...

vector<Enemy> enemies;
// ...
enemies.erase( remove( enemies.begin(), enemies.end(), 0), enemies.end() );

This is known as erase-remove idiom. I defined a conversion operator to int so I could directly pass a value (0 – it means the enemy is dead) to check against, rather than writing a predicate.

This brief post talked about two common tricks of STL vectors. Read more in Meyers’ Effective STL.

Ha, good luck for your game!

Advertisements