Ordered Sets

[Terry Reedy]

Steven D'Aprano wrote:
> 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?

I think the idea was 2 weakrefs and 1 normal ref instead of 3 normal refs.