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如在此解决方案）。

And std::deque and std::vector seem to have complementary O(1) and O(n) operations.

I'm guessing that std::set will introduce some O(log n) complexity.

Is there any stl container that supports all three operations that I need in constant time (or amortized constant time)?

Answer 1

If you don't care about order and uniqueness of elements in your container, you can use the following:

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();
  }
}