Details about pythons set implementation

Diez B. Roggisch deets at
Fri Jan 4 18:41:02 CET 2008

bukzor schrieb:
> On Jan 4, 9:08 am, Sion Arrowsmith <si... at>
> wrote:
>> 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....
>> --
>> \S -- si... at --
>>    "Frankly I have no feelings towards penguins one way or the other"
>>         -- Arthur C. Clarke
>>    her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump
> Why cant you implement < for complex numbers? Maybe I'm being naive,
> but isn't this the normal definition?
>     a + bi < c + di iff sqrt(a**2 + b**2) < sqrt(c**2, d**2)
> How do you implement a set without sorting?
> Are you expecting better than O(log n)?

Of course, hashing does O(1) (most of the time, with a sane hash of course.)


More information about the Python-list mailing list