How would you remove elements of a std::vector based on some property of the elements?

Question

If for instance you have a std::vector<MyClass>, where MyClass has a public method: bool isTiredOfLife(), how do you remove the elements that return true?

Answer 1

I prefer remove_if

v.erase(remove_if(v.begin(), v.end(), 
                 mem_fun_ref(&MyClass::isTiredOfLife)), 
        v.end());

remove_if returns an iterator pointing after the last element that's still in the sequence. erase erases everything from its first to its last argument (both iterators).

Answer 2

Using remove_if is the "right" way to do this. Be careful NOT to use an iterator to cycle through and erase, because removing items invalidates the iterator. In fact, any example which uses erase() as its primary method is a bad idea on vectors, because erase is O(n), which will make your algorithm O(n^2). This should be an O(n) algorithm.

I think remove_if is a little complex, but the example given above is good. Here is another good O(n) way to do it:

for( size_t i = 0; i < vec.size(); )
   if( vec[i].isTiredOfLife() )
   {
      vec[i] = vec.back();
      vec.pop_back();
   }
   else
      ++i;