In Python, how do I iterate over a dictionary in sorted key order?

There's an existing function that ends in the following, where d is a dictionary:

return d.iteritems()

that returns an unsorted iterator for a given dictionary. I would like to return an iterator that goes through the items sorted by key. How do I do that?

Haven't tested this very extensively, but works in Python 2.5.2.

>>> d = {"x":2, "h":15, "a":2222}
>>> it = iter(sorted(d.iteritems()))
>>> it.next()
('a', 2222)
>>> it.next()
('h', 15)
>>> it.next()
('x', 2)
>>>

If you are used to doing for key, value in d.iteritems(): ... instead of iterators, this will still work with the solution above

>>> d = {"x":2, "h":15, "a":2222}
>>> for key, value in sorted(d.iteritems()):
>>>     print(key, value)
('a', 2222)
('h', 15)
('x', 2)
>>>

With Python 3.x, use d.items() instead of d.iteritems() to return an iterator.

Use the sorted() function:

return sorted(dict.iteritems())

If you want an actual iterator over the sorted results, since sorted() returns a list, use:

return iter(sorted(dict.iteritems()))

A dict's keys are stored in a hashtable so that is their 'natural order', i.e. psuedo-random. Any other ordering is a concept of the consumer of the dict.

sorted() always returns a list, not a dict. If you pass it a dict.items() (which produces a list of tuples), it will return a list of tuples [(k1,v1), (k2,v2), ...] which can be used in a loop in a way very much like a dict, but it is not in anyway a dict!

foo = {
    'a':    1,
    'b':    2,
    'c':    3,
    }

print foo
>>> {'a': 1, 'c': 3, 'b': 2}

print foo.items()
>>> [('a', 1), ('c', 3), ('b', 2)]

print sorted(foo.items())
>>> [('a', 1), ('b', 2), ('c', 3)]

The following feels like a dict in a loop, but it's not, it's a list of tuples being unpacked into k,v:

for k,v in sorted(foo.items()):
    print k, v

Roughly equivalent to:

for k in sorted(foo.keys()):
    print k, foo[k]

Greg's answer is right. Note that in Python 3.0 you'll have to do

sorted(dict.items())

as iteritems will be gone.

You can now use OrderedDict in Python 2.7 as well:

>>> from collections import OrderedDict
>>> d = OrderedDict([('first', 1),
...                  ('second', 2),
...                  ('third', 3)])
>>> d.items()
[('first', 1), ('second', 2), ('third', 3)]

Here you have the what's new page for 2.7 version and the OrderedDict API.

In general, one may sort a dict like so:

for k in sorted(d):
    print k, d[k]

For the specific case in the question, having a "drop in replacement" for d.iteritems(), add a function like:

def sortdict(d, **opts):
    # **opts so any currently supported sorted() options can be passed
    for k in sorted(d, **opts):
        yield k, d[k]

and so the ending line changes from

return dict.iteritems()

to

return sortdict(dict)

or

return sortdict(dict, reverse = True)

>>> import heapq
>>> d = {"c": 2, "b": 9, "a": 4, "d": 8}
>>> def iter_sorted(d):
	    keys = list(d)
	    heapq.heapify(keys) # Transforms to heap in O(N) time
	    while keys:
		    k = heapq.heappop(keys) # takes O(log n) time
		    yield (k, d[k])

		
>>> i = iter_sorted(d)
>>> for x in i:
    	print x

	
('a', 4)
('b', 9)
('c', 2)
('d', 8)

This method still has an O(N log N) sort, however, after a short linear heapify, it yields the items in sorted order as it goes, making it theoretically more efficient when you do not always need the whole list.

If you want to sort by the order that items were inserted instead of of the order of the keys, you should have a look to Python's collections.OrderedDict. (Python 3 only)

sorted returns a list, hence your error when you try to iterate over it, but because you can't order a dict you will have to deal with a list.

I have no idea what the larger context of your code is, but you could try adding an iterator to the resulting list. like this maybe?:

return iter(sorted(dict.iteritems()))

of course you will be getting back tuples now because sorted turned your dict into a list of tuples

ex: say your dict was: {'a':1,'c':3,'b':2} sorted turns it into a list:

[('a',1),('b',2),('c',3)]

so when you actually iterate over the list you get back (in this example) a tuple composed of a string and an integer, but at least you will be able to iterate over it.

Assuming you are using CPython 2.x and have a large dictionary mydict, then using sorted(mydict) is going to be slow because sorted builds a sorted list of the keys of mydict.

In that case you might want to look at my ordereddict package which includes a C implementation of sorteddict in C. Especially if you have to go over the sorted list of keys multiple times at different stages (ie. number of elements) of the dictionaries lifetime.

http://anthon.home.xs4all.nl/Python/ordereddict/