Why are there no ordered dictionaries?

[Bengt Richter]

On Wed, 23 Nov 2005 23:00:29 +0100, Christoph Zwerschke <cito at online.de> wrote:

>Fuzzyman wrote:
>
>> So what do you want returned when you ask for d1[1] ? The member keyed
>> by 1, or the item in position 1 ?
>
>In case of conflict, the ordered dictionary should behave like a 
>dictionary, not like a list. So d1[1] should be the member keyed by 1, 
>not the item in position 1. Only in case there is no member keyed by 1, 
>the item in position 1 could be returned, but I think that would be too 
>adventurous a hattrick and can lead to big confusion. Better to raise a 
>KeyError in that case.
>
>>> But no other way to directly manipulate the keys should be provided.
>
>> Why - don't trust yourself with it ?
>
>No, because I think it is not needed if list operations like insert are 
>directly possible on your dictionary.
>
>But maybe methods such as setkeys() and setvalues() would be nice to 
>have in addition.
>
>Instead of writing d.sequence = new_sequence, I would write 
>d.setkeys(new_sequence). But I'm not sure what to do if new_sequence is 
>not a permutation of the old one. Raise a KeyError? Or even swallow 
>this? For instance
>
>d = OrderedDict((1,11), (2,12))
>
>d.setkeys((2, 1)) ==> d = OrderedDict((2, 11), (1, 12))
>
>d.setkeys((3, 4)) ==> d = OrderedDict((3, 11), (4, 12)) (or KeyError?)
>
>d.setvalues((12, 11)) ==> d = OrderedDict((1, 12), (2, 11))
>
>d.setvalues((13, 14)) ==> d = OrderedDict((1, 13), (2, 14)) (always ok)

Too many weird possibilities for unexpected key-value associations.
d.setitems() might be safer, but see d.items[i:j] below (without eliminating d.items() ;-)

The implication above is that OrderedDict takes an *args argument,
but really it takes a single argument that is a sequence of k,v pairs,
(and maybe some keyword options).

>
>(Or maybe better set_keys in analogy to has_key?)
>
>I hesitate making keys and values managed properties, because this would 
>conflict with them being methods in ordinary dicts. Ordered dicts should 
>resemble ordinary dicts as closely as possible. And giving it a 
>different name like "sequence" I find confusing and unintuitive.
>
>A resort could be the following: If keys() is given a sequence as 
>argument, then use this as the new sequence of keys, and similar with 
>values(). This way, no new methods need to be introduced.
>
You could make keys, values, and items custom descriptors which would define __call__
for the old key() etc accesses, well as __getitem__ and __setitem__. Then you could write

    d.items[0], d.items[-1] = d.items[-1], d.items[0]

to swap the order of the first and last items in the thing (I hesitate to say dict ;-)
You could also operate on slices. BTW, before I showed an example where d[2:3] returned
a new dict instance rather than d.items()[:]. I think the items list is better, since
they naturally add, sort, reverse, etc as lists, and you can write OrderedDict(d[2:3]+d[1:2])
if you want a new dict.

A slice assignment to d[i:j] is really sugar for something, but we have to decide exactly
what in case of duplicate keys in the incoming items, either with each other (effictively
a shorter incoming list with the last key:value pairs replacing prior pairs with the same key,
but the first key determining placement -- but where? what if a key doesn't exists outside of
the target slice (hence not within the eliminated slice, since the whole target dict item list
has unique keys)? One way to define it would be
    d.items[i:j] = itemseq

to be implemented as sugar for
    newitems = d.items[:i] + list(itemseq) + d.items[j:]
    d.clear()
    d.update(newitems)
so
    d.reverse()
could be spelled
    d.items[:] = d.items[::-1]

If you are using slices, you can safely use them directly in the __getitem__ of th dict interface,
as I did in the "Que mas?" post. So we don't have to write d.items[i:j] and could write d[i:j].
The thing is, d[i:j] will tempt to skip ".items" in d.items[i] and write d[i], which has the dict key meaning,
not the item list index. It is faster not have a descriptor between though.

I think maybe allowing write to keys or values is pretty iffy. There are too many weird
re-associations of keys and values possible, and which you could do my other means if you
really really wanted to. But I do think full index and slice read access would be fine.

I think also that d1==d2 should effectively be implemented as d1[:] == d2[:] -- i.e, compare
the item lists to implement comparisons.

Detailed requirements are most of the work ;-)
I'm thinking now to try subclassing list in a constrained way instead of dict, but well see.

Regards,
Bengt Richter