[Python-ideas] ordered dict

[BJörn Lindqvist]

On 4/21/07, Josiah Carlson <jcarlson at uci.edu> wrote:
>
> "BJörn Lindqvist" <bjourne at gmail.com> wrote:
> > On 4/21/07, Terry Reedy <tjreedy at udel.edu> wrote:
> > > But it *is* currently a problem for lists that will become much more
> > > extensive in the future, so it *is* currently a problem for sorted dicts
> > > that will be much more of a problem in the future.  Hence, sorted dicts
> > > will have to be restricted to one type or one group of truly comparable
> > > types.
> >
> > Alternatively, you could require a comparator function to be specified
> > at creation time.
>
> You could, but that would imply a total ordering on elements that Python
> itself is removing because it doesn't make any sense.  Including a list
> of 'acceptable' classes as Terry has suggested would work, but would
> generally be superfluous.  The moment a user first added an object to
> the sorted dictionary is the moment the type of objects that can be
> inserted is easily limited (hello Abstract Base Classes PEP!)

Where did the "we are all consenting adults here" mantra go? Java
doesn't imply any total order on elements either, yet it manages to
fit a TreeMap class that does not artificially limit the kind of items
you can put in it. Yes, you can "screw up" by overriding the hashCode
and equals methods of the items you put in it. Java, in this case,
doesn't try to enforce correctness on the language level, instead it
documents the contract the programmer is supposed to follow.
m1.equals(m2) should imply that m1.hashCode() == m2.hashCode().

Python suffer the same "problem":

class Obj:
    def __eq__(self, o):
        return 0

o1 = Obj()
o2 = Obj()
L = [o1, o2]
assert L.index(o2) == 1

Similar fuck ups are possible when using dicts. In practice this is
not a problem. An ordered dict doesn't need any more safeguards than
Python's already existing data structures. Using the natural order of
its items are just fine and when you need something more fancy,
override the __eq__ method or give the collections sort method a
comparator function argument.


-- 
mvh Björn