2

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

Improve this question
5
  • 1
    Read this: stackoverflow.com/questions/6438086/iterator-invalidation-rules. As soon as an iterator is invalidated using it is undefined bahaviour. Commented Jul 14, 2021 at 7:38
  • 3
    You are calling ++ for end iterator - undefined behaviour. if(ob == tmp_ob) { // ... } else ++setIt; and for(setIt = my_set.begin(); setIt != my_set.end(); ) Commented Jul 14, 2021 at 7: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? Commented Jul 14, 2021 at 7:45
  • 1
    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) Commented Jul 14, 2021 at 7:45
  • 1
    can reproduce wandbox.org/permlink/HqeFmKORjCyflAs3 Commented Jul 14, 2021 at 8:09

3 Answers 3

Reset to default
3

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

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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 undefined behaviour is undefined.
@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.
0

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.

Improve this answer

1 Comment

Makes sense, but I do not understand why cout is not continuing output then
-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++; }
Improve this answer

3 Comments

I don't see how this answer the OP question, OP knows that the code is using an invalidated iteratator
How does this answer the question??
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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.