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

[Daniel Eloff]

"...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."

Sad that sets are really just dicts. But why is only lookup O(log n) ?
Insertion is just lookup + list.insert(). Similar for removing elements.
The complexity of list.insert() depends on the underlying
implementation, (vector or linked list?) but that still shouldn't make
it O(n) ?

"But i don't think it [bisect] fits your need for a quick lookup: it's a
python module so probably it's slower."

All bisect should be doing is taking len() and dividing it by two ( //
for integer divide). That's the mid point, you can then compare the
element at that index with the key to see if it's place above or below
and you continue almost recursively dividing that subset of the list in
half via index calculations and comparing elements. I don't think that
could be very slow, even in python.

An alternative, however, is to whip up such a class in C++, possibly
using hashes stored with the key so that we're dealing with integer
comparisons. A simple vector based approach would beat the stuffing out
of anything in python if you have a situation where the list is accessed
far more often than it is updated.

I've got several C++ dependancies in my application anyway, so I don't
mind the portability issues this poses. Besides it can be easily
implemented without any platform dependancies so porting is a simple as
compiling with a different compiler.

And maybe the Python guys would be able to use it in a future release of
Python?