how to randomly erase an element in a set?

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

  1. thomas

    thomas Guest

    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
    #1
    1. Advertising

  2. * 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
    #2
    1. Advertising

  3. 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
    #3
  4. 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
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jose luis fernandez diaz
    Replies:
    7
    Views:
    20,182
    Rob Williscroft
    Apr 21, 2004
  2. Davy

    Select element from Set randomly?

    Davy, Aug 22, 2005, in forum: C Programming
    Replies:
    4
    Views:
    361
    Keith Thompson
    Aug 22, 2005
  3. Robert
    Replies:
    6
    Views:
    465
    Robert
    Aug 23, 2005
  4. erase vs. erase

    , Mar 25, 2006, in forum: C++
    Replies:
    7
    Views:
    351
    Pete Becker
    Mar 30, 2006
  5. newbie
    Replies:
    1
    Views:
    288
Loading...

Share This Page