Why are there no ordered dictionaries?

Christoph Zwerschke cito at online.de
Thu Nov 24 18:42:45 CET 2005


Bengt Richter schrieb:

>>d.setvalues((13, 14)) ==> d = OrderedDict((1, 13), (2, 14))

> 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).

Right. Interpret it as a short notation only, I did not want to change 
the interface. I think it's a common mistake to forget the brackets 
because you think one pair should be enough. At least I often forget it.

> 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.

Nice. You could also get the i-th value with d.values[i].

But is this considered good style or would it be considered "dirty" to 
have a callable member that also supports indexing and slicing? (I don't 
know, just asking?) Plus, it opens a can of worms by increasing the 
complexity tremendously. Let's see whether this can be handled.

> 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.

Not sure about that. I would rather expect that if you slice an object, 
you get an object of the same type. And you can also add, sort, reverse, 
etc the ordered dict if you want.

> 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 ...

You mean slice assignments to d.items[i:j]. If you make the slice 
assignment to d[i:j] then at least you cannot have conflicts in the 
incoming items. The first question is: Should a slice assignment be 
treated as deletion with subsequential addition (changing the order) or 
as a replacement (i.e. try to not change the order)? I agree that the 
second would be the expected semantics, but as you mentioned more 
difficult to implement.

 > 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)

Which should be the same as
d = OrderedDict(d.items[:i] + list(itemseq) + d.items[j:])
Sounds reasonable.

> So
>     d.reverse()
> could be spelled
>     d.items[:] = d.items[::-1]

Slice assignment for keys and values would also allow to set a new key 
order with

d.keys[:] = newkeyseq

So no need to define a setkeys() method or let keys() take arguments.
If we want to allow this kind of things at all.

> 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 still think d[i:j] should return an ordered dict, not an item list.

> 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.

There are different opinions. Fuzzyman would probably say "Don't trust 
yourself?" I myself am undecided. Perhaps you could expect that somebody 
knows what he does if he makes a slice assignment to d.keys. In any way, 
such an assignment should not "break" the directory (with "broken" I 
mean that the internal keys sequence does not match the keys of the 
internal dictionary). If anything does not match, it should raise a 
KeyException. If it is implemented that way, I think we can allow it.

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

Wouldn't it be more performant to compare for 
d1.internal_dict==d2.internal_dict and 
d1.internal_sequence==d2.internal_sequence?
You don't keep track of the item lists, they need to be built on every 
occasion.

-- Christoph



More information about the Python-list mailing list