Why are there no ordered dictionaries?

[Christoph Zwerschke]

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.

> 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.

> "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.

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').

> Anyway -- subclassing dict to implement your definition is reasonably
> easy, and we could put the resulting package on the Cheese Shop.  I hope
> python.org keeps good enough statistics to be able to tell us, a couple
> months later, how many people downloaded said package, vs how many
> people downloaded a complete Python distro; of course, that ratio is
> biased (in favour of the package) by the fact that many people already
> have a complete distro available, while initially nobody would have the
> package, but if we measure when things settle, after letting a month of
> two or 'transient' pass, that effect might be lessened.

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.

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...

-- Christoph