[Python-3000] ordered dict for p3k collections?

[Mark Summerfield]

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:
http://groups.google.co.uk/group/comp.lang.python/browse_frm/thread/b16c34f8dd09a8a0/62a9cd8f8b73cdac#62a9cd8f8b73cdac

I also put an example implementation on PyPI since a respondent advised
that I do that:
http://pypi.python.org/pypi?:action=display&name=ordereddict&version=1.0.0

I certainly hope that Python will have one or more ordered data
structures in the collections module since I think they are often
useful. I don't expect mine to be used, I am just trying to get the
_idea_ accepted that an ordered data structure is useful and worth
putting in the standard library. I hope for example, that an AVL tree
and/or a B*tree and/or a skiplist will be implemented.

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