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

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

所以它没有完成，CPU 负载为 100%。

我知道如何正确执行此操作(见下文)，但我无法理解这里发生的情况。这不是一个无限循环，从那时起它应该连续输出一些东西，但它只是不断地做一些事情。知道什么吗？

如何正确操作:Deleting elements from std::set while iterating和 How to remove elements from an std::set while iterating over it

Answer 1

Hokay，所以你问这如何无限循环而不连续触发“检查对象”打印。

快速回答(您已经从其他人那里得到了)是在 my_set.end() 上调用 operator++ 是 UB，因此能够执行任何操作。

对 GCC 的深入研究(因为 @appleapple 可以在 GCC 上重现，而我在 MSVC 中的测试发现没有无限循环)揭示了一些有趣的东西:

operator++ 调用是作为对 _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 的“有趣”部分 - 任何事情都可能发生......