An element of an ordering.

Create a new ordering with a single element. O(1)

after t inserts a new element to the ordering, greater than t but less than all existing elements greater than t.

O(1) amortized.

before t inserts a new element to the ordering, less than t but greater than all existing elements less than t.

O(1) amortized.

Check if two elements belong to the same order. O(1)

Compare two elements. O(1)

How many elements are ordered. O(1)

Memory of every element is retained. When you know you are not going to use an element any longer, forget it to release memory. O(1).

After calling forget, an element should not be used. You can check if it is the case with is_valid.