Sorted list as an alternative to dictionary for when you only need keys?

Tim Peters tim.peters at gmail.com
Mon Jul 19 22:53:05 CEST 2004


[Jeff Epler]
> ...
> Python 2.2 and above also have a "bisect" module which can be used for O(lg n)
> insertions, deletions, and searches for items in sorted lists, but
> there's not a simple OO interface for it.

The bisect module is much older than 2.2 (I can't remember a time when
Python didn't have it), but insertion and deletion are O(n), only
lookup is O(log n) with bisect.  Expected time is O(1) for insertion,
deletion, and lookup with a dict.  Sets are the same as dicts.



More information about the Python-list mailing list