Tip #7: A remove_if for vector<T *>

It is common for C++ programmers to create STL containers of pointers to objects; typically these objects are allocated from the free store and the container “owns” the memory allocated to them, which means:

1) When the container is deleted, the free store memory of all the objects should be freed as well; and

2) If an algorithm that removes elements from the container is applied, the free store memory should be released as necessary.

Number 1) is easy: either derive from the container at hand or embed it into your own class, and in the destructor loop over the elements and call delete for each element.

Number 2), however, is conceptually difficult: the STL does provide an algorithm, called remove_if, to remove elements that match a certain criteria. Unfortunately, this algorithm cannot be used without producing memory leaks in this case. Normally (if your container would not contain pointers to objects on the free store) you would write something like:

vector<Object> v ;
...
vector<Object>::iterator last =
   remove_if( v.begin(), v.end(), predicate() ) ;
v.erase( last, v.end() ) ;

In the case of containers of pointers, however, the program must additionally get rid of the free store memory that is pointed to by the element pointers. The idea comes to mind to loop over the open range [last,v.end()) and call delete for each pointer in this range — this is however wrong, since that range contains only leftovers from the remove_if algorithm; specifically it does not contain the pointers to the elements to be deleted! (For a discussion about what remove_if removes and why in this case pointers can be lost, see section 9.7 of Nicolai Josuttis’ The C++ Standard Library.) But fortunately there is a solution to this problem: the partition algorithm does just what we want: it separates the pointers into a range of pointers to elements that satisfies a certain condition, and a range of pointers that doesn’t satisfy that very same condition. It could be used like this:

vector<Object *> v ;

v.push_back( new Object( ... ) ) ;
...
vector<Object *>::iterator last =
   partition( v.begin(), v.end(), not1(predicate()) ) ;
for( vector<Object *>::iterator i = last ; i != v.end() ; ++i )
{
    delete *i ;
}
v.erase( last, v.end() ) ;

Or, to avoid the problem entirely, this can be automated a bit by making the contained pointers responsible for their own cleanup. This is done by using a vector of reference-counted smart pointers instead of a vector of bald pointers. For example, you can use Boost’s shared_ptr (see <www.boost.org>) and use a vector<shared_ptr<T> > instead of a vector<T*>.

[See also Item 33 of Scott Meyers’ forthcoming book Effective STL —mb.]

Thanks to Harald Nowak, [email protected], for this tip.