Details about pythons set implementation

r.grimm at r.grimm at
Sat Jan 5 11:06:21 CET 2008

On Jan 4, 6:08 pm, Sion Arrowsmith <si... at>
> Hrvoje Niksic  <hnik... at> wrote:
> >BTW if you're using C++, why not simply use std::set?
> Because ... how to be polite about this? No, I can't. std::set is
> crap. The implementation is a sorted sequence -- if you're lucky,
> this is a heap or a C array, and you've got O(log n) performance.
> But the real killer is that requirement for a std::set<T> is that
> T::operator< exists. Which means, for instance, that you can't
> have a set of complex numbers....
> --

Hallo and Sorry for being OT.
As Arnaud pointed out, you must only overload the  < Operator for the
requested type.
Something like
bool operator < ( const Type& fir, const Type& sec )....
similar to python with __lt__ .
The rest of magic will be  done  by the  compiler/interpreter.
Assoziative Arrays (set,map,multi_set,multi_map) in the classical STL
are implemented as binary trees. Therefore the keys must be comparable
and the access time is O(log n ).
To get a dictionary with O(1), the most  STL implementation support a
extension called hash_set.
The new standard TR1 support unsorted_set ... . You can download it
from Newer gcc runtimes also including the new
subnamespace tr1.
There is no need to implement set in c++ to get O(1).

Greetings Rainer

More information about the Python-list mailing list