如何从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)插入和删除的损失.