[Tutor] Dictionary

[Danny Yoo]

> But see below:
>
>  >>> {1:1, 22:2, 333:3, 4444:4, 55555:5}.keys()
> [1, 55555, 4444, 333, 22]
>
> >Is it incident or a feature? Can we rely on that
> >behaviour?
>
> As seen above, you can't rely on that. See library reference 2.2.7, note
> (3). "Keys and values are listed in random order." I think it should
> really say "arbitrary" order or something like that, but the intention
> with that text must be to warn you from expecting to get a sorted list,
> even if that is what you get now for SOME key values.


If we do want to use a dictionary, yet go through it in key-sorted order,
we need to do the intermediary step of running a sort() through the keys()
(or even the items()!)

###
>>> def getSortedItems(dictionary):
...     items = dictionary.items()
...     items.sort()
...     return items
...
>>> d = {1:1, 22:2, 333:3, 4444:4, 55555:5}
>>> getSortedItems(d)
[(1, 1), (22, 2), (333, 3), (4444, 4), (55555, 5)]
###

For most common tasks, this works sufficiently well that people really
haven't clamored too much for a keys() method that returns things in
sorted order.


However, if we really do want to have a sort of dictionary that does
return its keys() in sorted order, we may want to use something like a
"red-black" tree data structure.

A red-black tree behaves similarly to a dictionary --- it maps keys to
values --- but also makes it convenient to march through the keys and
values in sorted order, without having to do that intermediate sort()
step.  Someone's written an implementation in Python:

    http://newcenturycomputers.net/projects/rbtree.html


I hope this helps!