An ordered dictionary for the Python library?

[James Stroud]

Mark Summerfield wrote:
> - If an item is inserted it is put in the right place (because the
> underlying data structure, b*tree, skiplist or whatever is
> intrinsically ordered by < on the key)

+1 for all your suggestions below, but -1 for the above. You suggest that

   myOrderedDict['key'] = value

would place it in the dictionary in sorted order depending on 'key'. 
More natural to some of us (or maybe its just me) would be to append the 
key/value pair to the end of items.

My Argument: The problem with inserting at sorted position is the 
assumption that the dict is already sorted, but maybe I want the key 
ordering to reflect something arbitrary, like a database, etc (e.g. 
'Last', 'First', 'MI'). So now I assign to an OrderedDict that already 
has these latter 3 keys:

   myOrderedDict['Favorite Color'] = 'chartruse'

Where does it go? Answer: it probably depends on how the underlying 
sorter works and (even worse) the internal state of the sorter's data 
structure. So, my intuition is that SortedDict behavior should be kept 
distinct from OrderedDict behavior.

> - Extra methods
>     key_at(index : int) -> key
>     item_at(index : int) -> (key, value)
>     value_at(index : int) -> value
>     set_value_at(index : int, value) # no return value necessary but
> maybe key if convenient
>     od[x:y:z] -> list of values ordered by key # can read a slice but
> not assign a slice

I do not see why assigning a slice is a bad idea here. The behavior 
could be such:

  od = OrderedDict((('Last':'Smith'), ('First':'John'), ('MI':'J'))

  od[:1] = ['Brown']
  od[:2] = ['Glotz', 'Joe']

  od[:2] = ['Williams', 'Mary', 'Francis']  # <== ValueError

The latter would be a phenomenon similar to unpacking a tuple of the 
wrong length.

>   and maybe
>     keys_for(fromindex : int, uptobutexcludingindex : int) -> ordered
> list of keys

Of course the naming is redundant for these in my opinion. E.g.:

   key_at -> key
   item_at -> item
   value_at -> value
   set_value_at -> set_value  (not simply set)
   keys_for -> keys           (takes optional argument(s))

James