Why are there no ordered dictionaries?

[Alex Martelli]

Christoph Zwerschke <cito at online.de> wrote:
   ...
> But I think the following rule is "natural" enough to consider it as THE
> standard behavior of ordered dictionaries:
> 
> "Insertion: If the key exists: Don't change the order. If it does not
> exist: Append it to the sequence of keys. Deletion: Remove from the 
> sequence of keys."
> 
> I think this is also the behavior of associative arrays in PHP or Perl

Perl hashes now keep track of 'order of keys'?  That's new to me, they
sure didn't back when I used Perl!  It's been a while, but a little
googling shows me, e.g at
<http://www.openarchives.org/pipermail/oai-implementers/2002-September/0
00642.html>, assertions such as:
"""
Hashes don't maintain key order. To get them in sorted order try:

    foreach $i (sort keys(%afiliacao))
"""
which fully match my memories.  Could you produce a URL to support the
hypothesis that Perl has changed its behavior?  What about PHP?  Thanks!

> and could be considered as the "ONE unambiguous definition".

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

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.

If we ran such an experiment, what fraction do you think would serve to
convince Guido that a dict 'ordered' by your definition is necessary in
Python 2.5's standard library (presumably in module 'collections')?


Alex