Ordered Sets

[Raymond Hettinger]

[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).


Raymond