Not sure if you have found an answer to this yet, but with more information about what you're trying to do could help with communicating the right solution. Again I think a hash table can answer your questions about fast-lookup, but it just depends your chosen key, and other requirements you might have about sorting. If its not too sugar specific, feel free to contact me directly. Regards, James. <div class="gmail_quote">2009/6/7 Benjamin M. Schwartz <<a href="mailto:bmschwar@fas.harvard.edu">bmschwar@fas.harvard.edu</a>> <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">Lucian Branescu wrote: > Would an ordered dictionary otherwise be all right, or am I > misunderstanding your requirements? There are other implementations, > like <a href="http://www.xs4all.nl/%7Eanthon/Python/ordereddict/" target="_blank">http://www.xs4all.nl/~anthon/Python/ordereddict/</a> </div>No, an ordered dictionary is not enough. All these ordered dictionaries are ordered either by time or by sorting the keys. Neither will work for me. The problem is simple: if I insert something at position 5, I need the object currently at position 5 to move to position 6, and the object currently at position 6 to move to position 7, etc. To accomplish this in an time-ordered odict, I would have to remove all keys subsequent to the insertion point, make the insertion, and then re-insert those keys. That's O(n). To accomplish this in a sorted-order odict, I would have to generate a new key that causes my insertion to occur at the right location. If there are repeated insertions at the same location, generating such keys becomes an O(n) operation. To see this, suppose I am repeatedly inserting at the second position. Initially, the keys are (0,1). The first insertion has to pick a key between 0 and 1, e.g. 0.5. The second insertion has to pick a key between 0 and 0.5: e.g. 0.25. The number of bits required to store these keys to sufficient precision increases by one bit on each insertion. This means that the length of the keys is O(n), so every comparison is O(n). --Ben </blockquote></div>