Using boost::random to select from an std::list where elements are being removed

See this related question on more generic use of the Boost Random library.

My questions involves selecting a random element from an std::list, doing some operation, which could potentally include removing the element from the list, and then choosing another random element, until some con开发者_如何学Pythondition is satisfied.

The boost code and for loop look roughly like this:

// create and insert elements into list
std::list<MyClass> myList;
//[...]

// select uniformly from list indices
boost::uniform_int<> indices( 0, myList.size()-1 );    
boost::variate_generator< boost::mt19937, boost::uniform_int<> > 
  selectIndex(boost::mt19937(), indices);

for( int i = 0; i <= maxOperations; ++i ) {
    int index = selectIndex();
    MyClass & mc = myList.begin() + index;

    // do operations with mc, potentially removing it from myList
    //[...]
}

My problem is as soon as the operations that are performed on an element result in the removal of an element, the variate_generator has the potential to select an invalid index in the list. I don't think it makes sense to completely recreate the variate_generator each time, especially if I seed it with time(0).

I assume that MyClass & mc = myList.begin() + index; is just pseudo code, as begin returns an iterator and I don't think list iterators (non-random-access) support operator+.

As far as I can tell, with variate generator your three basic options in this case are:

• Recreate the generator when you remove an item.
• Do filtering on the generated index and if it's >= the current size of the list, retry until you get a valid index. Note that if you remove a lot of indexes this could get pretty inefficient as well.
• Leave the node in the list but mark it invalid so if you try to operate on that index it safely no-ops. This is just a different version of the second option.

Alternately you could devise a different index generation algorithm that's able to adapt to the container changing size.

You could create your own uniform_contained_int distribution class, that accept a container in its constructor, aggregates a uniform_int, and recreates the uniform_distribution each time the container changes size. Look at the description of the uniform_int which methods you need to implement to create your distribution.

I think you have more to worry about performance-wise. Particularly this:

std::list<MyClass> myList;
myList.begin() + index;

is not a particularly fast way of geting index-th element.

I would transform it into something like this (which should operate on a random subsequence of the list):

X_i ~ U(0, 1) for all i
left <- max_ops
N <- list size
for each element
  if X_i < left/N
    process element
    left--
  N--

provided you don't need the random permutation of the elements.