I think you can implement this efficiently by building the ordered set using a modern Python dict (which preserves insertion order)
- whose keys are the elements of the set, and
- whose values are integers whose order reflects the ordering.
Set removal is just removal from the dict, and takes O(1) amortized time.
Set addition is adding to the mapping a key-value pair equal to the element being added and a new value that is one larger than than the last element’s value (next(reversed(d.values())) + 1). It also takes O(1) amortized time. (If the next integer is too big, then you can renumber all the elements in linear time by iterating the mapping. This doesn’t change the amortized time.)
Finally, set intersection can be efficiently implemented:
- For each element in the smaller set, filter using the larger set, adding these to a list.
- Sort this list using the integers from the dict of the first set.
- Finally, add these sorted elements to a new ordered set.
This is O(mlogm) where m is the shorter set.