[Python-3000] ordered dict for p3k collections?

[Mark Summerfield]

On 2007-09-14, Adam Olsen wrote:
> On 9/14/07, Mark Summerfield <mark at qtrac.eu> wrote:
> > On 2007-09-14, Nicko van Someren wrote:
> > > On 11 Sep 2007, at 15:06, Mark Summerfield wrote:
> > > > Is there any chance that an ordered dict will be added to Python 3's
> > > > library?
> > >
> > > It would make sense, since one of the primary justifications for the
> > > new metaclass system (PEP 3115) is to allow the metaclass to provide
> > > order-preserving dictionaries to record the order in which members
> > > are defined.
> > >
> > > > I think other people must find such things useful. There are three
> > > > implementations on the Python Cookbook site, and one on PyPI, all in
> > > > pure Python (plus I have my own implementation, also pure Python).
> > >
> > > Is there much commonality between the interfaces for these?  I'm sure
> > > there are various different opinions as to the exact nature of the
> > > API, particularly around any facilities for re-ordering, slicing etc.
> > >       Cheers,
> > >               Nicko
> >
> > After posting I realised that actually this isn't P3K-specific. I'd hope
> > to see the collections module extended with more data structures in
> > general.
> >
> > I put a similar post on the main python list but with no consensus so
> > far...
> >
> > I put forward an API which is the same as dict (but any list or iterator
> > returned "just happens" to work in key order) plus a few extra methods
> > to exploit the ordering. I don't know how to refer to a usenet thread
> > but this should get there:
>
> That's a sorted dict.  PEP 3115 wants an insertion-ordered dict.
> You're not the first to confuse them. ;)

Hmmm, I'd not come across that terminology distinction before.
I guess I'll have to rename mine then.

BTW In my previous I said "I hope for example, that an AVL tree and/or a
B*tree and/or a skiplist will be implemented." Actually, I don't care
what data structures are used, I just think that Python lacks ordered
data structures, specifically: sorteddict and sortedset. (Personally
I've never needed an insertion-ordered dict.)


-- 
Mark Summerfield, Qtrac Ltd., www.qtrac.eu