Deleting Elements from Std::Set While Iterating

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

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

Most efficient way to erase from a set while iterating over it

It is undefined behaviour to erase from a set within a ranged-based for loop (even if it appears to work). Ranged-based for loops use an iterator internally and erasing the element invalidates the iterator.

But std::set::erase returns a valid iterator to the next element in the std::set so you can use an explicit iterator loop instead:

for(auto itr = files.cbegin(); itr != files.cend();) {
  if (exists(*itr)) {
    std::cout << "Found file: " << *itr << "\n";
    itr = files.erase(itr);
  } else
    ++itr;
}

Live demo.

erase set element while iterating///

So just to explain further,

What you effectively have written is:

for (set<int>::const_iterator i=sset.begin(), e=sset.end(); i != e; i++)
{
    auto s = *i;
    sset.erase(s);
}

So the issue is that on doing the erase, the internal iterator i becomes invalidated. This is a general pain with trying to sequentially delete the content of many of the containers.

The following more traditional sequential delete code is also bad for the same reason, but perhaps more obviously:

for (set<int>::iterator i=sset.begin(), e=sset.end(); i != e; i++)
{
    sset.erase(i);
}

Fixes:

Generally, it is simpler to rely on context swap destruction of the whole container, when you can:

C++98: SsetType().swap(sset); 
C++11: sset = decltype<sset>();

And you could just do:

sset.erase(sset.begin(), sset.end());

Another way to fix this is to just keep deleting the begin() until the set is empty()

But the problem with all of these is you can't easily extend them to conditionally erase members of a set you are iterating through. Yes, there are helpers for conditional erase as well, and they can be used with lambdas, so they can carry state, but they generally tend to be as hard to use as rolling your own loop.

Since c++11, set::erase(iterator) returns a new iterator which is safe to continue iterating with, so you can write:

for (set<int>::iterator i=sset.begin(), e=sset.end(); i != e; )
{
    i = sset.erase(i);
}

If you were performing some conditional test, then:

for (set<int>::iterator i=sset.begin(), e=sset.end(); i != e; )
{
    if ( ... condition ... )
        i = sset.erase(i);
    else
        i++;
}

before, in c++98, you would have written something like:

for (set<int>::iterator i=sset.begin(), e=sset.end(); i != e; )
{
    auto j = i;
    j++;
    if ( ... condition ... )
        i = sset.erase(i);
    i = j;
}

As an exercise, you can roll the use of j into the for statement. getting the initial j++ in C98 is tricky, though!

How to remove elements from an std::set while iterating over it

Standard way is to do something like

for(set<T>::iterator iter = s.begin(); iter != s.end();)
{
   if(/*some condition*/)
   {
      s.erase(iter++);
   }
   else
   {
      ++iter;
   }
}

By the first condition we are sure, that iter will not be invalidated anyway, since a copy of iter will be passed into erase, but our iter is already incremented, before erase is called.

In C++11, the code will be like

for(set<T>::iterator iter = s.begin(); iter != s.end();)
{
   if(/*some condition*/)
   {
      iter = s.erase(iter);
   }
   else
   {
      ++iter;
   }
}

Deleting elements from std set while iterating leads to endless loop

Hokay, so you asked how this could loop infinitely without continuously triggering the "Check object" print.

The quick answer (that you already got from others) is that calling operator++ on my_set.end() is UB, and thus able to do anything.

A deeper dive into GCC specifically (since @appleapple could reproduce on GCC, while my test in MSVC found no infinite loop) revealed some interesting stuff:

The operator++ call is implemented as a call to _M_node = _Rb_tree_increment(_M_node); and that one looks as follows:

static _Rb_tree_node_base*
local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
    if (__x->_M_right != 0)
        {
            __x = __x->_M_right;
            while (__x->_M_left != 0)
                __x = __x->_M_left;
        }
    else
        {
            _Rb_tree_node_base* __y = __x->_M_parent;
            while (__x == __y->_M_right)
                {
                    __x = __y;
                    __y = __y->_M_parent;
                }
            if (__x->_M_right != __y)
                __x = __y;
        }
    return __x;
}

So, it defaults to finding the "next" node by taking the first right, and then running all the way to the left. But! a look in the debugger at the my_set.end() node reveals the following:

(gdb) s
366             _M_node = _Rb_tree_increment(_M_node);
(gdb) p _M_node
$1 = (std::_Rb_tree_const_iterator<Foo*>::_Base_ptr) 0x7fffffffe2b8
(gdb) p _M_node->_M_right
$2 = (std::_Rb_tree_node_base::_Base_ptr) 0x7fffffffe2b8
(gdb) p _M_node->_M_left
$3 = (std::_Rb_tree_node_base::_Base_ptr) 0x7fffffffe2b8

Both the left and right of the end() node apparently points at itself. Why? Ask the implementer, but probably because it makes something else easier or more optimizable. But it does mean that in your case the UB you run into is an infinite loop on essentially:

__x->_M_left = __x;

while (__x->_M_left != 0)
  __x = __x->_M_left;  // __x = __x;

Again, this is the case for GCC, on MSVC it did not loop (debug threw an exception, release just ignored it; finished the loop and printed "loop finished." and "finished" as if nothing strange had happened). But that is the "fun" part about UB - anything could happen...

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

int finalSize = 0;
for(int i = 0; i < N; i++)
{
        if(result[i] != 0) {
                result[finalSize++] = i;
        }
}
result.resize(finalSize);

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

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

0x196c160 0x196bec0 0x196c180 0x196bee0 

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

0x144aec0 0x144b180 0x144b180 0x144aee0

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