How to iterate on a changing dictionary

[Roy Smith]

In article <mailman.154.1308496441.1164.python-list at python.org>,
 Chris Angelico <rosuav at gmail.com> wrote:

> On Mon, Jun 20, 2011 at 12:32 AM, TheSaint <nobody at nowhere.net.no> wrote:
> > Hello
> >
> > Trying to pop some key from a dict while is iterating over it will cause an
> > exception.
> > How I can remove items when the search result is true.
> >
> > Example:
> >
> > while len(dict):
> >   for key in dict.keys():
> >      if dict[key] is not my_result:
> >         dict.pop(key)
> >    else:
> >       condition_to_break
> > print('Dictionary is over')
> 
> One way is to iterate over an explicitly formed list of the keys.
> 
> for key in list(dict.keys()):
> 
> That creates an entirely new list with a snapshot copy of the keys. If
> you then remove elements from the dictionary, the list will still
> iterate correctly.

If the dict is large and you only want to remove a relatively small 
number of keys, you could instead build up a list of keys to be deleted 
and do them in a second pass:

# pseudo-code
pending_keys = []
for key in dict.keys():
  if dict[key] is not my_result:
    pending_keys.append(key)
for key in pending_keys:
  del dict[key]

Yet another variation which makes sense if you want to delete most of 
the keys would be to copy them to a new dictionary.  I'm not sure how 
Python handles memory management on dictionaries which shrink.  I'm 
guessing it doesn't do anything about resizing the hash table downwards, 
so you end up with a lot of wasted space.  This solves that problem:

# pseudo-code
new_dict = {}
for key in dict.keys():
  if dict[key] is my_result:
    new_dict[key] = dict[key]

although you could improve on that with iteritems() instead of keys().

Of course, of all these, Chris Angelico's original code is the most 
straight-forward, and that's would I would use unless you had some 
strong reason to believe performance was an issue.