June 16, 2008
6:26 a.m.
It is possible to get both ordered dict and sorted dict semantics in the same type if you replace (key, value) pairs for dictionary entries with (key,value,order) triples. The third component is a value that indicates the place of the entry relative to the other entries. To get an ordered dict, __setitem__ assigns 1+ max(order) to the new entry's order. To get a sorted dict, order = key. To get a dict sorted by some key function, order = keyfunc(key), etc... David