c++ - 为什么删除元素的 std::for_each 不会中断迭代？

Question

据我所知，在集合迭代期间删除元素会破坏迭代或导致您跳过元素。为什么使用删除的谓词调用 std::for_each 不会导致这种情况发生？ (有效)。

代码片段:

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    map<int,long long> m;
    m[1] = 5000;
    m[2] = 1;
    m[3] = 2;
    m[4] = 5000;
    m[5] = 5000;
    m[6] = 3;

    // Erase all elements > 1000
    std::for_each(m.begin(), m.end(), [&](const decltype(m)::value_type& v){
        if (v.second > 1000) {
            m.erase(v.first);
        }
    });

    for (const auto& a: m) {
      cout << a.second << endl;
    }
    return 0;
}

打印出来

1
2
3

编辑:我现在看到 if 它实际上在调用函数之前递增迭代器然后它可以工作。但这是否算作编译器特定/未定义的行为？

Answer 1

这是未定义的行为，不会可靠地工作。在删除 lambda 函数中添加一行以打印键和值后，我看到:

1=5000
2=1
3=2
4=5000
2=1          // AGAIN!!!
3=2          // AGAIN!!!
5=5000
6=3

使用我的标准库的 map 实现，在删除键为 4 的元素后，迭代返回键为 2 的节点!然后它重新访问具有键 3 的节点。因为您的 lambda 愉快地重新测试了这些节点 (v.second > 1000) 并且返回时没有任何副作用，所以中断的迭代不会影响输出。

您可能会合理地问:“但从天文角度来看，它在不崩溃的情况下设法继续迭代(即使到错误的下一个节点)是不可能的吗？”

实际上，很有可能。

删除节点会导致为该节点占用的内存调用delete，但通常执行delete的库代码只会:

• 调用析构函数(没有特别的理由浪费时间覆盖左子指针、右子指针和父指针)，然后

• 修改其关于已分配内存区域与可用内存区域的记录。

不太可能“浪费”时间任意修改正在释放的堆内存(尽管某些实现会处于内存使用 Debug模式)。

因此，被删除的节点可能原封不动地坐在那里，直到执行其他一些堆分配。

并且，当您erase map 中的一个元素时，标准要求容器中的任何其他元素都不能在内存中移动 - 迭代器、指针和对其他元素的引用元素必须保持有效。它只能修改维护二叉树的节点的左/右/父指针。

因此，如果您继续对已删除元素使用迭代器，则很可能会看到指向已删除元素在删除之前链接到的左/右/父节点的指针，以及 operator++()将使用与删除的元素仍在 map 中时所采用的相同逻辑“迭代”它们。

如果我们考虑示例 map 的内部二叉树，其中 N3 是具有键 3 的节点:

                           N5
                          /  \
                        N3    N7
                       / \    /
                      N1  N4 N6

完成迭代的方式可能是:

• 最初，从 N1 开始； map 必须直接跟踪它的位置以确保 begin() 是 O(1)

• 如果在一个没有子节点的节点上，重复 { Nfrom = where you are, move to parent, if nullptr or right != Nfrom break} (e.g. N1->N3, N4->N3->N5, N6->N7->N5->nullptr)

• 如果在一个有右手 child 的节点上，那么取它任意数量的左手链接(例如 N3->N4，N5->N7->N6)

所以，如果说 N4 被移除(所以 N3->right = nullptr;)并且没有重新平衡发生，那么迭代记录 NFrom=N4 然后移动到父 N3，然后 N3->right != Nfrom，所以它会认为它应该停止在已经迭代的 N3 上，而不是继续前进到 N5。

另一方面，如果在 erase 之后树已经重新平衡，则所有赌注都将关闭，无效的迭代器可能会重复或跳过元素，甚至“按希望”迭代。

这不是旨在让您推断erase 后的行为 - 它未定义，不应依赖。相反，我只是想展示一个理智的实现可以解释您的意外观察结果。