Details about pythons set implementation

[r.grimm at science-computing.de]

On Jan 4, 6:08 pm, Sion Arrowsmith <si... at chiark.greenend.org.uk>
wrote:
> Hrvoje Niksic  <hnik... at xemacs.org> 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 www.boost.org. Newer gcc runtimes also including the new
subnamespace tr1.
There is no need to implement set in c++ to get O(1).


Greetings Rainer