Removing item from vector, while in C++11 range 'for' loop?
Solution 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;
}
Solution 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()
);
Solution 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.
Solution 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);
Solution 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
Related videos on Youtube
EddieV223
Updated on September 09, 2020Comments
-
EddieV223 over 3 years
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 rangefor
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'... }
-
Benjamin Lindley about 12 yearsIf 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. -
TomJ about 12 yearsIs there a reason why you can't just add an index counter and then use something like inv.erase(index)?
-
Ben Voigt about 12 years@TomJ: That would still screw up the iteration.
-
Ivan about 12 years@TomJ and it would be a performance killer - on every erase, you get to move all elements after the erased one.
-
bobobobo about 11 years@BenVoigt
i--
after delete. Or iterate backwards with integer indices. -
Ben Voigt about 11 years@bobobobo: That still has O(N^2) complexity.
-
bobobobo about 11 years@BenVoigt I recommended switching to
std::list
below
-
-
Kiran Kumar about 12 yearsWouldn't erase-remove idiom applicable here ?
-
Seth Carnegie about 12 years@Naveen 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. -
ildjarn about 12 years"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 toerase
. The reason the iterators are invalidated is because each of the elements succeeding the erased element are moved. -
dirkgently about 12 years@ildjarn: Yep, true! That was a typo.
-
Potatoswatter about 12 years@SethCarnegie Erase-remove with a lambda for the predicate elegantly allows that (since this is already C++11)
-
Potatoswatter about 12 yearsThis isn't the erase-remove idiom. There is no call to
std::remove
, and it's O(N^2) not O(N). -
Potatoswatter about 12 yearsA capture-default of
[&]
would be appropriate, to allow him to "do some stuff" with local variables. -
dirkgently about 12 years@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?
-
Ben Voigt about 11 yearsI don't think you understand how
remove_if
on astd::vector
actually work, and how it keeps the complexity to O(N). -
Ben Voigt about 11 yearsDon't like this solution, it's O(N^2) for most containers.
remove_if
is better. -
bobobobo about 11 yearsThat 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 astd::list
a much better choice. -
Ben Voigt about 11 yearsNope, 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 astd::vector
likely outperforms removal from astd::list
. And preservesO(1)
random access. -
bobobobo about 11 yearsVery clever, but a removal at the front of a
std::vector
is stillO(N)
(memory sliding cost) any way you slice it, while astd::list
hasO(1)
removal for every case (change 2 pointers). -
Ben Voigt about 11 yearsThen 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.
-
bobobobo about 11 yearsThis 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. -
Branko Dimitrijevic about 11 years@bobobobo If by "iterator-based loop" you mean Seth Carnegie's answer, that is O(n^2) on average.
std::remove_if
is O(n). -
bobobobo about 11 yearsYou 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 avector
of 5 elements and you only.erase()
1 at a time, there is no performance impact for using iterators vsremove_if
. If the list is larger, you really should be switching tostd::list
where there's lots of middle-of-list removal. -
bobobobo about 11 yearsI 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. -
Branko Dimitrijevic about 11 years@bobobobo Unless you actually need random access.
-
Ben Voigt about 11 yearsPre-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.
-
Kolyunya over 10 yearsErasing 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?
-
magras over 9 years@Kolyunya No it's fine because he doesn't store end iterator.
-
swalog about 9 years@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? -
Ben Voigt about 9 years@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). -
Ben Voigt about 9 yearsI 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) -
Aconcagua about 8 yearsAlthough accepted, this answer is not correct - see my answer below!
-
sp2danny about 8 yearsthis answer is correct,
erase
returns a new valid iterator. it might not be efficient, but it's guaranteed to work. -
lilbigwill99 almost 7 yearsjust dont forget when using x to access a certain index, do x-1 lol
-
Kesse over 6 yearsWhat the heck. This is an overkill.
-
Aconcagua over 6 years@Kesse 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)? -
Francois Bertrand about 2 yearsI 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.
-
Francois Bertrand about 2 yearsI 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).