Using boost :: random to select from std :: list where items are removed

Question

See this related question for a more general use of the Boost Random library.

My questions include selecting a random item from std::list , performing some operation that could potentially involve removing an item from the list, and then selecting another random item until some condition is met.

The boost and for loop code look something 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 operations performed on an element result in the element being deleted, variate_generator can select an invalid index in the list. I don’t think it makes sense to completely recreate variate_generator every time, especially if I sow it with time (0).

Answer 1

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

As far as I can tell, with the variation generator your three main options in this case are:

• Restore the generator when you delete an item.
• Filter the generated index, and if it> = the current size of the list, try again until you get a valid index. Please note: if you delete a large number of indexes, this can become quite inefficient.
• Leave the node in the list, but mark it invalid, so if you try to use this index, it does not work safely. This is just another version of the second option.

Alternatively, you can develop another index generation algorithm that can adapt to the size of the container change.

Answer 2

You can create your own uniform_contained_int distribution class that accepts the container in its constructor, aggregates the uniform_inter, and recreates the uniform distribution every time the container changes size. See the description of uniform_int what methods you need to implement to create your distribution.

Answer 3

I think you need to worry more about performance. Especially this:

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

is not a particularly fast way to get the index element.

I would turn it into something similar (which should work 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-- 

if you do not need random permutation of elements.