Why are there no ordered dictionaries?

[Alex Martelli]

Christoph Zwerschke <cito at online.de> wrote:

> Alex Martelli schrieb:
> > Perl hashes now keep track of 'order of keys'?  That's new to me, they
> > sure didn't back when I used Perl!
> 
> Maybe I shouldn't have talked about Perl when I'm an ignoramus about 
> that language... You're right, Perl has unordered arrays. That was new
> to me since I associate the term "array" always with "ordered" and I 
> just remembered that PHP's assoc arrays are similar to Perl's but in 
> fact, and the examples I have read did not mention about that problem.

Perl's _arrays_ are a bit like Python _lists_, and ordered; it's the
_hashes_ that are a bit like Python _dicts_, and unordered.  PHP's use
of "array" for both concepts may indeed be a bit confusing.


> > What about PHP?
> 
> You can conclude that PHP's assoc arrays are ordered from the fact that
> the language provides a ksort() function to order the keys. And I think
> PHP's insertion order is the one I mentioned in my last post.
> 
> Anyway, it would be interesting to examine this in detail and how this
> is implemented in other languages.

Yep.  After just a bit of research I suspect you're right re PHP but
haven't found a specific reference-manual page URL about it.


> > "first insertion (since the last deletion if any)" is ONE unambiguous
> > definition, but surely not "_the_ ONE" with emphasis on ``the''.
> > I see nothing _ambiguous_ (nor _unnatural_) in being interested in the
>  > *last* insertion, for example; indeed if phrased as "upon insertion, put
>  > the key at the end of the sequence" (whether it was already elsewhere in
>  > the sequence of not), with no need for conditionals regarding previous
> > existence, it might appear more "conceptually compact".
> 
> But it would not satisfy the concept of "keys of a dictionary" which are
> always unique.

Why not?  Since keys are unique, any 'sequence' of keys is a permutation
of a set, a perfectly well-defined concept.


> BTW, there are some boundary conditions that should be fulfilled for the
> insertion order, most obviously:
> 
> If you define an ordered dict that way:
> 
> d = odict()
> d['a'] = 1
> d['b'] = 2
> d['c'] = 3
> 
> The keys should then be orderes as ('a', 'b', 'c').

Yep, but both 'first-insertion' and 'latest-insertion' (and many other
rules) meet that constraint.


> That would be also biased (in favour of Python) by the fact that 
> probably very little people would look for and use the package in the
> cheese shop if they were looking for ordered dicts. I for example would
> probably use ordered dicts if they were part of the standard lib, but
> not if I have to install it as an obscure separate package. So I don't
> think that will give us a real clue how many people would like ordered
> dicts in the standard lib.

A package on cheese shop need not be "obscure" -- that depends on
announcing it well, etc.  And the standard library is so huge that many
things inside IT are in fact obscure -- I find myself often pointing out
standard-library solutions to rather experienced Pythonistas who had
been rolling their own, unaware of the stdlib alternative (thus making
the stdlib even bigger has a cost...).  So, I don't think this effect
invalidates the experiment; while not all who download an add-on would
like it in the stdlib, and vice versa, there is surely a correlation
between amount of interest/need for the add-on's functionality, and both
rate of downloads as well as interest in having it in the stdlib.

> But anyway, if I find some time, I will research a little bit more about
> the issue and create such a package, because it seems to me that the 
> existing packages and recipes are not really satisfying and you're right
> it seems to be reasonably easy. It's on my todo list now...

It presumably should have a C implementation for speed and a Python one
for wide availability and ease of installation (the latter gives all the
advantages of prototyping in fixing the API &c, and is made especially
easy by the existence of UserDict.DictMixin in the stdlib).  I'll be
glad to help out with the C part when it gets to that, just holler...


Alex