Deleting elements from std set while iterating leads to endless loop

user_4270676 0
Viewed 160

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

c++
3 Answers

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

user_118292470

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.

user_27427170 
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++;

}
user_116816790
Related