Why are there no ordered dictionaries?

[Alex Martelli]

Christoph Zwerschke <cito at online.de> wrote:
   ...
> I have started the thread in the first place because I believed it is
> pretty unabmiguous what an "ordered dictionary" is and how it should 

I think you're wrong here.  People in the past who have requested or
implemented stuff they called 'ordered dicts' in the past had in mind
drastically different things, based on some combination of insertion
orders, keys, and _values_.  So, ambiguity is definitely present in the
phrase 'ordered dictionary', because there are so many different
criteria whereby the 'ordering' could take place.

Note the plural in 'insertion orderS': some people care about the FIRST
time a key was added to a dict, some about the LAST time it was added,
some about the latest time it was 'first inserted' (added and wasn't
already there) as long as it's never been deleted since that occasion --
and these are just a few of the multifarious orders based on the time of
insertions and deletions of keys.  The number of variations is
staggering, e.g., consider

x['a'] = 1
x['b'] = 2
x['a'] = 1

in some applications you'd want to have 'b' come before 'a' because the
last time of addition was earlier for 'b' -- but in others you might
want 'a' first because the latest addition wasn't really one, since it
didn't really change anything (because the value inserted was the same
as the one already there -- it would be different, for those other apps,
if the RHS of the third assignment was 0 rather than 1...).

To get 'ordered dicts' into Python, you have to identify ONE unambiguous
definition which has a large-enough number of use-cases, possibly
customizable through some reasonably SIMPLE combination of flags and a
callable or two, like the 'sorted' built-in has a 'reversed' flag and
'key' and 'cmp' optional callables.  Expect a lot of flak from those who
have been pining for an 'ordered dict' which does NOT match your one
unambiguous definition...;-)

If the field of use cases for 'ordered dicts' is just too fragmented,
it's quite possible that it's best not to have any single kind built-in,
even though, could all different use cases be combined (which by
hypothesis is unfeasible), "critical mass" would be reached...


Alex