Ordered Sets

[Aaron Brady]

On Mar 20, 1:50 pm, Scott David Daniels <Scott.Dani... at Acm.Org> 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.
>
> --Scott David Daniels
> Scott.Dani... at Acm.Org

Whether the structure holds one reference to its "containees" or three
doesn't matter.  But you're right, weakrefs are relaxing.

I pronounce it the perfect data structure.  Tell your CS 200 professor
immediately.  Shout it from the rooftops.

IINM if I'm not mistaken, an O(1) 'multiadd' method wouldn't be hard
either.  If the item exists already, insert it in place in the linked
list.