Why are there no ordered dictionaries?

[Christoph Zwerschke]

bonono at gmail.com schrieb:
> It seems to be though as "ordered dictionary" are slowly to be confined
> to only "ordered on order of change to the dictionary".

"Ordered dictionary" means that the keys are not an ordinary set like in 
an ordinary dictionary, but an "ordered set." I think this definition is 
pretty straightforward and common. An ordered set is the same as a 
unique list, i.e. a list where all elements are unique.

When there is automatical ordering using a comparison function, I would 
not speak of an "ordered directory", but of a "sorted directory." This 
would be basically a dictionary plus a comparison function. The keys 
would always be iterated in the order given by the comparison function. 
It would be nice to have a sorted dictionary as well, even if you can 
achieve the same by calling the sorted built-in on the keys. Think of a 
sorted directory as a subclass of ordered directories. Implementing it 
that way would even have perfomance benefits if the keys are inserted 
using the bisect algorithm. This is better than calling sorted() on the 
keys of an ordinary dictionary many times.

By the way, you will find the same terminology in Smalltalk, where 
"SortedCollection" is a subclass of "OrderedCollection".

-- Christoph