Why are there no ordered dictionaries?

[Ben Sizer]

Fredrik Lundh wrote:
> Ben Sizer wrote:
> > This is interesting; I would have thought that the tuple is read and a
> > dictionary created by inserting each pair sequentially. Is this not the
> > case?
>
> pointers to the members of each pair, yes.  but a pointer copy is a
> cheap operation (for the given use case, we're only talking about a
> few dozen pairs anyway, at the most).

I was really thinking more about the other work, such as the hashing
and whatever, but I guess that is very efficient anyway.

> this is a common fallacy; Python programmers underestimate the
> cost of adding extra layers to their code (e.g. by using an ordered
> dict data structure that has to incrementally update both a list and
> a dictionary), and overestimate the cost of letting the C layer do
> bulk operations.

If it was me I would probably have just used a list and searched it
linearly: premature optimisation is the root of all evil, etc. But then
I've never found a need for an ordered dictionary anyway; I always felt
they were more an artifact of the language implementation than a
reflection of something inherently useful.

However, you have to forgive people for falling prey to the 'fallacy'
you describe - for years there's been an attempt to teach people to use
proper data structures and algorithms instead of relying on
micro-optimisations (ie. "it's too slow: redo it in assembly"). So
often, the first port of call for a good programmer will be to try and
find a structure that maps directly to the problem.

-- 
Ben Sizer