An ordered dictionary for the Python library?

[Mark Summerfield]

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? If it is not, what should be done, or is there some
other approach and API that would better provide the functionality
envisaged?