This http://www.python.org/dev/peps/pep-0372/ might be interesting. Perhaps it could get backported to 2.5.
But it still has O(n) deletion. 2009/6/7 Benjamin M. Schwartz <bmsch...@fas.harvard.edu>: > James Zaki wrote: >> Taking a guess with the information you've given perhaps a hash >> table<http://en.wikipedia.org/wiki/Hash_table>could help? > > Python uses the term "Dict" to describe its built-in hash table. I do > think a hash table could be helpful, for example, to maintain the reverse > lookup mapping if the forward lookup is stored in a List (which is > actually python's version of a dynamic array, like C++'s Vector). > However, I am still stuck with O(N) performance in this case for insertion > and deletion, because each such modification shifts the position of all > subsequent objects. This would correspond to changing the value > associated with half the keys in the hash table, on average, for each > insertion. > > I was hoping for a structure with log-time performance. > > --Ben > > > _______________________________________________ > Sugar-devel mailing list > Sugar-devel@lists.sugarlabs.org > http://lists.sugarlabs.org/listinfo/sugar-devel > > _______________________________________________ Sugar-devel mailing list Sugar-devel@lists.sugarlabs.org http://lists.sugarlabs.org/listinfo/sugar-devel