Channels ▼
RSS

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


July 2001/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, Harald.Nowak@infrasoft.at, for this tip.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video