如何有效地选择从STD的随机元素::设为 [英] How to efficiently select a random element from a std::set

问题描述

我怎样才能有效地选择一个随机元素的std ::设为？

How can I efficiently select a random element from a std::set?

A 的std ::设置：迭代是双向迭代器。所以我不能直接指数随机选取的元素像我所能为的std :: deque的或的std ::矢量

A std::set::iterator is a bidirectional iterator. So I can't directly index a randomly chosen element like I could for a std::deque or std::vector

我的可以的采取从迭代器返回的std ::设置::开始（）并加一 0 到的std ::设置::大小（） - 1 次，但似乎做了很多不必要的工作。对于指数接近设定的大小，我最终会遍历树的整个上半场，即使它已经知道的元素不会被发现在那里。

I could take the iterator returned from std::set::begin() and increment it 0 to std::set::size()-1 times, but that seems to be doing a lot of unnecessary work. For an "index" close to the set's size, I would end up traversing the entire first half of the tree, even though it's already known the element won't be found there.

有没有更好的方法？

在效率的名义，我愿意来定义随机为的随机的的比什么方法，我可能会用选择随机指标的载体。称之为合理的随机。

In the name of efficiency, I am willing to define "random" as less random than whatever approach I might have used to choose a random index in a vector. Call it "reasonably random".

修改...

下面许多有见地的答案。

Many insightful answers below.

短的版本是，即使你能找到的的具体的中的的log（n）的时候，你无法找到的任意在这段时间通过的std ::设为界面元素。

The short version is that even though you can find a specific element in log(n) time, you can't find an arbitrary element in that time through the std::set interface.

推荐答案

使用的 的boost ::容器:: flat_set 来代替：

Use boost::container::flat_set instead:

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

插入和缺失成为O（N）不过，我不知道这是一个问题。你还有为O（log N）的查找，而事实上，该容器是连续的给出了一个全面改善，往往胜过邻损失（日志N）的插入和删除。

Insertions and deletions become O(N) though, I don't know if that's a problem. You still have O(log N) lookups, and the fact that the container is contiguous gives an overall improvement that often outweighs the loss of O(log N) insertions and deletions.

这篇关于如何有效地选择从STD的随机元素::设为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！