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.

The method I give below is likely to be faster than remove_if but, unlike remove_if, will NOT preserve the relative order of the elements. If you care about maintaining order (i.e. your vector is sorted), use remove_if, as in the answer above. If you don't care about order, and if the number of items to be deleted is typically less than a quarter of the vector, this method is likely to be faster:

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