Can You Remove Elements from a Std::List While Iterating Through It

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.

Can I remove elements from std::list, when I'm iterating on it?

The correct code is the following:

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); /*nothing*/)
{
    if (*itr > 10)
        itr = lst.erase(itr);
    else
        ++itr;
}

When you delete an item from the list, you may invalidate the iterator (if it points to the item being deleted.) Therefore you need to delete using erase (which returns a valid iterator pointing to the next item).

Even better idea would be using std::remove_if:

bool greater_than_10(int x)
{
    return x > 10;
}

lst.remove_if(greater_than_10);

If your compiler supports lambdas, you can put it even shorter:

lst.remove_if([](int x){ return x > 10; });

(I didn't test this code, as my compiler is not so new; the lambda function is thankfully stolen from @John Dibling's answer.)

Actually, erasing from list invalidates only the iterators pointing to the item being deleted. Beware however that other STL containers don't have this property.

So, in short: generally speaking, you should not delete the items from the list while iterating through it, because the deletion may invalidate the iterator (and the program will possibly crash). If you are however completely sure that the items which you delete are not the values referenced by any of the iterators which you use at the moment of deletion, you may delete.

Beware that for the other STL containers (e.g. vectors) the constraint is even more strict: deleting from the container invalidates not only iterators pointing to the deleted item, but possibly other iterators, too! So deleting from that containers while iterating through them is even more problematic.

How to remove items from a list while iterating?

You can use a list comprehension to create a new list containing only the elements you don't want to remove:

somelist = [x for x in somelist if not determine(x)]

Or, by assigning to the slice somelist[:], you can mutate the existing list to contain only the items you want:

somelist[:] = [x for x in somelist if not determine(x)]

This approach could be useful if there are other references to somelist that need to reflect the changes.

Instead of a comprehension, you could also use itertools. In Python 2:

from itertools import ifilterfalse
somelist[:] = ifilterfalse(determine, somelist)

Or in Python 3:

from itertools import filterfalse
somelist[:] = filterfalse(determine, somelist)

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.

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);

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

The problem is, after erase_after the iterator to the erased element, i.e. it becomes invalid; performing ++it later leads to UB.

erase_after returns the iterator to the element following the erased one, you can assign it to it. (And move ++it into the for statement to control it manually.)

typedef std::forward_list<int>::iterator IT;

IT before = m.before_begin();

for ( IT it = m.begin(); it != m.end(); )
{
    std::cout << *it;

    if ( *it % 2 == 0 )
    {
        it = m.erase_after( before );
    } 
    else
    {
        before = it;
        ++it;
    }

}

LIVE

Is it safe to delete elements in a Set while iterating with for..of?

Yes, it is perfectly fine to add elements and remove elements to a set while iterating it. This use case was considered and is supported in JavaScript 2015 (ES6). It will leave it in a consistent state. Note this also applies to itearting with forEach.

Intuitively:

The set iteration algorithm basically looks something like this:

Set position to 0
While position < calculateLength() // note it's calculated on each iteration
    return the element at set.entryList[position]

Addition just looks something like this:

If element not in set
   Add element to the _end_ of the set

So it does not interfere with existing iterations - they will iterate it.

Deletion looks something like this:

Replace all elements with are equal to `element` with a special empty value

Replacing it with an empty value rather than deleting it ensures it will not mess up with iterators' positions.

Formally

Addition

Here is the relevant part of the specification from %SetIteratorPrototype%.next:

Repeat while index is less than the total number of elements of entries. The number of elements must be redetermined each time this method is evaluated.

The set iterator proceeds to iterate the entries one by one.

From Set.prototype.add:

Append value as the last element of entries.

This ensures that when adding elements to the list it will be iterated before the iteration completes since it always gets a new slot in the entries list. Thus this will work as the spec mandates.

As for deletion:

Replace the element of entries whose value is e with an element whose value is empty.

Replacing it with an empty element rather than removing it ensures that the iteration order of existing iterators will not get out or order and they will continue iterating the set correctly.

With code

Here is a short code snippet that demonstrates this ability

var set = new Set([1]);
for(let item of set){
   if(item < 10) set.add(item+1);
   console.log(item);
}

Which logs the numbers 1 to 10. Here is a version not using for... of you can run in your browser today:

var set = new Set([1]);for (var _i = set[Symbol.iterator](), next; !(next = _i.next()).done;) {   var item = next.value;   if (item < 10) set.add(item + 1);   document.body.innerHTML += " " + item;}

for(auto &it: l){
    l.erase(*it);
}

for(int &it: l){
    l.erase(*it);
}

{
    auto cur = container.begin() ;
    auto end = container.end();
    for ( ; cur != end; ++cur) 
    {
        auto val = *cur;
        do_stuff 
    }
}

l.erase(l.remove(5), l.end()); // remove all elements containing the number 5