On Jan 4, 6:08 pm, Sion Arrowsmith <[EMAIL PROTECTED]> wrote: > Hrvoje Niksic <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
