How to delete an element from a vector while looping over it?

Question

I am looping through a vector with a loop such as for(int i = 0; i < vec.size(); i++). Within this loop, I check a condition on the element at that vector index, and if a certain condition is true, I want to delete that element.

How do I delete a vector element while looping over it without crashing?

You could use `remove_if` and `erase` maybe? http://en.wikipedia.org/wiki/Erase-remove_idiom — clstrfsck, Dec 21 '11 at 22:30
Erase Remove: http://stackoverflow.com/questions/4175896/safe-way-to-continuously-erase-from-a-stdvector — Martin York, Dec 21 '11 at 23:01

score 31 · Accepted Answer · answered Dec 21 '11 at 22:37

The idiomatic way to remove all elements from an STL container which satisfy a given predicate is to use the remove-erase idiom. The idea is to move the predicate (that's the function which yields true or false for some element) into a given function, say pred and then:

static bool pred( const std::string &s ) {
  // ...
}

std::vector<std::string> v;
v.erase( std::remove_if( v.begin(), v.end(), pred ), v.end() );

If you insist on using indices, you should not increment the index for every element, but only for those which didn't get removed:

std::vector<std::string>::size_type i = 0;
while ( i < v.size() ) {
    if ( shouldBeRemoved( v[i] ) ) {
        v.erase( v.begin() + i );
    } else {
        ++i;
    }
}

However, this is not only more code and less idiomatic (read: C++ programmers actually have to look at the code whereas the 'erase & remove' idiom immediately gives some idea what's going on), but also much less efficient because vectors store their elements in one contiguous block of memory, so erasing on positions other than the vector end also moves all the elements after the segment erased to their new positions.

How to know how many elements have you killed after the v.erase() ? (Without counting the size before & after?) — dynamic, Jun 03 '13 at 09:59
The predicate need not be a function, but may be a functor (especially if you need to get external data in to decide whether or not to remove an element). — Paul Price, Sep 29 '14 at 16:25
@dynamic `std::vector` features random-access iterators, so you can tell how many elements are erased simply by subtracting the new end iterator returned by `std::remove_if` from the current end iterator (e.g. `v.end()`). — Frerich Raabe, Mar 09 '15 at 21:38

score 10 · Answer 2 · answered Dec 21 '11 at 23:05

If you cannot use remove/erase (e.g. because you don't want to use lambdas or write a predicate), use the standard idiom for sequence container element removal:

for (auto it = v.cbegin(); it != v.cend() /* not hoisted */; /* no increment */)
{
    if (delete_condition)
    {
        it = v.erase(it);
    }
    else
    {
        ++it;
    }
}

If possible, though, prefer remove/erase:

#include <algorithm>

v.erase(std::remove_if(v.begin(), v.end(),
                       [](T const & x) -> bool { /* decide */ }),
        v.end());

`for (auto it . . . ` will this compile? – ThomasMcLeod Dec 22 '11 at 04:17 — ThomasMcLeod, Dec 22 '11 at 04:17

score 8 · Answer 3 · answered Dec 21 '11 at 22:31

8

Use the Erase-Remove Idiom, using remove_if with a predicate to specify your condition.

answered Dec 21 '11 at 22:31

Fred Larson

60,987
18
112
174

Can we keep the links intern to SO. Less likely to be vandalized here. – Martin York Dec 21 '11 at 23:02

score 3 · Answer 4 · answered Apr 30 '14 at 08:55

3

if(vector_name.empty() == false) {
    for(int i = vector_name.size() - 1; i >= 0; i--)
    {
        if(condition) 
            vector_name.erase(vector_name.at(i));
    }
}

This works for me. And Don't need to think about indexes have already erased.

answered Apr 30 '14 at 08:55

Dawoon Yi

426
3
9

Should be erase(vector_name.begin() + i); also checking if vector is empty is useless because size == 0 would lead to no iteration in the for loop – log0 Dec 14 '15 at 11:50
@log0 random access is possible. why not? and agree with the latter. – Dawoon Yi Dec 28 '15 at 08:40
`erase` takes an iterator as argument, `at` returns a vector **value** (a string for instance) – log0 Dec 29 '15 at 15:32

score 1 · Answer 5 · answered Dec 21 '11 at 22:30

1

Iterate over the vector backwards. That way, you don't nuke the ability to get to the elements you haven't visited yet.

answered Dec 21 '11 at 22:30

That Chuck Guy

443
4
12

score 1 · Answer 6 · answered Dec 22 '11 at 04:35

I realize you are asking specifically about removing from vector, but just wanted to point out that it is costly to remove items from a std::vector since all items after the removed item must be copied to new location. If you are going to remove items from the container you should use a std::list. The std::list::erase(item) method even returns the iterator pointing to the value after the one just erased, so it's easy to use in a for or while loop. Nice thing too with std::list is that iterators pointing to non-erased items remain valid throughout list existence. See for instance the docs at cplusplus.com.

That said, if you have no choice, a trick that can work is simply to create a new empty vector and add items to it from the first vector, then use std::swap(oldVec, newVec), which is very efficient (no copy, just changes internal pointers).

How to delete an element from a vector while looping over it?

6 Answers6

Linked

Related