python - 为什么在迭代期间修改 dict 并不总是引发异常？

Question

从迭代中删除一个项目通常会导致RuntimeError: dictionary changed size during iteration异常:

d = {1: 2}
# exception raised
for k in d:
  del d[k]

更准确的说，删除本身会成功。然而，要进入下一轮迭代，解释器必须调用next(it)，其中it是一个迭代器，遍历它之前获得的字典。那时，next() 会注意到字典大小发生了变化，并发出提示。

到目前为止一切顺利。但是，如果我们同时删除和添加一个项目到字典中会怎样:

d = {1: 1}
# no exception raised
for k in d:
  # order of next two lines doesn't matter
  d[k*10] = k*10
  del d[k]

我几乎可以肯定这是不安全的(文档暗示在迭代期间既不允许插入也不允许删除)。为什么解释器允许这段代码无错误地运行？

我唯一的猜测是，每当调用插入或删除方法时检查哪些迭代器无效的代价太高。所以 dict 并没有试图完美地引发这个异常。相反，它只是跟踪每个迭代器内部字典的大小，并在实际要求迭代器移动到下一个项目时检查它是否没有改变。是否没有能够以低成本实现全面验证的方法？

Answer 1

确保在循环中尝试插入或删除键时引发异常的一种方法是维护对字典所做的修改次数。然后迭代器可以在它们的 __next__ 方法中检查那个数字没有改变(而不是验证字典大小没有改变)。

这段代码可以做到这一点。使用 SafeDict 或其 keys()/items()/values() 代理，循环变得安全意外插入/删除:

class SafeKeyIter:
    def __init__(self, iterator, container):
        self.iterator = iterator
        self.container = container
        try:
            self.n_modifications = container.n_modifications
        except AttributeError:
            raise RuntimeError('container does not support safe iteration')

    def __next__(self):
        if self.n_modifications != self.container.n_modifications:
            raise RuntimeError('container modified duration iteration')
        return next(self.iterator)

    def __iter__(self):
        return self


class SafeView:
    def __init__(self, view, container):
        self.view = view
        self.container = container

    def __iter__(self):
        return SafeKeyIter(self.view.__iter__(), self.container)

class SafeDict(dict):
    def __init__(self, *args, **kwargs):
        self.n_modifications = 0
        super().__init__(*args, **kwargs)

    def __setitem__(self, key, value):
        if key not in self:
            self.n_modifications += 1
        super().__setitem__(key, value)

    def __delitem__(self, key):
        self.n_modifications += 1
        super().__delitem__(key)

    def __iter__(self):
        return SafeKeyIter(super().__iter__(), self)

    def keys(self):
        return SafeView(super().keys(), self)

    def values(self):
        return SafeView(super().values(), self)

    def items(self):
        return SafeView(super().items(), self)

# this now raises RuntimeError:
d = SafeDict({1: 2})
for k in d:
    d[k * 100] = 100
    del d[k]

这看起来并不太昂贵，所以我不确定为什么它没有在 CPython dict 中实现。也许在字典上更新 n_modifications 的额外成本被认为太高了。