1

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

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::listandappend步骤remove将是 O(1) 但随机选择将是 O(n) （例如，std::advance在此解决方案中使用）。

并且似乎有互补的 O(1) 和 O(n) 操作std::deque。std::vector

我猜这std::set会引入一些 O(log n) 复杂性。

是否有任何 stl 容器支持我在恒定时间（或摊销恒定时间）内需要的所有三个操作？

4

3 回答 3

5

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

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();
  }
}
于 2020-03-19T22:13:21.220 回答
1

如果元素顺序应该一致，则不存在这样的容器。您可以使用or获得O(1)选择和（摊销）附加，但删除是. 您可以使用 获得（平均情况）插入和删除，但选择是. 让你追加和删除，但选择。没有容器可以让您完成所有三个操作。找出最不常用的一个，选择一个适用于其他容器的容器，接受一个操作会更慢。vectordequeO(n)O(1)unordered_mapO(n)listO(1)O(n)O(1)

如果容器的顺序与使用 3365922 的评论无关，则可以在 / 上完成删除步骤，方法O(1)是vector使用deque最终swap元素对要删除的元素执行 ping 操作，然后执行pop_back.

于 2020-03-19T22:07:15.817 回答
1

我猜 std::set 会引入一些 O(log n) 复杂性。

不完全的。集合中的随机选择具有线性复杂性。

是否有任何 stl 容器支持我在恒定时间（或摊销恒定时间）内需要的所有三个操作？

严格来说没有。

但是，如果您不关心元素的顺序，那么您可以在恒定时间内从向量或双端队列中删除。随着要求的放宽，所有操作都将具有恒定的复杂性。

如果您确实需要保持操作之间的顺序，只要元素的顺序不需要影响随机分布（即您想要均匀分布），恒定的复杂性仍然是可能的。解决方案是使用混合方法：

将值存储在链表中。将迭代器存储到向量中的每个元素。使用向量进行随机选择；使用保持元素顺序的迭代器擦除列表中的元素；从向量中擦除迭代器而不保持迭代器的顺序。向列表中添加元素时，请记住添加迭代器。

于 2020-03-19T22:11:39.333 回答