An ordered dictionary for the Python library?

[mensanator at aol.com]

On Sep 13, 1:27 am, Mark Summerfield <m.n.summerfi... at googlemail.com>
wrote:
> On 13 Sep, 00:03, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>
> > Mark Summerfield <m.n.summerfi... at googlemail.com> writes:
> > > I feel that Python lacks one useful data structure: an ordered
> > > dictionary.
> > > Do other Python programmers feel this lack? Is this worth a PEP?
>
> > Yes.  It should use a functional data structure.
>
> Could you elaborate?
>
> Here's my impression of the postings so far: there are 3 categories of
> response:
>
> (A) There is no need for such a thing.
>
> (B) It is useful, but so easy to implement that it needn't be in the
> library.
>
> (C) It is worth having an ordered data structure of some kind.
>
> Regarding (A) and (B): I remember Python before it had the sets
> module. "There's no need for sets, you can do them with dicts".
> Thankfully sets are in the language and I for one use them
> extensively.
>
> For (C) what I had in mind was:
>
> An API that is identical to a dict, with the few additional methods/
> behaviours listed below:
> - If an item is inserted it is put in the right place (because the
> underlying data structure, b*tree, skiplist or whatever is
> intrinsically ordered by < on the key)
> - Extra methods
>     key_at(index : int) -> key
>     item_at(index : int) -> (key, value)
>     value_at(index : int) -> value
>     set_value_at(index : int, value) # no return value necessary but
> maybe key if convenient
>     od[x:y:z] -> list of values ordered by key # can read a slice but
> not assign a slice
>   and maybe
>     keys_for(fromindex : int, uptobutexcludingindex : int) -> ordered
> list of keys
>
> I've given examples of the use cases I envisage (and that I use in
> both Python with my own ordered dict and in C++ with the map class) in
> a previous posting, and I've shown the  API I envisage above. I know
> that some people might prefer ordering by value or the option of case-
> insensitive ordering, but both these can be achieved using the API
> above, e.g.,
>     od[value.lower()] = value # case-insensitive ordering of list of
> values
> And as for duplicates there are two approaches I use: (1) make each
> string unique as I showed in my previous post, or (2) use a value that
> itself is a list, dict or set.
> (As for those who have suggested an ordered data structure that isn't
> a dict, I don't see a conflict, I'd be happy to see more data
> structures in the collections module.)
>
> Is what I've suggested sufficient (and sufficiently general) for the
> standard library?

Is the index the insertion order? The only use I have an ordered
dictionary is to quickly determine that a sequence value is the
first duplicate found (the structure can have millions of numbers)
and then play back (so they don't have to be re-calculated) the
sequence from the first duplicate to the end.

So I would get the index when I find the duplicate and then
iterate data[index:] to get the sequence in insertion order?


> If it is not, what should be done, or is there some
> other approach and API that would better provide the functionality
> envisaged?