Snapshot set with frozen insertion-order iterators

Implement SnapshotSet, a set of integers whose iterators are frozen at the moment they are created.

API

• add(value) -> bool: insert value. Return False and do nothing if it is already present.
• remove(value) -> bool: delete value. Return False if it is not present.
• contains(value) -> bool: whether value is currently in the set.
• iterator(): return an iterator over the elements that were in the set when iterator() was called, in insertion order.

Rules

• Changes made after an iterator is created (adds, removes, re-adds) must never affect what that iterator returns, even if the iterator is only partly consumed when they happen.
• Insertion order means the order of the most recent add. A value that is removed and added again moves to the end.
• Many iterators may be open at once, each with its own snapshot.
• Aim for O(1) add, remove and contains. Creating an iterator should not copy the whole set.

Example 1

s.add(4); s.add(9); s.add(6)
it = s.iterator()
s.remove(9)
s.add(3)
list(it)            -> [4, 9, 6]
list(s.iterator())  -> [4, 6, 3]

Example 2

s.add(1); s.add(2)
a = s.iterator()
next(a)             -> 1
s.remove(1); s.add(1)
list(a)             -> [2]
list(s.iterator())  -> [2, 1]