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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.