用于选择和删除随机项目的STL容器？

Question

我正在实现的算法具有以下结构：

while C is not empty
  select a random entry e from C
  if some condition on e
    append some new entries to C (I don't care where)
  else
    remove e from C

重要的是，随机选择循环e的每个迭代（具有统一的概率）。>>

理想情况下，select，append和remove步骤均为O（1）。

[如果我理解正确，则使用std::list，append和remove步骤将为O（1），但随机选择将为O（n）（例如，使用std::advance中的this solution）。

[std::deque和std::vector似乎具有互补的O（1）和O（n）运算。

我猜测std::set将引入一些O（log n）复杂度。

是否有stl容器支持我在恒定时间（或摊销的恒定时间）中需要的全部三个操作？

我正在实现的算法具有以下结构：如果C不为空，如果e上的某些条件在C上添加了一些新条目（我不在乎，否则...]，则从C中选择一个随机条目e）[

Answer 1

如果您不关心容器中元素的顺序和唯一性，则可以使用以下方法：

std::vector<int> C;
while (!C.empty()) {
  size_t pos = some_function_returning_a_number_between_zero_and_C_size_minus_one();
  if (condition())
    C.push_back(new_entry);
  else {
    C[i] = std::move(C.back());
    C.pop_back();
  }
}

Answer 2

如果元素顺序应该一致，则不存在这样的容器。您可以选择O(1)并在vector或deque后面附加（摊销），但删除为O(n)。您可以使用O(1)，但可以使用unordered_map来插入和删除selection is O(n)（平均大小写）。 O(n)使您可以list进行添加和删除，但可以选择O(1)。没有容器可以让您获得全部三个操作的O(n)。找出最不常用的容器，选择一个对其他容器有效的容器，然后接受一个操作会比较慢。

Answer 3

我猜std :: set将引入一些O（log n）复杂度。