c – 如何从std :: set中有效地选择一个随机元素

发布时间：2020-12-16 06:00:04 所属栏目：百科来源：网络整理

导读：如何从std :: set中有效地选择一个随机元素？ std :: set :: iterator不是随机访问迭代器.所以我不能直接索引一个随机选择的元素,像我可以为std :: deque或std :: vector 我可以从std :: set :: begin()返回的迭代器,并将其增加到std :: set :: size() – 1

如何从std :: set中有效地选择一个随机元素？

std :: set :: iterator不是随机访问迭代器.所以我不能直接索引一个随机选择的元素,像我可以为std :: deque或std :: vector

我可以从std :: set :: begin()返回的迭代器,并将其增加到std :: set :: size() – 1次,但这似乎在做很多不必要的工作.对于接近集合大小的“索引”,我将最终遍历树的整个上半部分,即使已经知道该元素不会在那里找到.

有更好的方法吗？

以效率的名义,我愿意将“随机”定义为比我在矢量中选择一个随机索引的任何方法更少的随机.称之为“合理随机”.

编辑…

下面有很多有见地的答案.

简短的版本是,即使您可以在log(n)时间中找到特定的元素,您也不能在该时间内通过std :: set接口找到任意元素.

解决方法

改为使用 boost::container::flat_set：

boost::container::flat_set<int> set;
// ...
auto it = set.begin() + rand() % set.size();

插入和删除成为O(N),但我不知道这是否是一个问题.您仍然有O(log N)查找,并且容器是连续的事实总体上的改善通常超过O(log N)插入和删除的损失.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!