Deleting elements from std set while iterating leads to endless loop

Question

The following code produces the following output and ends up in kind of an endless loop with 100% cpu load.

#include <iostream>
#include <set>

class Foo{};

void delete_object_from_set(std::set<Foo *>& my_set, Foo* ob)
{
    std::set< Foo *>::iterator setIt;

    std::cout << "Try to delete object  '" << ob << "'..." << std::endl;

    for(setIt = my_set.begin(); setIt != my_set.end(); ++setIt)
    {
        Foo * tmp_ob = *setIt;
        std::cout << "Check object '" << tmp_ob << "'..." << std::endl;
        // compare the objects
        //
        if(ob == tmp_ob)
        {
            // if the objects are equal, delete this object from the set
            //
            std::cout << "Delete object '" << tmp_ob << " from set..." << std::endl;
            setIt = my_set.erase(setIt);
            std::cout << "Deleted object '" << tmp_ob << " from set..." << std::endl;
        }
    }
    std::cout << "loop finished."  << std::endl;    
};

int main()
{
  Foo* ob = new Foo();
  std::set< Foo * > my_set;
  my_set.insert(ob);

  delete_object_from_set(my_set, ob);

  std::cout << "finished" << std::endl;
  return 0;
}

The output:

Try to delete object  '0x563811ffce70'...
Check object '0x563811ffce70'...
Delete object '0x563811ffce70 from set...
Deleted object '0x563811ffce70 from set...

so it does not finish, having 100% cpu load.

I know how to do it correctly (see below), but I cannot understand what is going on here. It's not an endless loop, since then it should output something continuously, but it just keeps doing something. Any idea what?

How to do it the right way: Deleting elements from std::set while iterating and How to remove elements from an std::set while iterating over it

Read this: https://stackoverflow.com/questions/6438086/iterator-invalidation-rules. As soon as an iterator is invalidated using it is undefined bahaviour. — Jabberwocky, Jul 14 '21 at 07:38
You are calling `++` for `end` iterator - undefined behaviour. `if(ob == tmp_ob) { // ... } else ++setIt;` and `for(setIt = my_set.begin(); setIt != my_set.end(); )` — rafix07, Jul 14 '21 at 07:39
Thanks, but why does that end up in 100% cpu load and no output anymore? Can one say what the cpu is doing all the time? — Lucker10, Jul 14 '21 at 07:45
perhaps, launching a rocket most likely the operator++() in your set implementation goes in an infinite loop. If you are using gcc you may be able to find the source code for it (not sure about other compilers) — Alessandro Teruzzi, Jul 14 '21 at 07:45

score 3 · Accepted Answer · answered Jul 14 '21 at 09:33

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...

Great Answer. I never thought about the possibility that a increment operator could cause an infinite loop at all. And funny that its compiler specific as well. Thank you! Enlightened me and my understanding of c++ — Lucker10, Jul 14 '21 at 10:13
@Lucker10 on minGW64 it hits debugger trap on increment and hanged there for me. If ran from Qt Creator IDE it would show instruction where INT 3 was called. Wandbox build likely did something like that and killed process automatically. — Swift - Friday Pie, Jul 14 '21 at 20:40

score 0 · Answer 2 · answered Jul 14 '21 at 08:37

The code is equivalent of:

{
   setIt = my_set.begin(); 
   while(setIt != my_set.end())
   {
        Foo * tmp_ob = *setIt;
        std::cout << "Check object '" << tmp_ob << "'..." << std::endl;

        if(ob == tmp_ob)
        {

            std::cout << "Delete object '" << tmp_ob << " from set..." << std::endl;
            setIt = my_set.erase(setIt);
            std::cout << "Deleted object '" << tmp_ob << " from set..." << std::endl;
        }

      ++setIt;
   }
}

The call to my_set.erase(setIt); may return end() if last element of container was deleted. Consequently increments happens, which is UB. Would it trigger exception or not depends on implementation, but at any following point setIt never will be equal to my_set.end(), thus an infinite loop is possible.

Makes sense, but I do not understand why `cout` is not continuing output then — Lucker10, Jul 14 '21 at 09:08

score -1 · Answer 3 · answered Jul 14 '21 at 07:41

-1

for(setIt = my_set.begin(); setIt != my_set.end();)
{
    Foo * tmp_ob = *setIt;
    std::cout << "Check object '" << tmp_ob << "'..." << std::endl;
    // compare the objects
    //
    if(ob == tmp_ob)
    {
        // if the objects are equal, delete this object from the set
        //
        std::cout << "Delete object '" << tmp_ob << " from set..." << std::endl;
        setIt = my_set.erase(setIt);
        std::cout << "Deleted object '" << tmp_ob << " from set..." << std::endl;
    }
    else
        setIt++;

}

answered Jul 14 '21 at 07:41

John Guo

11
1

I don't see how this answer the OP question, OP knows that the code is using an invalidated iteratator – Alessandro Teruzzi Jul 14 '21 at 07:43
How does this answer the question?? – Jabberwocky Jul 14 '21 at 07:43
my_set.erase(setIt) return the iterator next to the erased iterator, and if this iterator is the end of the iteration , the loop end setIt++ will cause the endless loop. – John Guo Jul 15 '21 at 04:04

Deleting elements from std set while iterating leads to endless loop

3 Answers3