为什么在迭代期间修改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]

我几乎可以肯定这不安全(文档暗示在迭代期间不允许插入或删除).为什么解释器允许此代码无错运行？

我唯一的猜测是,每当调用insert或delete方法时,检查哪些迭代器无效是太昂贵了.所以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字典的额外成本被认为太高了。

Answer 2

是否没有一种方法能够以低成本实现全面验证？

以下是Alex Martelli对此主题的相关评论。

因为容器甚至不跟踪其上的迭代器，更不用说挂钩甚至 altering-method 来循环每个这样的迭代器，并以某种方式神奇地让每个迭代器知道更改。这将是很多微妙、复杂的代码，并且检查会减慢非常频繁的操作

因此，至少根据核心 Python 开发人员的说法，我们无法以低成本进行全面验证。