what is a efficient way to iterate a vector from and end and remove items?

[chrisben]

Hi,

I tried to iterate a vector and delete item if certain condition met. Is this an efficient implementation?
Any comments?
Thanks for the help

Chris


Iterator it = myVector.end();
-- it;

while( it != myVector.begin())
{
//remove the item if the condition met
if( it->condition )
{
Iterator itTemp = it - 1;
myVecoter.erase(it);
it = itTemp;
}
else
-- it;

}

[Cubbi]

Each vector::erase() copies all elements from the one that's being deleted to the end of the vector. Given an n-element vector, this is O(n) copies. Given m elements to delete, your algorithm performs O(m*n) copies.

The standard std::remove_if() followed by a single vector::erase() is linear

If it->condition doesn't depend on the order of iteration, the efficient solution is simply

myVector.erase(
        remove_if(myVector.begin(), myVector.end(),  std::bind(&Foo::condition, _1))
        , myVector.end());

demo: http://ideone.com/SNz2y

(or use your own functor instead of that bind)

[chrisben]

Thanks a lot, Cubbi.

Interested to know how remove_if achieve O(m)?

[Cubbi]

@chrisben sorry, it's O(n) moves/copies for std::remove_if because it has to preserve order of non-removed elements, I corrected the post.

For only m swaps, use std::partition() instead: http://ideone.com/Bnkka or write your own loop similar to http://www.cplusplus.com/reference/algorithm/partition/