Python dictionary: iterating and adding

On one of my earlier articles about Python dictionaries Jay asks (I paraphrase): What if you want to add items to a dictionary whilst iterating? And what if you want those items to appear in the iteration? Python’s standard dictionary iterators won’t help you.

Here’s a plan:

1. keep a set, visited of keys that you have already visited;
2. get the set of keys from the dictionary and subtract visited, leaving you with a set of keys not yet visited, todo;
3. visit each of the keys in todo;
4. now we have visited each of the keys in todo, add those keys to visited;
5. during the iteration the set of keys in the dictionary may have changed, so repeat from (2), stopping when todo is empty.

def iterall(adict):
    """Iterate over all the items in a dictionary,
    including ones which are added during the iteration.
    """
    visited = set()
    while True:
        todo = set(adict.keys()) - visited
        if not todo:
            break
        for k in todo:
            if k in adict:
                yield k, adict[k]
        visited |= todo

Here it is in use:

>>> d=dict(a=1,b=2)
>>> for k,v in iterall(d):
...     print k,v
...     d['c'+k[0]] = 'new'
... 
a 1
b 2
cb new
ca new
cc new

Python’s set datatype makes this easy to program and it has reasonable performance.

Obligatory Python whinge: The function implemented above, iterall, is effectively a new method that I’ve implemented for the dict class. But I can’t add a new method to a class that someone else implemented. Unlike, say, Common Lisp, Dylan, Smalltalk, and Objective-C, where I can.

About these ads