Removing item from vector, while in C++11 range 'for' loop?

Question

I have a vector of IInventory*, and I am looping through the list using C++11 range for, to do stuff with each one.

After doing some stuff with one, I may want to remove it from the list and delete the object. I know I can call delete on the pointer any time to clean it up, but what is the proper way to remove it from the vector, while in the range for loop? And if I remove it from the list will my loop be invalidated?

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

for (IInventory* index : inv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
}

Psychologist

If you want to get fancy, you could use std::remove_if with a predicate that "does stuff" and then returns true if you want the element removed. – Tocsin

Is there a reason why you can't just add an index counter and then use something like inv.erase(index)? – Kirstiekirstin

@TomJ: That would still screw up the iteration. – Necropolis

@Kirstiekirstin and it would be a performance killer - on every erase, you get to move all elements after the erased one. – Chavannes

@BenVoigt i-- after delete. Or iterate backwards with integer indices. – Poussin

@bobobobo: That still has O(N^2) complexity. – Necropolis

@BenVoigt I recommended switching to std::list below – Poussin

Answer 1

No, you can't. Range-based for is for when you need to access each element of a container once.

You should use the normal for loop or one of its cousins if you need to modify the container as you go along, access an element more than once, or otherwise iterate in a non-linear fashion through the container.

For example:

auto i = std::begin(inv);

while (i != std::end(inv)) {
    // Do some stuff
    if (blah)
        i = inv.erase(i);
    else
        ++i;
}

Domesticate

Wouldn't erase-remove idiom applicable here ? – Ebba

@Ebba I decided not to try to do that because apparently he needs to iterate over every item, do calculations with it, and then possibly remove it from the container. Erase-remove says that you just erase elements for which a predicate returns true, AFAIU, and it seems better this way to not mix iteration logic in with the predicate. – Domesticate

@SethCarnegie Erase-remove with a lambda for the predicate elegantly allows that (since this is already C++11) – Saphead

Don't like this solution, it's O(N^2) for most containers. remove_if is better. – Necropolis

Erasing from a vector invalidates iterators and references at or after the point of the erase, including the end() iterator, isn't it? Isn't you code incorrect then? – Lithuanian

@Lithuanian No it's fine because he doesn't store end iterator. – Bunny

@BenVoigt Erasing by iterator is by no means O(n^2), even for vectors it will only be linear for the remaining elements after the iterator. For maps and sets it is amortized constant time. That said, remove_if is often clearer. Perhaps you were thinking of removing by key? – Tamper

@swalog: Removal of a single item is linear for the commonly used containers (vector, deque). Therefore, removal of multiple items is assumed O(N^2). – Necropolis

I should clarify my prior comment: independent removal of O(N) items, seen in this answer, costs O(N^2). coordinated removal of multiple items, as seen in remove_if, can be O(N) – Necropolis

Although accepted, this answer is not correct - see my answer below! – Atheist

this answer is correct, erase returns a new valid iterator. it might not be efficient, but it's guaranteed to work. – Sinclare

Answer 2

Every time an element is removed from the vector, you must assume the iterators at or after the erased element are no longer valid, because each of the elements succeeding the erased element are moved.

A range-based for-loop is just syntactic sugar for "normal" loop using iterators, so the above applies.

That being said, you could simply:

inv.erase(
    std::remove_if(
        inv.begin(),
        inv.end(),
        [](IInventory* element) -> bool {
            // Do "some stuff", then return true if element should be removed.
            return true;
        }
    ),
    inv.end()
);

Tetrafluoroethylene

"because there is a possibility that vector reallocated the block of memory in which it keeps its elements" No, a vector will never reallocate due to a call to erase. The reason the iterators are invalidated is because each of the elements succeeding the erased element are moved. – Ectomere

A capture-default of [&] would be appropriate, to allow him to "do some stuff" with local variables. – Saphead

This doesn't look any simpler than an iterator-based loop, in addition you have to remember to surround your remove_if with .erase, otherwise nothing happens. – Poussin

@Poussin If by "iterator-based loop" you mean Seth Carnegie's answer, that is O(n^2) on average. std::remove_if is O(n). – Tetrafluoroethylene

You have a really good point, by swapping elements into the back of the list and avoiding actually moving elements until after all elts "to be removed" is done (which remove_if must do internally). However if you have a vector of 5 elements and you only .erase() 1 at a time, there is no performance impact for using iterators vs remove_if. If the list is larger, you really should be switching to std::list where there's lots of middle-of-list removal. – Poussin

@Poussin Unless you actually need random access. – Tetrafluoroethylene

Answer 3

You ideally shouldn't modify the vector while iterating over it. Use the erase-remove idiom. If you do, you're likely to encounter a few issues. Since in a vector an erase invalidates all iterators beginning with the element being erased upto the end() you will need to make sure that your iterators remain valid by using:

