c++ - 使用 boost::random 从要删除元素的 std::list 中进行选择

Question

查看此 related question更通用地使用 Boost Random 库。

我的问题涉及从 std::list 中选择一个随机元素，执行一些操作，这可能包括从列表中删除元素，然后选择另一个随机元素，直到满足某些条件满意。

boost 代码和 for 循环大致如下所示:

// 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
    //[...]
}

我的问题是一旦对元素执行的操作导致删除元素，variate_generator 就有可能在列表中选择无效索引。我不认为每次都完全重新创建 variate_generator 是有意义的，尤其是当我用 time(0) 为它播种时。

Answer 1

我假设 MyClass & mc = myList.begin() + index; 只是伪代码，因为 begin 返回一个迭代器，我不认为列表迭代器(非随机访问)支持operator+。

据我所知，在这种情况下，使用变量生成器的三个基本选项是:

• 当您删除一个项目时重新创建生成器。
• 对生成的索引进行过滤，如果它 >= 列表的当前大小，请重试直到获得有效索引。请注意，如果您删除大量索引，这也会变得非常低效。
• 将节点保留在列表中但将其标记为无效，因此如果您尝试对该索引进行操作，它会安全地停止操作。这只是第二个选项的不同版本。

或者，您可以设计一种能够适应容器大小变化的不同索引生成算法。