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

Question

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

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

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

有更好的方法吗？

在效率的名义上,我愿意将"随机"定义为比我可能用于在向量中选择随机索引的任何方法更少随机.称之为"合理随机".

编辑...

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

简短版本是即使您可以在log(n)时间内找到特定元素,也无法通过界面在该时间内找到任意元素.std::set

Answer 1

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

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