Ordered Sets

[Scott David Daniels]

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.

--Scott David Daniels
Scott.Daniels at Acm.Org