[Python-ideas] ordered dict

[Josiah Carlson]

"BJörn Lindqvist" <bjourne at gmail.com> wrote:
> 
> On 4/20/07, Terry Reedy <tjreedy at udel.edu> wrote:
> > 2. Order in the sorting or collation sense, which I presume you mean.  To
> > reduce confusion, call this a sorted dictionary, as others have done.
> >
> > Regardless, this has the problem that potential keys are not always
> > comparable.  This will become worse when most cross-type comparisons are
> > disallowed in 3.0.  So pershaps the __init__ method should require a tuple
> > of allowed key types.
> 
> >>> l = [(), "moo", 123, []]
> >>> l.sort()
> >>> l
> [123, [], 'moo', ()]
> 
> If it is not a problem for lists it is not a problem for ordered dictionaries.

It's about a total ordering.  Without a total ordering, you won't
necessarily be able to *find* an object even if it is in there.

>>> import random
>>> a = ['b', (), u'a']
>>> a.sort()
>>> a
['b', (), u'a']
>>> random.shuffle(a)
>>> a.sort()
>>> a
[u'a', 'b', ()]


Also, in 3.0, objects will only be orderable if they are of compatible
type.  str and tuple are not compatible, so will raise an exception when
something like "" < () is performed.


> > If not already present in PyPI, someone could code an implementation and
> > add it there.  When such has be tested and achieved enough usage, then it
> > might be proposed for addition to the collections module.
> 
> And that is how the currently considered for Python 3.0 ordered dict
> implementation got into Python?
> 
> I find it amusing that over the years people have argued against
> having an ordered dict in Python. But now, when one is considered,
> only THAT version with THOSE semantics, is good. The rest should go to
> PyPI.

No, the "ordered dict" that is making its way into Python 3.0 is
specifically ordered based on insertion order, and is to make more
reasonable database interfaces like...

class Person(db.table):
    firstname = str
    ...

Its implementation is also a very simple variant of a dictionary, which
isn't the case with any tree implementation.


Further, because there are *so many* possible behaviors for a dictionary
ordered by keys implemented as a tree, picking one (or even a small set
of them) is guaranteed to raise comments of "can't we have one that does
X too?"


 - Josiah