# how to randomly erase an element in a set?

Discussion in 'C++' started by thomas, Jun 25, 2009.

1. ### thomasGuest

We cannot use "set.begin()+rand()%MAX" to randomly locate an element
in a set?
Is there any convenient way to erase an element of a set randomly?

thomas, Jun 25, 2009

2. ### Alf P. SteinbachGuest

* thomas:
> We cannot use "set.begin()+rand()%MAX" to randomly locate an element
> in a set?
> Is there any convenient way to erase an element of a set randomly?

It seems that you want to do this in at most logarithmic time.

In that case just store the set elements in e.g. a vector, in addition to the set.

Erasing in constant time from the vector is simple: swap with the last element,
resize down 1 notch.

Remember to also erase in the set. ;-)

Cheers & hth.,

- Alf

--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! Just going there is good. Linking
to it is even better! Thanks in advance!

Alf P. Steinbach, Jun 25, 2009

3. ### Marcel MüllerGuest

Hi,

thomas wrote:
> Is there any convenient way to erase an element of a set randomly?

there was a very similar problem in the thread "Optimisation:
Specialised Container Needed" just ago. Mabe that helps.

Marcel

Marcel Müller, Jun 25, 2009
4. ### Juha NieminenGuest

Alf P. Steinbach wrote:
> 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.)

Juha Nieminen, Jun 25, 2009