Erasing While Iterating an Std::List

Can you remove elements from a std::list while iterating through it?

You have to increment the iterator first (with i++) and then remove the previous element (e.g., by using the returned value from i++). You can change the code to a while loop like so:

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive)
    {
        items.erase(i++);  // alternatively, i = items.erase(i);
    }
    else
    {
        other_code_involving(*i);
        ++i;
    }
}

Removing from std::list while iterating

If the item you remove is the last item in the list, the erase method will return end(). Your for loop will then try to increment that iterator, which results in undefined behaviour.

Another problem which you haven't come across yet is that, if the item you remove isn't the last item in the list, you'll end up skipping over the following item (because the iterator is incremented past the one that erase returns). You can think of erase as an increment operation that just happens to erase the item first.

The solution is to refactor the loop slightly, to move the increment to the end (and only if erase wasn't called):

bool resetTypeBit = true;
for (auto it = eventsList.begin(); it != eventsList.end(); ) {
    CreatureEvent* curEvent = *it;
    if (curEvent == event) {
        it = eventsList.erase(it);
    }
    else {
        if (curEvent->getEventType() == type) {
            resetTypeBit = false;
        }
        ++it; // move the increment to here
    }
}

Erasing while iterating an std::list

The idiomatic way to write that loop would be:

for (auto i = list.begin(); i != list.end();) {
    if (condition)
        i = list.erase(i);
    else
        ++i;
}

You can do the same thing with a set, multiset, map, or multimap. For these containers you can erase an element without affecting the validity to any iterators to other elements. Other containers like vector or deque are not so kind. For those containers only elements before the erased iterator remain untouched. This difference is simply because lists store elements in individually allocated nodes. It's easy to take one link out. vectors are contiguous, taking one element out moves all elements after it back one position.

Your loop is broken because you erase the element at i on some given condition. i is no longer a valid iterator after that call. Your for loop then increments i, but i is not valid. Hell upon earth ensues. This is the exact situation that is why erase returns the iterator to the element after what was erased... so you can continue traversing the list.

You could also use list::remove_if:

list.remove_if([](auto& i) { return i > 10; });

In the lambda, return true if the element should be removed. In this example, it would remove all elements greater than 10.

Removing an element from a std::set while iterating over it in C++17

According to C++17 standard:

9.5.4 The range-based for statement [stmt.ranged]

1 The range-based for statement

for ( for-range-declaration : for-range-initializer ) statement

is equivalent to

{
    auto &&__range = for-range-initializer ;
    auto __begin = begin-expr ;
    auto __end = end-expr ;
    for ( ; __begin != __end; ++__begin )
    {
        for-range-declaration = *__begin;
        statement
    }
}

So no, your code is not valid, as you erase the element the iterator is currently pointing to (std::set can have only one value for the same key!), thus the iterator gets invalidated and is incremented afterwards, which is undefined behaviour.

Be aware that you could erase another element from set, as in std::set (as well as in std::map or std::list) only the iterator erased is invalidated whereas all others remain valid.

If you intend to remove the current element of a container (including std::vector, as erase returns a new, valid iterator), you need to fall back to a classic loop, as shown in the answer to referenced question; I personally like a one-liner variant of:

    iter = /*some condition*/ ? container.erase(iter) : std::next(iter);

C++ how to erase from vector while iterating

erase returns next iterator.

if ((*a) == 2)
{
    delete a;
    it = intList.erase(it);
}

EDIT:
remove() and remove_if() will copy the elements(pointer here) and one will end up with multiple elements pointing to same integer and if you then try to free them, you'll be left with dangling pointers.

Consider the vector has 4 elements which look something like

0x196c160 0x196bec0 0x196c180 0x196bee0 

One might be tempted to use erase-remove idiom

auto temp = remove_if(vec.begin(),vec.end(),[](const auto &i){return *i==2;});

Now it looks like

0x144aec0 0x144b180 0x144b180 0x144aee0

temp would be pointing to 3rd element and a

for(auto it=temp;it!=vec.end();it++)
    delete *it;

Now the second element is a dangling pointer.

EDIT 2:
The above problem could be solved if you delete before the element is copied.Look at @Dietmar's answer.

C++ std::list: Erasing / removing elements while iterating

Use postfix increment.

list.erase(it++);

it is increased, so it no longer refers to the erased element, then the previous value of it is given to list.erase. Make sure that you either do list.erase(it++) or ++it in your loop - doing both will skip elements and potentially increment past end of the list.

Deleting elements from std::set while iterating

This is implementation dependent:

Standard 23.1.2.8:

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

Maybe you could try this -- this is standard conforming:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

Note that it++ is postfix, hence it passes the old position to erase, but first jumps to a newer one due to the operator.

2015.10.27 update:
C++11 has resolved the defect. iterator erase (const_iterator position); return an iterator to the element that follows the last element removed (or set::end, if the last element was removed). So C++11 style is:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}

Remove an entry out of a std::list while iterator

You are skipping the element after the deleted one.

You should use either it = list.erase(it); or ++it, but not both.

How can I erase elements from a vector given a list of iterator?

Using the iterator version.
Note:

1. Iterators are invalidated only when there is a reallocation.
2. Just replace iterators with index does not change the fact that they are invalid when some values are removed from the vector.
3. Using indexes is still a better approach as they don't get invalidated when more elements are added later.

Approach:
Create a copy of vector with elements that should not be removed

using Element = std::string;
using RenderData = int;
struct Ref {
    std::vector<RenderData>::iterator itr;
    bool should_remove;
};

struct Main {
    std::vector<RenderData> ints;
    std::unordered_map<Element, Ref> elements;
    void remove_stuff(){
        std::vector<RenderData> localCopy;        
        localCopy.swap(ints);
        ints.reserve(localCopy.size());        
        for(auto it = elements.begin(); it != elements.end();) {
            Ref& ref = it->second;
            if(ref.should_remove) {
                it = elements.erase(it);
            } else {
                ints.push_back(std::move(*ref.itr));
                ref.itr = ints.end() - 1;                
                it++;
            }
        }            
    }
};

Link: https://godbolt.org/g/SouZ5E

C++ List Iteration and erasing

Member function erase deals with iterators.

For such a task it would be correctly to use an ordinary for loop. For example

for ( auto it = Objects.begin(); it != Objects.end(); )
{
    if ( it->EraseFlag ) it = Objects.erase( it );
    else ++it;
}

Another approach is to use member function remove_if. For example

Objects.remove_if( []( const auto &value ) { return value.EraseFlag; } );

---

Related Topics