for (MyVector::iterator b = v.begin(); b != v.end();) { 
    if (foo) {
       b = v.erase( b ); // reseat iterator to a valid value post-erase
    else {
       ++b;
    }
}

Note, that you need the b != v.end() test as-is. If you try to optimize it as follows:

for (MyVector::iterator b = v.begin(), e = v.end(); b != e;)

you will run into UB since your e is invalidated after the first erase call.

Satan

@ildjarn: Yep, true! That was a typo. – Satan

This isn't the erase-remove idiom. There is no call to std::remove, and it's O(N^2) not O(N). – Saphead

@Potatoswatter: Of course not. I was trying to point out the problems with deleting as you iterate. I guess my wording didn't pass muster? – Satan

Answer 4

Is it a strict requirement to remove elements while in that loop? Otherwise you could set the pointers you want to delete to NULL and make another pass over the vector to remove all NULL pointers.

std::vector<IInventory*> inv;
inv.push_back( new Foo() );
inv.push_back( new Bar() );

for ( IInventory* &index : inv )
{
    // do some stuff
    // ok I decided I need to remove this object from inv...?
    if (do_delete_index)
    {
        delete index;
        index = NULL;
    }
}
std::remove(inv.begin(), inv.end(), NULL);

Churn

Answer 5

sorry for necroposting and also sorry if my c++ expertise gets in the way of my answer, but if you trying to iterate through each item and make possible changes (like erasing an index), try using a backwords for loop.

for(int x=vector.getsize(); x>0; x--){

//do stuff
//erase index x

}

when erasing index x, the next loop will be for the item "in front of" the last iteration. i really hope this helped someone

Lieberman

just dont forget when using x to access a certain index, do x-1 lol – Lieberman

I like this answer as it is extremely obvious what's going on (no relying on "this and that iterator get set to this and that on deletion"). As lilbigwill99 mentioned, you need to index using (x-1). However reevaluating that everywhere is painful for syntax and performance. I would suggest initializing the vector to x=(size-1), compare x>=0 (not just >), then proceeding "normally" with indexing. – Blowzy

I do want to add that for vector types (as requested by OP), from a performance perspective, this is also the fastest (no reorganizing of the vector's memory as we are deleting from the end). – Blowzy

Answer 6

OK, I'm late, but anyway: Sorry, not correct what I read so far - it is possible, you just need two iterators:

std::vector<IInventory*>::iterator current = inv.begin();
for (IInventory* index : inv)
{
    if(/* ... */)
    {
        delete index;
    }
    else
    {
        *current++ = index;
    }
}
inv.erase(current, inv.end());

Just modifying the value an iterator points to does not invalidate any other iterator, so we can do this without having to worry. Actually, std::remove_if (gcc implementation at least) does something very similar (using a classic loop...), just does not delete anything and does not erase.

Be aware, however, that this is not thread safe(!) - however, this applies, too, for some of the other solutions above...

Atheist

What the heck. This is an overkill. – Stonecrop

@Stonecrop Really? This is the most efficient algorithm you can get with vectors (does not matter if range based loop or classic iterator loop): This way, you move each element in the vector at most once, and you iterate over the entire vector exactly once. How many times would you move subsequent elements and iterate over the vector if you deleted each matching element via erase (provided you delete more than one single element, of course)? – Atheist

Answer 7

I will show with example, the below example remove odd elements from vector:

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};

    //method 1
    for(auto it = vecInt.begin();it != vecInt.end();){
        if(*it % 2){// remove all the odds
            it = vecInt.erase(it);
        } else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 2
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 2
    for(auto it=std::begin(vecInt);it!=std::end(vecInt);){
        if (*it % 2){
            it = vecInt.erase(it);
        }else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 3
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 3
    vecInt.erase(std::remove_if(vecInt.begin(), vecInt.end(),
                 [](const int a){return a % 2;}),
                 vecInt.end());

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

}

output aw below:

024
024
024

Keep in mind, the method erase will return the next iterator of the passed iterator.

From here , we can use a more generate method:

template<class Container, class F>
void erase_where(Container& c, F&& f)
{
    c.erase(std::remove_if(c.begin(), c.end(),std::forward<F>(f)),
            c.end());
}

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};
    //method 4
    auto is_odd = [](int x){return x % 2;};
    erase_where(vecInt, is_odd);

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;    
}

See here to see how to use std::remove_if. https://en.cppreference.com/w/cpp/algorithm/remove

Postdoctoral

Answer 8

In opposition to this threads title, I'd use two passes:

#include <algorithm>
#include <vector>

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

std::vector<IInventory*> toDelete;

