STL Tips (Maybe some Tricks Later)

Like most articles here, this one will start with a shallow contrivance to make a point. A collection of Foo objects, perhaps in an STL vector.

namespace
{
    std::vector<Foo *> fooCollection;
}

Now, let's say a Foo pointer can appear one or more times in fooCollection. Furthermore, let's also assume that when a Foo is destroyed, it should probably not exist in the collection anymore.

Foo::~Foo()
{
    std::vector<Foo *>::iterator i;
    for(i = fooCollection.begin(); i != fooCollection.end(); ++i)
    {
        Foo * target = *i;
        if(target == this)
        {
            fooCollection.erase(i);
        }
    }
}

Pretty straightforward -- except once the code is run, awful things will happen. Iterators aren't necessarily valid after the collection has been modified.

Foo::~Foo()
{
    std::vector<Foo *>::iterator i;
    for(i = fooCollection.begin(); i != fooCollection.end(); ++i)
    {
        Foo * target = *i;
        if(target == this)
        {
            fooCollection.erase(i);
            break;
        }
    }
}

Ok, so after Foo is found in the collection, erase it, then break. The program no longer explodes when it is run. Of course, it is also no longer correct. Remember, the collection could contain the same Foo pointer more than once!

Most programmers familiar with the STL have already been cringing at the first two examples. std::vector<T>::erase() returns an iterator to the next element. To write code that will work properly with a vector after it has been modified, this value needs to be used. Incrementing an iterator while modifying a container is bad mojo.

Foo::~Foo()
{
    std::vector<Foo *>::iterator i;
    for(i = fooCollection.begin(); i != fooCollection.end();)
    {
        Foo * target = *i;
        if(target == this)
        {
            i = fooCollection.erase(i);
        }
        else
        {
          ++i;
        }
    }
}

Alright, that's the right way to remove several elements from a vector from within a for loop. By now, STL antagonists are surely chuckling at the rest of the C++ pedants! "What a pain in the ass!". They would be right. That's probably the worst way to solve the problem.

There's hope! STL provides several algorighms that operate on containers (also known as modifying algorithms. We'll remove all of that icky destructor code, replace it with a single algorithm call and improve encapsulation altogether!

Foo::~Foo()
{
    foo.erase(std::remove(fooCollection.begin(), fooCollection.end(), this), fooCollection.end());
}

Tada! A 90% reduction in code (potentially a 90% reduction in bugs) and it does the right thing. But wait! There's more! Because the remove algorithm doesn't necssarily operate with vectors exclusively, fooCollection can be refactored more easily to be something other than a vector. If it were a list or something else, the Foo destructor would continue to work unchanged!

Using what that the STL has to offer can drastically improve code quality. In addition to generic containers, the standard also defines adaptors, function objects and other support algorithms that work well with containers. Using only adapters supplied with the STL, std::remove()'s functionality can also be expressed as:

Foo::~Foo()
{
    std::remove_if(fooCollection.begin(), fooCollection.end(), std::bind2nd(equal_to<Foo *>(), this));
}

In another article, I'll talk a bit about function objects (functors) and some other STL tricks to help separate container-specific code from general game programming and to be more expressive with algorithms.
In the mean time, here are some references to useful and interesting algorithms, adapters and functors, some are straightforward, some are mind-bending in the ways thay can be expressed and used:

• bind2nd
• Functor Overview
• for_each
• compose2