custom dict that allows delete during iteration

As you note, you can store the items to delete somewhere and defer the deletion of them until later. The problem then becomes when to purge them and how to make sure that the purge method eventually gets called. The answer to this is a context manager which is also a subclass of 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

Usage:

# make the dict and do whatever to itddd = dd_dict(a=1, b=2, c=3)# now iterate over it, deferring deleteswith ddd:    for k, v in ddd.iteritems():        if k is "a":            del ddd[k]            print ddd     # shows that "a" is still thereprint ddd                 # shows that "a" has been deleted

If you're not in a with block, of course, deletes are immediate; as this is a dict subclass, it works just like a regular dict outside of a context manager.

You could also implement this as a wrapper class for a dictionary:

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 wrapperprint d

It's even possible to make the wrapper class fully functional as a dictionary, if you want, though that's a fair bit more code.

Performance-wise, this is admittedly not such a win, but I like it from a programmer-friendliness standpoint. The second method should be very slightly faster since it's not testing a flag on each delete.

What you need to do is to not modify the list of keys you iterating over. You can do this in three ways:

1. Make a copy of the keys in a separate list and iterate over that. You can then safely delete the keys in the dictionary during iteration. This is the easiest, and fastest, unless the dictionary is huge in which case you should start thinking about using a database in any case. Code:

   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. Make a copy not of the keys you are iterating over, but a copy of the keys you are to delete. In other words, don't delete these keys while iterating instead add them to a list, then delete the keys in that list once you are finished iterating. This is slightly more complicated than 1. but much less than 3. It is also fast. This is what you do in your first example.

   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 loopfor k in delete_these:    del dict_[k]

3. The only way to avoid making some sort of new list is, as you suggest, to make a special dictionary. But that requires when you delete keys it does not actually delete the keys, but only mark them as deleted, and then delete them for real only once you call a purge method. This requires quite a lot of implementation and there are edge-cases and you'll fudge yourself by forgetting to purge, etc. And iterating over the dictionary must still include the deleted keys, which will bite you at some point. So I wouldn't recommend this. Also, however you implement this in Python, you are likely to just once again end up with a list of things to delete, so it's likely to just be a complicated and error prone version of 2. If you implement it in C, you could probably get away with the copying by adding the flags directly into the hash-key structure. But as mentioned, the problems really overshadow the benefits.

You can accomplish this by iterating over a static list of the key/value pairs of the dictionary, instead of iterating over a dictionary view.

Basically, iterating over list(dict_.items()) instead of dict_.items() will work:

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

Here is an example (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))

and the output:

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