[Python-3000] ordered dict for p3k collections? (original) (raw)

Mark Summerfield mark at qtrac.eu
Fri Sep 14 19:36:11 CEST 2007

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

More information about the Python-3000 mailing list