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

IT技术 javascript ecmascript-6
2021-02-21 18:54:02

的安全代码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)
2个回答

是的,您可以简化为,这是完全安全的。

  • Sets 和 Maps 总是按插入顺序迭代
  • 删除一个项目不会影响任何迭代器的位置——你可以想象集合的形状没有被改变,只是被清空。
  • 所以:被删除且尚未迭代的元素不会被迭代
  • 已经迭代并被删除的元素(如您的情况)不会影响任何其他迭代/查找。
  • 在迭代期间添加的元素(并且还不是集合的一部分)将始终被迭代

从最后一点可以看出,唯一危险的事情就是这样

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

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

你应该说“是的,它是安全的”而不是“是的”,因为标题以“它是否危险......”开头。
2021-04-16 18:54:02
Map#forEach规范下有一个注释说类似的事情。
2021-04-20 18:54:02
@jtbandes 我不知道有任何文档准确地说明了这一点(但是,您可能想尝试 MDN),我的答案中的结论直接遵循规范中集合可观察语义作为条目列表。
2021-04-28 18:54:02
您能否添加一个链接到参考文档以证实您的陈述?
2021-05-05 18:54:02

我会说是的,这是安全的。当您在后台使用 Set/Map 迭代时,for ... of循环将通过@@iterator并且Iterator.next()操作:所以没有索引,无论当前位置之前是什么。只有一个下一个元素是重要的。

因此,直到您删除当前迭代器位置“前面”的元素 - 这样做是安全的。

如果Set()实现为二叉树呢?删除节点可能会导致树重新平衡。它会破坏迭代器操作吗?
2021-04-18 18:54:02
不是。根据规范 - 内部Set更像是一个ListSet set's [[SetData]] internal slot to a new empty List.
2021-04-20 18:54:02
@Bergi,根据规范 -是的Repeat for each e that is an element of entries,- 所以对所有条目进行一次循环。但是,当然,前提是它是根据规范实现的。
2021-05-04 18:54:02
@gavenkoa 关于删除 - 它是O(size)
2021-05-06 18:54:02
规范只定义了所需的行为,而不是应该如何实现。例如,实现可以通过将其实现为具有插入顺序链接集条目的散列集来实现定义的行为,从而在保持可预测顺序的同时实现分摊 O(1) 查找。
2021-05-12 18:54:02