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

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_ = {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__时，迭代器就知道该去哪里，而不需要查看当前元素（它只需要在第一次到达该元素时查看）。如果没有下一个元素，迭代器可以设置一个标志，这样每当再次调用__next__时，就会引发StopIteration异常。

如果迭代器试图前进到的元素被删除了，抛出异常是可以的；在多个迭代同时进行时，没有必要支持删除操作。

这种方法有什么问题吗？

一个问题是，我不确定是否可以在与现有dict相比没有额外开销的情况下实现；否则，使用list(dict_)的方法会更快！

更新：

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

我真的很喜欢所有的想法，但由于我必须选择一个，所以我接受了上下文管理器的解决方案，因为它允许在非常小的代码更改下，将字典用作普通字典或“增强”字典。

Answer 1

你可以通过遍历一个静态的键值对列表来实现这个功能，而不是直接遍历字典的视图。

简单来说，就是用 list(dict_.items()) 来遍历，而不是用 dict_.items()，这样就可以了：

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

这里有一个例子（ideone）：

dict_ = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g'}
for k, v in list(dict_.items()):
    if k % 2 == 0:
        print("Deleting  ", (k, v))
        del dict_[k]
        continue
    print("Processing", (k, v))

输出结果是：

Deleting   (0, 'a')
Processing (1, 'b')
Deleting   (2, 'c')
Processing (3, 'd')
Deleting   (4, 'e')
Processing (5, 'f')
Deleting   (6, 'g')

Answer 2

你需要做的是，不要在遍历的过程中修改你正在查看的键的列表。你可以通过三种方式来做到这一点：

1. 把键复制到一个新的列表中，然后遍历这个新的列表。这样你就可以在遍历的时候安全地删除字典中的键。这是最简单、最快的方法，除非字典非常大，这种情况下你可能需要考虑使用数据库。代码：

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

2. 不是复制你正在遍历的键，而是复制你打算删除的键。换句话说，在遍历的时候不要删除这些键，而是把它们添加到一个列表中，等你遍历完再删除这个列表中的键。这比第一种方法稍微复杂一点，但比第三种方法简单得多，而且速度也很快。这就是你在第一个例子中所做的。

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

3. 避免创建新列表的唯一方法，正如你所说，是制作一个特殊的字典。但是这要求在你删除键的时候，实际上并不是真的删除，而只是标记为已删除，只有在你调用清除方法时才真正删除。这需要相当多的实现工作，并且会有一些边缘情况，你可能会因为忘记清除而出错。而且在遍历字典的时候，仍然需要包含已删除的键，这在某些时候会给你带来麻烦。所以我不推荐这种方法。而且，无论你在Python中如何实现，你很可能最终还是会得到一个待删除的键的列表，所以这可能只是第二种方法的一个复杂且容易出错的版本。如果你在C语言中实现，可能可以通过直接在哈希键结构中添加标志来避免复制。但如前所述，问题真的会掩盖好处。

Answer 3

正如你所提到的，你可以把要删除的项目先存放起来，然后再决定什么时候删除它们。这样的问题就变成了什么时候清理这些项目，以及如何确保清理的方法最终会被调用。解决这个问题的方法是使用一个上下文管理器，它也是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

如果你愿意，甚至可以让这个包装类完全像字典一样功能齐全，尽管这样代码会多一些。

从性能上来说，确实没有太大的优势，但我觉得从程序员友好的角度来看，这样做是不错的。第二种方法应该会稍微快一点，因为它在每次删除时不需要检查一个标志。