If I have a dictionary in Python, and I iterate through it once, and then again later, is the iteration order guaranteed to be preserved given that I didn't insert, delete, or update any items in the dictionary? (But I might have done look-ups).
+2
A:
A Python dictionary has no concept of order. So you can't depend on a specific order while iterating.
This is deliberate: since it's a hashmap it's unavoidable if you want 'fast lookups'!
ChristopheD
2009-12-04 20:04:12
true, but there is some underlying order you get when you call .iterkeys() or .itervalues(). My question is - will this be preserved if the dict is not modified?
Claudiu
2009-12-04 20:06:29
That depends on the implementation, but no such guarantee is made. It appears that CPython does indeed always (based past observation and _very_ limited testing) return the keys/values/items in the same order. If you need the order to be guaranteed, just use an OrderedDict implementation, of which you can find many out in the wild.
Will McCutchen
2009-12-04 20:13:11
Will MCCutchen basically answered it: use an OrderedDict if you want to rely on an order while iterating a dict, you can't count on it on a 'standard' dict.
ChristopheD
2009-12-04 20:15:57
+1
A:
It might be preserved in some implementations, but don't count on it, as it is not a part of the Dict spec.
Ofri Raviv
2009-12-04 20:11:11
If you follow the link to the Dict spec. in John Machin's answer, you'll see that the Dict specification DOES guarantee that the iteration order will not change if you don't modify the contents. What you can't count on is that the order will be consistent between implementations.
Stephen C. Steel
2009-12-04 23:07:32
+1
A:
As Christophe said, a dictionary is used to organise key/value pairs because of the fast access time it provides. If you application needs a fixed index, you should look at the other data structures that provide a specific/known order.
Having said that, it should be safe to assume that the order doesn't change unless items are added (there wouldn't be any point to do this expensive operation of reshuffling stuff) etc but, again, don't rely on it.
Patrick
2009-12-04 20:11:21
+3
A:
Yes. There's no randomisation involved. There's an even stronger guarantee -- see here.
John Machin
2009-12-04 20:15:40
Not downvoting, but from your link: `arbitrary order which is ... /snip/ varies across Python implementations,` If you want your code to be portable, don't rely on a dict ordering. What happens if they change the dict implementation in the next CPython implementation?
ChristopheD
2009-12-04 20:18:55
As I wrote in my answer, *this is implementation specific*. other implementations might not not guarantee this. so if you utilize this property, you are actually giving up on portability.
Ofri Raviv
2009-12-04 20:19:32
@Ofri Raviv: All he is asking is will he get the same result if he does `for key in some_dict` twice if he doesn't perturb the dict in the meantime. This is a simple guarantee. If it were not true, the more complex guarantee give in the docs that I linked to would not be possible.
John Machin
2009-12-04 20:50:08
@ChristopheD: He doesn't care about what the ordering is. All he cares about the ordering is that is NOT CHANGED between two iterations in the same thread. Change of Python version or change of platform is irrelevant.
John Machin
2009-12-04 20:55:23
+11
A:
The standard Python dict like most implementations does not preserve ordering as the items are usually accessed using the key.
However predictable iteration is sometime useful and in Python 3.1 the collections module contains an OrderedDict that is order preserving with minimal performance overhead.
Tendayi Mawushe
2009-12-04 20:17:10
This is probably the best, safest, and most standard-compliant solution for people concerned about maintaining order in a `dict`. High five!
jathanism
2009-12-04 20:22:00
@Claudiu: You haven't got around to explaining what is the "it" that you want to do.
John Machin
2009-12-04 20:57:26
If you need to iterate through a dictionary in order by key value, you could always write: for key in sorted(myd.keys()): print key, myd[key]
Matt Boehm
2009-12-04 21:34:10
You can indeed sort the keys but sometimes you do actually want the order to be the order in which the elements were added to the dict which is not necessarily the sort order.This requirement is fairly common Python is not only language to support it with collections.OrderedDict, Java has a similar data structure called java.util.LinkedHashMap
Tendayi Mawushe
2009-12-04 21:43:25
The OrderedDict is providing a much stronger guarentee than the question asked for: not only is the interation order unchanged if the Dict is not modified, it is predictable for all implementations (items are iterated in the order they were inserted).
Stephen C. Steel
2009-12-04 23:10:45
I had a dict as a data structure. I wanted to do some processing on the keys, and then do some more processing on the keys a little later. I thought the order mattered, but it actually didn't. and then I ended up using a list anyway, so that's a moot point. but hey still a good question!
Claudiu
2009-12-05 02:56:36
+17
A:
Here is what dict.items documentation says:
dict.items() return a copy of the dictionary’s list of (key, value) pairs.
If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called with no intervening modifications to the dictionary, the lists will directly correspond.
I think it's reasonable to assume that item ordering won't change if all you do is iteration.
Nikola Smiljanić
2009-12-04 20:21:35
Theres no need to assume: the documentation is explicitly telling you the order won't change if all you do is interation!
Stephen C. Steel
2009-12-04 23:12:02
+1
A:
collections.OrderedDict will be available in Python 2.7 in addition to Python 3.1.
For Python versions earlier than 2.7, there's collective.ordereddict on PyPI, and Django has its own SortedDict implementation.
akaihola
2009-12-04 22:57:39