ES6: 在Set/Map迭代期间删除元素是否危险？

Question

new Set() 的安全代码可能看起来像：

let items = [];
for (let item of set)
  if (isBad(item))
    items.push(item);
for (let item of items)
  set.delete(item)

我能简化代码为：

for (let item of set)
  if (isBad(item))
    set.delete(item);

使用 new Map() 的安全代码可能如下:

let keys = [];
for (let [key, val] of map)
  if (isBadKey(key) || isBadValue(val))
    keys.push(key);
for (let key of keys)
  map.delete(key)

我可以简化代码为：

for (let [key, val] of map)
  if (isBadKey(key) || isBadValue(val))
    map.delete(key)

- gavenkoa

Answer 1

可以这样简化，完全安全。

• Sets和Maps始终按插入顺序迭代
• 删除项目不会影响任何迭代器的位置 - 您可以将集合的形状视觉化为未更改，只是被清空了。
• 因此：已删除但尚未迭代的元素将不会被迭代
• 已经迭代并被删除的元素（就像您的情况一样）不会影响其他迭代/查找，但不会影响其他迭代/查找
• 在迭代期间添加并且不是集合的一部分的元素将始终被迭代

从最后一点得出的结论是唯一危险的事情是做类似于

const s = new Set([1]);
for (let x of s) {
    s.delete(x);
    s.add(1);
}

但不是因为未定义的行为或内存累积，而是因为无限循环。

- Bergi

---

请提供一个参考文献链接来支持你的陈述。 - jtbandes

@jtbandes 我不知道有任何文件明确说明这一点（你可以尝试查看 MDN），但我的回答中的结论直接遵循规范中集合的可观察语义（http://ecma-international.org/ecma-262/#sec-keyed-collections）作为条目列表。 - Bergi

在Map#forEach规范下有一条注释，内容类似。 - wOxxOm

因为标题是以“是否危险”开始的，所以你应该说“是的，很安全”，而不仅仅是“是的”。 - Cinn

Answer 2

我认为是安全的。当你使用for ... of迭代Set/Map时，在底层循环会通过@@iterator进行遍历。而Iterator仅使用.next()：因此没有索引，也不管当前位置之前的内容。只有下一个元素是重要的。

因此，在你删除当前迭代器位置之前的元素之前，这样做是安全的。

- Kiril

---

如果Set()被实现为二叉树，会发生什么？删除节点可能会导致树重新平衡。这会影响迭代器操作吗？ - gavenkoa

这并不是根据规范，Set内部更像是一个List： 设置set的[[SetData]]内部插槽为一个新的空列表。 - Kiril

规范仅定义所需的行为，而不是实现方式。例如，实现可以将其实现为具有插入顺序链接集条目的哈希集，从而实现摊销O（1）查找，同时保持可预测的顺序，以实现定义的行为。 - the8472

@gavenkoa 关于删除 - 它的时间复杂度是 O(size)。 - Kiril

根据规范，根据@Bergi所说 - 是的：对于每个条目中的元素e重复执行 - 因此需要遍历所有条目进行一次循环。但是，这当然只有在按照规范实现时才会生效。 - Kiril