允许在迭代期间删除的自定义字典

Question

根据Lennart Regebro的回答进行更新

假设您遍历字典，有时需要删除一个元素。以下是非常有效的：

remove = []
for k, v in dict_.items():
  if condition(k, v):
    remove.append(k)
    continue
  # do other things you need to do in this loop
for k in remove:
  del dict_[k]

唯一的开销是构建要删除的密钥列表；除非与字典大小相比变大，否则这不是问题。但是，这种方法需要一些额外的编码，因此它不是很流行。

流行的dict理解方法：

dict_ = {k : v for k, v in dict_ if not condition(k, v)}
for k, v in dict_.items():
  # do other things you need to do in this loop

会导致完整的字典副本，因此，如果字典变大或经常调用包含函数，则可能会导致愚蠢的性能下降。

更好的方法是只复制键而不是整个字典：

for k in list(dict_.keys()):
  if condition(k, dict_[k]):
    del dict_[k]
    continue
  # do other things you need to do in this loop

（请注意，所有代码示例均在Python 3中进行，因此keys()，items()将返回视图，而不是副本。）

在大多数情况下，它不会对性能造成太大影响，因为检查最简单条件的时间（更不用说您在循环中正在做的其他事情）通常比将一个键添加到列表的时间更长。

我仍然想知道是否有可能使用允许在迭代时删除的自定义词典来避免这种情况：

for k, v in dict_.items():
  if condition(k, v):
    del dict_[k]
    continue
  # do other things you need to do in this loop

也许迭代器可以始终向前看，以便在__next__调用时，迭代器无需查看当前元素就知道要去哪里（它只需要在首次到达该元素时便要查看该元素）。并且如果没有下一个元素，则迭代器可以仅设置标志，该标志将导致StopIteration在__next__再次调用时引发异常。

如果迭代器尝试前进到的元素最终被删除，则引发异常是可以的；同时进行多次迭代时，无需支持删除。

这种方法有什么问题吗？

一个问题是，我不确定与现有技术相比，没有任何实质性开销就能做到dict；否则，使用该list(dict_)方法会更快！

更新：

我尝试了所有版本。我不报告时间安排，因为它们显然非常依赖于具体情况。但是可以肯定地说，在许多情况下，最快的方法可能是list(dict_)。毕竟，如果您考虑一下，副本是最快的操作，它随着列表的大小线性增长。只要与列表大小成正比，几乎任何其他开销都可能更大。

我真的很喜欢所有想法，但是由于我只需要选择一个想法，因此我接受上下文管理器解决方案，因为它允许通过很小的代码更改就可以将字典用作普通字典或“增强”字典。

Answer 1

如您所述，您可以将要删除的项目存储在某处，并将其删除推迟到以后。然后，问题就变成了 何时 清除它们以及 如何
确保最终调用清除方法。答案是上下文管理器，它也是的子类dict。

class dd_dict(dict):    # the dd is for "deferred delete"
    _deletes = None
    def __delitem__(self, key):
        if key not in self:
            raise KeyError(str(key))
        dict.__delitem__(self, key) if self._deletes is None else self._deletes.add(key)
    def __enter__(self):
        self._deletes = set()
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                dict.__delitem__(self, key)
            except KeyError:
                pass
        self._deletes = None

用法：

# make the dict and do whatever to it
ddd = dd_dict(a=1, b=2, c=3)

# now iterate over it, deferring deletes
with ddd:
    for k, v in ddd.iteritems():
        if k is "a":
            del ddd[k]
            print ddd     # shows that "a" is still there

print ddd                 # shows that "a" has been deleted

with当然，如果您不处于阻塞状态，则立即删除。因为这是一个dict子类，所以它就像dict上下文管理器外部的常规对象一样工作。

您还可以将其实现为字典的包装类：

class deferring_delete(object):
    def __init__(self, d):
        self._dict = d
    def __enter__(self):
        self._deletes = set()
        return self
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                del self._dict[key]
            except KeyError:
                pass
        del self._deletes
    def __delitem__(self, key):
        if key not in self._dict:
            raise KeyError(str(key))
        self._deletes.add(key)

d = dict(a=1, b=2, c=3)

with deferring_delete(d) as dd:
    for k, v in d.iteritems():
        if k is "a":
            del dd[k]    # delete through wrapper

print d

如果需要的话，甚至可以使包装器类作为字典完全发挥作用，尽管这是更多的代码。

从性能角度来看，这当然不是一个胜利，但是从程序员友好的角度来看，我喜欢它。第二种方法应该稍微快一点，因为它没有在每次删除时测试标志。