for (IInventory* index : inv)
{
    // Do some stuff
    if (deleteConditionTrue)
    {
        toDelete.push_back(index);
    }
}

for (IInventory* index : toDelete)
{
    inv.erase(std::remove(inv.begin(), inv.end(), index), inv.end());
}

Canary

Answer 9

A much more elegant solution would be to switch to std::list (assuming you don't need fast random access).

list<Widget*> widgets ; // create and use this..

You can then delete with .remove_if and a C++ functor in one line:

widgets.remove_if( []( Widget*w ){ return w->isExpired() ; } ) ;

So here I'm just writing a functor that accepts one argument (the Widget*). The return value is the condition on which to remove a Widget* from the list.

I find this syntax palatable. I don't think I would ever use remove_if for std::vectors -- there is so much inv.begin() and inv.end() noise there you're probably better off using an integer-index-based delete or just a plain old regular iterator-based delete (as shown below). But you should not really be removing from the middle of a std::vector very much anyway, so switching to a list for this case of frequent middle of list deletion is advised.

Note however I did not get a chance to call delete on the Widget*'s that were removed. To do that, it would look like this:

widgets.remove_if( []( Widget*w ){
  bool exp = w->isExpired() ;
  if( exp )  delete w ;       // delete the widget if it was expired
  return exp ;                // remove from widgets list if it was expired
} ) ;

You could also use a regular iterator-based loop like so:

//                                                              NO INCREMENT v
for( list<Widget*>::iterator iter = widgets.begin() ; iter != widgets.end() ; )
{
  if( (*iter)->isExpired() )
  {
    delete( *iter ) ;
    iter = widgets.erase( iter ) ; // _advances_ iter, so this loop is not infinite
  }
  else
    ++iter ;
}

If you don't like the length of for( list<Widget*>::iterator iter = widgets.begin() ; ..., you can use

for( auto iter = widgets.begin() ; ...

Poussin

I don't think you understand how remove_if on a std::vector actually work, and how it keeps the complexity to O(N). – Necropolis

That doesn't matter. Removing from the middle of a std::vector is always going to slide each element after the one you removed up one, making a std::list a much better choice. – Poussin

Nope, it will not "slide each element up one". remove_if will slide each element up by the number of spaces freed. By the time you account for cache usage, remove_if on a std::vector likely outperforms removal from a std::list. And preserves O(1) random access. – Necropolis

Very clever, but a removal at the front of a std::vector is still O(N) (memory sliding cost) any way you slice it, while a std::list has O(1) removal for every case (change 2 pointers). – Poussin

Then you have a great answer in search of a question. This question talks about iterating the list, which is O(N) for both containers. And removing O(N) elements, which is also O(N) for both containers. – Necropolis

I didn't get initially that remove_if by some internal magic actually avoids moving anything until it has identified all the elts to be removed have been identified and marked. Interesting. – Poussin

Pre-marking isn't required; it's perfectly possible to do this in a single pass. You just need to keep track of "next element to be inspected" and "next slot to be filled". Think of it as building a copy of the list, filtered based on the predicate. If the predicate returns true, skip the element, otherwise copy it. But the list copy is made in place, and swapping/moving is used instead of copying. – Necropolis

Answer 10

I think I would do the following...

for (auto itr = inv.begin(); itr != inv.end();)
{
   // Do some stuff
   if (OK, I decided I need to remove this object from 'inv')
      itr = inv.erase(itr);
   else
      ++itr;
}

Midge

Answer 11

you can't delete the iterator during the loop iteration because iterator count get mismatch and after some iteration you would have invalid iterator.

Solution: 1) take the copy of original vector 2) iterate the iterator using this copy 2) do some stuff and delete it from original vector.

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

std::vector<IInventory*> copyinv = inv;
iteratorCout = 0;
for (IInventory* index : copyinv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
    inv.erase(inv.begin() + iteratorCout);
    iteratorCout++;
}  

Furlough

Answer 12

Erasing element one-by-one easily leads to N^2 performance. Better to mark elements that should be erased and erase them at once after the loop. If I may presume nullptr in not valid element in your vector, then

std::vector<IInventory*> inv;
// ... push some elements to inv
for (IInventory*& index : inv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
    {
      delete index;
      index =nullptr;
    }
}
inv.erase( std::remove( begin( inv ), end( inv ), nullptr ), end( inv ) ); 

should work.

In case your "Do some stuff" is not changing elements of the vector and only used to make decision to remove or keep the element, you can convert it to lambda (as was suggested in somebody's earlier post) and use

inv.erase( std::remove_if( begin( inv ), end( inv ), []( Inventory* i )
  {
    // DO some stuff
    return OK, I decided I need to remove this object from 'inv'...
  } ), end( inv ) );

Roobbie