c++ - 迭代时从标准集中删除元素会导致无限循环

Question

以下代码产生以下输出，并以 100% cpu 负载的无限循环结束。

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

输出:

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

所以它没有完成，有 100% cpu 负载。
我知道如何正确地做到这一点(见下文)，但我无法理解这里发生了什么。这不是一个无限循环，从那时起它应该连续输出一些东西，但它只是不断地做一些事情。知道什么吗？
如何正确操作: Deleting elements from std::set while iterating和 How to remove elements from an std::set while iterating over it

Answer 1

好吧，所以您问这如何在不连续触发“检查对象”打印的情况下无限循环。
快速的答案(你已经从其他人那里得到)是调用 operator++在 my_set.end()是UB，因此可以做任何事情。
更深入地研究 GCC(因为@appleapple 可以在 GCC 上重现，而我在 MSVC 中的测试没有发现无限循环)揭示了一些有趣的东西:operator++ call 被实现为对 _M_node = _Rb_tree_increment(_M_node); 的调用。那个看起来如下:

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

因此，它默认通过第一个右侧找到“下一个”节点，然后一直运行到左侧。 但! 在调试器中查看 my_set.end()节点显示以下内容:

(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

end() 的左右两边节点显然指向自己。为什么？询问实现者，但可能是因为它使其他事情更容易或更可优化。但这确实意味着在您的情况下，您遇到的 UB 本质上是一个无限循环:

__x->_M_left = __x;

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

同样，GCC 就是这种情况，在 MSVC 上它没有循环(调试抛出异常，发布只是忽略它；完成循环并打印“循环完成”和“完成”，好像没有发生任何奇怪的事情)。但这就是关于 UB 的“有趣”部分——任何事情都有可能发生……