Alf said:
In that case just store the set elements in e.g. a vector, in addition
to the set.
If the elements are large, that can be a waste of space. However, you
can simply store iterators to the set in the vector, and then choose a
random iterator from the vector, use it to erase the element from the
set, and then remove it from the vector (using the swapping trick).
(Of course you now have to be very careful to not to keep iterators to
deleted elements, but good modular design should help keeping the set
and the vector always in sync and prevent any mistakes.)