how to randomly erase an element in a set?

T

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?
 
A

Alf P. Steinbach

* 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
 
M

Marcel Müller

Hi,
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
 
J

Juha Nieminen

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.)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top