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?

12.12.2008 23:57:05
10 ОТВЕТОВ
РЕШЕНИЕ

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.

171
17.12.2018 01:13:06
use .items() instead of iteritems(): as @Claudiu said, iteritems does not work for Python 3.x, but items() is available from Python 2.6.
Remi 1.10.2011 17:30:14
This is not obvious. In fact, items() creates a list and therefore uses memory, whereas iteritems() essentially does not use memory. What to use mostly depend on the size of the dictionary. Furthermore, the automatic Python 2 to Python 3 conversion tool (2to3) automatically takes care of the conversion from iteritems() to items(), so there is no need to worry about this.
Eric O Lebigot 9.12.2012 11:48:13
@HowerHell use a collections.OrderedDict then you sort once & get items in sorted order always.
Mark Harviston 3.06.2013 15:23:32
But @EOL, even if iteritems() does not use memory, everything must be pulled into memory for sorted(), so there is no difference between the use of items() and iteritems() here memory-wise.
Richard 4.10.2013 14:49:28
@Richard: While it is true that all the elements must be pulled into memory, they are stored twice with items() (in the list returned by items(), and in the sorted list) and only once with iteritems() (in the sorted list only).
Eric O Lebigot 7.10.2013 08:38:09

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()))
83
13.12.2008 04:26:42
That fails for me: <type 'exceptions.TypeError'>: iter() returned non-iterator of type 'list'
mike 13.12.2008 00:04:48
That's probably because you use "dict" as the variable name. "dict" is actually the type name of dictionaries. Just use another name like "mydict" here and voila.
utku_karatas 13.12.2008 00:17:14
Still not working. Are you positive sorted() returns another iterator, as opposed to a regular list?
mike 13.12.2008 00:26:40
when and where does this exception occur? you can iterate over a list without a problem
user3850 13.12.2008 00:47:05
Agreed, hop. I don't think I ever call .next() directly except when skipping lines in files. Our iter(sorted(dict.iteritems())) solution ends up making a copy of the whole dict in memory at the "sorted(" stage anyway, so the primary iterator benefit seems lost :)
user44484 13.12.2008 14:51:39

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

sorted(dict.items())

as iteritems will be gone.

31
13.12.2008 00:00:20
That fails for me: <type 'exceptions.TypeError'>: iter() returned non-iterator of type 'list'
mike 13.12.2008 00:05:19
"Dont make use of cars because in the future we will have hoverboards"
J.J 17.03.2015 23:03:59

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]
39
13.12.2008 00:44:32
Okay, but I don't want a Dict or a List, I want an Iterator. How do i coerce it into being an Iterator?
mike 13.12.2008 00:47:57
sorted(foo.keys()) is better as the equivalent sorted(foo), since dictionaries return their keys when iterated over (with the advantage of not being forced to create the foo.keys() intermediate list, maybe—depending on how sorted() is implemented for iterables).
Eric O Lebigot 28.07.2014 09:24:31
Wonder which is better for speed and/or memory k in sorted(foo.keys()): which pulls the keys or for k,v in sorted(foo.items()): which returns a copy of the dictionary’s list pairs I would guess sorted(foo.keys())
CrandellWS 18.10.2015 02:31:02
@CrandellWS: The best way to answer the time question is with the Python timeit module.
Peter Rowell 18.10.2015 17:12:10
@frank -- Short Answer: No. A dict is an array with the actual key being a hash of the value of the supplied key. Although some implementations may be fairly predictable, and some may even make this contract, I count on nothing when it comes to hash ordering. See this post for more on 3.6+ behavior. In particular note the first answer.
Peter Rowell 30.05.2018 20:37:02

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.

3
13.12.2008 01:27:02

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)

4
9.12.2011 10:25:31

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/

2
18.06.2012 09:57:20

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)
5
6.03.2013 20:53:01
>>> 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.

5
11.04.2013 04:39:35

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.

7
8.07.2013 17:49:52
That will return key,values in the order they are inserted - not in a sorted order (i.e. alphabetic).
Tony Suffolk 66 30.11.2019 02:10:34