[Python-Dev] Proposal: add odict to collections

[Raymond Hettinger]

From: "Talin" <talin at acm.org>
> There's been a lot of controversy/confusion about ordered dicts.

I think that is why all earlier proposals all died.


> One of 
> the sources of confusion is that people mean different things when they 
> use the term "ordered dict": In some cases, the term is used to mean a 
> dictionary that remembers the order of insertions, and in other cases it 
> is used to mean a sorted dict, i.e. an associative data structure in 
> which the entries are kept sorted. (And I'm not sure that those are the 
> only two possibilities.)

For an insertion order dictionary, there was also a question about
how to handle duplicate keys.

Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return?

   [(k1,v3), (k2,v2)]
   [(k2,v2), (k1,v3)]

The first maintains the original sort order and is consistent with the usual
idea that d[k]=v simply replaces the value but does not alter the hash table.
It is a bit weird though because v3 appears earlier than v2 which was
inserted earlier.  It's especially weird for keys that are equal but not
identical: d[0]=v1  d[0.0]=v3.  Do you want 0.0 to remain associated
with v3 or should the items list contain a pair that was not in the original
insertion list, (0, v3)?

The second one is a bit weird because a key "loses its place" whenever
the value is updated.

IIRC, previous discussions showed an interest in odicts but that
there were a lot of questions of the specific semantics of the API.
This would no doubt be compounded by attempts to emulate
dict views. Regardless, there should probably be a PEP and
alternate pure python versions should be posted on ASPN so people
can try them out.
post


Raymond