Why are there no ordered dictionaries?

[Christoph Zwerschke]

> What answers have you received that have not been satisfactory?

I googled a little bit and haven't found many answers at all. Some were 
in the posting I mentioned: Stuff should go into the standard lib only 
when it is mature and "right" enough. However, we are already at Python 
2.4 and there is still no ordered dictionary, though there is a lot of 
other specialized stuff.

> Some possible answers: The native dict is very fast, partly because
> the implementation doesn't need to ensure any particular ordering.

Ok, but that's not an argument against providing ordered dictionaries as 
well.

> Ordering the keys isn't the normal case, and can be done easily when
> needed.

That depends. Maybe I do not want the keys to be sorted alphabetically, 
but according to some criteria which cannot be derived from the keys 
themselves.

> You asked "why not" rather than "has anyone done this anyway"; if
> you asked the latter of the Python Cookbook, you might find something
> like this.

Yes, I also found that others have done it more than once, and I know 
that it's not so difficult to do. There are at least two recipes in the 
mentioned cookbook and there is odict in pythonutils. The question was 
why is it not available in the *standard* lib.

> In what cases do you find yourself needing a dict that preserves its
> key order? Can you present a use case that would be improved by an
> ordered dict?

There are too many different situations and it would be too much to 
explain them here, usually in the case mentioned above where the keys 
are not sorted alphabetically. I often solve them by using two data 
structures, a list or tuple, plus a dictionary. For instance, the list 
could contain the names of database fields which shall be output in a 
certain order, and the dictionary values could contain human readable 
description of the database fields for headers or something. Instead of 
maintaining both data structures I feel it would be more natural to use 
only one ordered dictionary.

> For my part, I consider it a virtue of Python that the standard
> library doesn't change rapidly. It allows many competing
> implementations to be shaken out before everyone starts depending on
> any one of them.

Ok, but this can be used as an argument to not add anything to the 
standard lib any more. There are already enough competing 
implementations. Also, the implementation details are not so important, 
there must be only agreement on the interface and behavior which should 
not be so difficult in this case.

I simply wanted to ask why it is not available in the standard lib, 
since I simply don't know

- has it not been demanded loud enough?
- is it really not needed (if you need it it shows you are doing 
something wrong)?
- because nobody presented a satisfying implementation yet?
- are there hidden difficulties or controversial issues?

-- Christoph