Ordered Sets

[Steven D'Aprano]

On Fri, 20 Mar 2009 11:50:28 -0700, Scott David Daniels wrote:

> Raymond Hettinger wrote:
>> [Aahz]
>>> The doubly-linked list part is what's sick and perverted.
>> 
>> The doubly-linked list part is what gives it big-oh running times the
>> same as regular sets.  If the underlying sequence is stored as a list,
>> then deletion goes from O(1) to O(n). If the insertion times are
>> recorded in a dictionary, then the insertion order has to be sorted
>> prior to iteration which makes iteration go from O(n) to O(n log n).
> 
> The double-linked list part could be done with weakrefs and perhaps Aahz
> would relax a bit.

I'm not sure whether Aahz's description is meant to be taken seriously, 
or if there is a smiley hidden in his post. After all, doubly-linked 
lists are a standard building block in data structure design.

But assuming it is meant as a serious criticism, I'm not sure that I like 
the idea of using weakrefs. I think it is a feature, not a bug, that 
sets, lists and dicts keep a reference to the items in them. I think it 
would be bizarre if putting an item into an OrderSet meant that you 
needed to put it somewhere else as well to prevent it being garbage 
collected.

Or have I misunderstood the consequences of using weakrefs?



-- 
Steven