Is numeric keys of Python's dictionary automatically sorted?

[Steven D'Aprano]

On Wed, 07 Mar 2007 23:34:20 -0800, Nick Vatamaniuc wrote:



>> >>From the standard library docs:
>>
>> > "Keys and values are listed in an arbitrary order which is non-random,
>> > varies across Python implementations, and depends on the dictionary's
>> > history of insertions and deletions."
>>
>> > i.e. the behaviour you have discovered is an implementation detail,
>> > and could change in future versions.
> 
> I would consider that a bad choice. In the dictionary the keys are a
> set i.e. you might as well get a set() when you do d.keys() but the
> set() came later so you just get a list. 

The internal implementation of dictionaries are irrelevant.

Whether the keys "inside" a dictionary are "a set of keys" or "a list of
keys" or "a bunch of keys" is just semantics. 


> The problem with a list is
> that somehow people want to make sense of it's order, just like in
> this case. 

And the problem with a dictionary is that some people want to make sense
of its order, just like in this case, and the fifty thousand previous
times people have asked this newsgroup how they can sort a dictionary.



> So if instead of asking, he could have just written the
> application based on the fact that the keys will always be sorted in
> some way. But then one day his application maybe run a different
> platform and all of the sudden the keys are not sorted as before and
> then disaster strikes.

That would be his problem for being a bad coder, not our problem or the
language's fault.

There is no limit to the "could haves" that lead to disaster. Somebody
"could have" assumed that list.sort() returns the sorted list. Somebody
"could have" assumed that "is" is merely a synonym for "==".

And you know something? We get people making those mistakes all the time.
When people make those mistakes, it is *their responsibility*, for being
stupid or not reading the docs or not doing sufficient testing, or simply
for being inexperienced.


> I hope that dictionary.keys() would return a set to emphasize that
> keys are unordered.

What makes you think that people will magically intuit that sets are
unordered when they insist on thinking that dicts are ordered?

The below-average coder does this:

>>> D = {1: None, 2: None, 3:None}
>>> D
{1: None, 2: None, 3: None}

and concludes that dictionaries are ordered. If they are better-than
average, they might try this:

>>> D = {1: None, 4: None, 3:None} # keys out of order
>>> D
{1: None, 3: None, 4: None}

Still ordered, right? It's actually quite hard to get a dict with purely
integer keys out of order. So they ASS_U_ME that dicts are ordered.

What makes you think they won't do the same with sets?

>>> set((1, 2, 3))
set([1, 2, 3])
>>> set((1, 4, 3))
set([1, 3, 4])
>>> D = {4: None, 2: None, 1: None, 3: None}
>>> set(D.keys())
set([1, 2, 3, 4])

Sure looks ordered to me.

The solution is:

(1) Don't assume unordered data structures like sets and dicts are
ordered, even if they look like it. They aren't.

(2) If you want the keys of a dict sorted, get the keys, and sort them
when and as you need them.

(3) If you think you want a sorted dictionary, chances are you actually
want a different algorithm.

(4) But if you really do need a sorted dictionary, there are recipes on
the web. Google is your friend. But remember, they will be slower than
regular dictionaries.


-- 
Steven D'Aprano