Steve Holden: I forgot a detail: in the Python version of Odict I use element deletion is O(n). You need a second dict to improve that (or a duble linked list of hashing operations, see below).
> FYI there was a *long* discussion around the need for Speed sprint about > implementing ordered dicts. As the discussion started by your thread has > started to reveal, everyone has just-ever-so-slightly-different > requirements. IIRC the goal was dropped because it wasn't possible to > agree on a specification. I received a similar answer about graphs too. But this time I think the semantic of an ordered dict is simple and clear enough, so I belive a generally acceptable solution may be found still. An implementation with double linked lists allows amortized O(1) for all the usual dict metods, deletions too. Maybe firstkey() lastkey() methods can be added too, that return the first and last key of the odict. The following is a simple example, note that this is a "wrong" implementation, because you can't scan the keys in the ordered way (you can scan the values in a ordered way). I presume in a C implementation you can find the key of a given value. If this isn't possibile without creating a chain of hashing operations, then I too drop off from this odict idea :-) class Odict(dict): def __init__(self): dict.__init__(self) self.lh = None # list header self.lt = None # list tail def __getitem__(self, key): return dict.__getitem__(self, key)[1] def __setitem__(self, key, val): if key in self: dict.__getitem__(self, key)[1] = val else: new = [self.lt, val, None] dict.__setitem__(self, key, new) if self.lt: self.lt[2] = new self.lt = new if not self.lh: self.lh = new def __delitem__(self, k): if k in self: pred,_,succ= dict.__getitem__(self,k) if pred: pred[2] = succ else: self.lh = succ if succ: succ[0] = pred else: self.lt = pred dict.__delitem__(self, k) else: raise KeyError, k Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list