Why are there no ordered dictionaries?

[Christoph Zwerschke]

Alex Martelli wrote:

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

Perl's _hashes_ have been also called _associative arrays_ originally.

 >>Anyway, it would be interesting to examine this in detail and how this
 >>is implemented in other languages.

Ok, I just did a little research an compared support for ordered dicts 
in some other languages:

* Perl has hashes (associative arrays) which are not ordered.
Here also people are asking for and implementing "ordered hashes",
e.g. http://perltraining.com.au/tips/2005-06-29.html
http://search.cpan.org/dist/Tie-IxHash/lib/Tie/IxHash.pm
http://search.cpan.org/dist/Tie-InsertOrderHash/InsertOrderHash.pm
http://www.yapc.org/America/previous-years/19100/schedule/author/pinyan.html

* Ruby hashes are not ordered.
Again people are asking for and implementing "ordered hashes".
e.g. http://raa.ruby-lang.org/project/orderedhash/
http://groups.google.com/group/comp.lang.ruby/browse_frm/thread/8ebe8d1c5830c801/6428a870925f23f4

* Smalltalk: Innately has unordered Dictionaries.
People are asking for and implementing "OrderedDictionaries" as well,
e.g. http://exept.eu.org:8080/ClassDoc/classDocOf:,OrderedDictionary

* Lisp has (ordered) "association lists".

* PHP has ordered associative arrays.

* Awk, TCL: Associative arrays are unordered.

* C++ has a Map template in the STL which is ordered (a "Sorted 
Associative Container").

* Java: Has "LinkedHashMap" which is ordered.

So ordered dictionaries don't seem to be such an exotic idea.

All implementations I found were pretty unequivocally the same that I 
had in mind, using insertion order, appending the latest inserted keys 
at the end, not changing the order if an existing key is re-inserted, 
and deleting keys together with entries.

I also found a discussion thread like the current where similar 
arguments were mentioned for and against ordered dictionaries:

In http://mail.python.org/pipermail/python-dev/2005-March/052041.html,
Nick Coghlan raises the following rhetorical question:

Would the default semantics below really be that suprising?

"An ordered dictionary remembers the order in which keys are first seen 
and, when iterated over, returns entries based on that order. This 
applies to direct iteration, iteration over values and (key, value) 
pairs, to the list-producing methods (i.e. keys(), values() and items()) 
and to any other operations that involve implicit iteration (e.g. 
converting to a string representation). Overwriting an entry replaces 
its value, but does not affect its position in the key order. Removing 
an entry (using 'del') _does_ remove it from the key order. Accordingly, 
if the entry is later recreated, it will then occur last in the key 
order. This behaviour is analagous to that of a list constructed using 
only list.append() to add items (indeed, the key order can be thought of 
as a list constructed in this fashion, with keys appended to the list 
when they are first encountered)."

This was also the semantics I immediately had in mind when I thought 
about ordered dictionaries, though I hadn't read anything about ordered 
dictionaries before and it is the same semantics that I found others 
have implemented in other languages.

I can't help but I still find it unambiguous and intuitive enough to 
consider it "the one" standard implementation for ordered dictionaries.

Also, in the use cases mentioned (describing database columns, html form 
fields, configuration parameters etc.), the dictionary is usually only 
created once and then not changed, so different handling of re-insertion 
or deletion of keys would not even be relevant in these cases.

-- Christoph