Why are there no ordered dictionaries?

[Kay Schluehr]

Bengt Richter wrote:
> On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke <cito at online.de> wrote:
>
> >Fredrik Lundh wrote:
> >> if you restructure the list somewhat
> >>     d = (
> >>         ('pid', ('Employee ID', 'int')),
> >>         ('name', ('Employee name', 'varchar')),
> >>         ('sal', ('Salary', 'float'))
> >>         )
> >> you can still loop over the list
> >> ...
> >> but you can easily generate an index when you need it:
> >>     index = dict(d)
> >
> >That's exactly the kind of things I find myself doing too often and what
> >I was talking about: You are using *two* pretty redundant data
> >structures, a dictionary and a list/tuple to describe the same thing.
> >Ok, you can use a trick to automatically create the dictionary from the
> >tuple, but still it feels somewhat "unnatural" for me. A "ordered
> >dictionary" would be the more "natural" data structure here.
> >

> But, as has been mentioned**n, this is only one example of an ordering one
> could make default for an "ordered" dictionary. Suppose you say it should
> be ordered by insertion order, so
>   d = OrderedDict(); d[1]='one'; d[2]='two' =>> list(d) => [1, 2]
> ok, now we do d[1]='ein' and what is the order? list(d) => [2, 1] ??
> Or do replacements not count as "insertions"?

"Insertion-order" is not a good term. For a dictionary {key:value} pair
creation, updating and deletion are possible modifying operations.  I
don't see how deletion influences the order so creation and updating
remains. Therefore you have to select beween a creation_order and an
update_order. This can be reduced to one additional keyword e.g.
"creation_order" that is assigned a boolean value which is true by
default.

> The devil is always going
> to be in the details. Maybe you want a model that works more like a list
> of key:value pairs with just optimized access to a pair by key name as
> well as position in the list. Or maybe you want to permit append and
> NOT prevent [('a',1), ('a':2)] and maybe d['a'] => [1, 2] ???

As far as I understand the requirement an odict provides the same
interface as a dict. The only difference is a certain order of the keys
that is induced by operations on a dict and cannot be established by
properties of the keys ( or values ) itself.

> Note that is isn't hard to snap a few pieces together to make an ordered
> dict to your own specs. But IMO it belongs in pyPI or such, not in the system
> library. At least until it gets a lot of mileage -- and MMV ;-)

It's also not very hard to write a hex2ascii converter. That's the
reason why 20 incompatible versions of it ( coded in C ) exists in my
department ;)

Kay

PS. Here is some attempt of my own to implement an odict, following the
discussion here.
The implementation highlights just the model and is incomplete:

class odict(dict):
    def __init__(self, create_order = True):
        dict.__init__(self)
        self.create_order = create_order
        self.__cnt = 0

    def __setitem__(self, key, value):
        val = dict.get(self,key)
        if val and self.create_order:
            dict.__setitem__(self, key, (val[0], value))
        else:
            self.__cnt+=1
            dict.__setitem__(self, key, (self.__cnt, value))

    def __getitem__(self, key):
        return dict.__getitem__(self, key)[1]

    def values(self):
        return list(zip(*sorted(dict.values(self)))[1])

    def keys(self):
        ks = [(dict.get(self,k)[0],k) for k in dict.keys(self)]
        return list(zip(*sorted(ks))[1])

>>> od = odict()
>>> od["a"] = 0
>>> od["b"] = 8
>>> od.keys()
["a", "b"]

>>> od = odict(create_order = False)
>>> od["a"] = 1
>>> od["b"] = 2
>>> od["a"] = 3
>>> od.keys()
["b", "a"]