Sub-linear-time ordered set (!= sorted set) implementation?
Another pretty simple solution is a balanced binary search tree with threading (an overlaid linked list passing through all the nodes of the tree in order of their original insertion). Then insertion/search/removal are all O(log n), and iteration is O(n). You just update insert/remove to either append to the linked list or remove the node from it.