你可以用 std::advance 方法。

#include <set>
#include <algorithm>

int main() {
  using namespace std;
  // generate a set...
  set<int> s;
  for( int i = 0; i != 10; ++i ) s.insert(i);

  set<int>::const_iterator it(s.begin());

  // 'advance' the iterator 5 times
  advance(it,5);
}

第一个解决方案: O(log n) 及时/ O(1) 在太空中(不统一!)

在上面的评论中假设的,可以在 O(log(n)) (vs) o(n) 对于 std::advance )无矢量(使用 o(n) 更多空间)使用我描述的方法 here .

本质上,你:

• 检查集合是否为空(如果为空,则没有希望)
• 生成随机值
• 如果已经存在,返回它,否则插入它
• 获取一个迭代器 it 关于它
• 将随机元素作为 *(it++) 或 *(set.begin()) 如果 它 最后
• 在删除插入的元素之前不返回

注意:正如 亚伦 未选择元素 均匀地 随意地。您需要构建与集合中的元素分布相同的随机元素,以实现统一的轮询。

第二种解决方案: O(1) 及时/ o(n) 空间(统一)

戴维高 已经用向量给出了解决方案,但有一个问题,因为当 流行音乐 作为堆栈的一个元素,必须在 o(n) 或者你可以在每次你想要检索一个随机元素的时候重建你的向量,但是那是 o(n) 也是。

要避免此问题并将插入/删除保持为 O(log n) ,您可以保留 std::unordered_set 并使用 similar method 得到一个随机元素的第一个解 O(1) .

P.S:如果您的元素很大,那么可以使用一组无序的指针(使用修改过的哈希表)来释放一些内存。

如果随机访问很重要,并且您可以使用o(n)平均插入工作量,那么 this paper 可能很方便。

这里的主要思想是使用排序向量,然后查找函数 std::lower_bound . 这样,查找会像在正常集合中一样接受O(log n)。此外,(随机)插入需要O(N),因为所有以下元素必须像在法向量中一样移动(并且可能执行重新分配)。但是,在后面插入是常量(除了重新分配之外)。你可以打电话来避免 reserve() 有足够的存储空间)。

最后,问题的要点是:随机访问是O(1)。 画一个随机数 i 从均匀分布到 [0, V.size()-1] ,并返回相应的元素 V[i] .

这里是本文的代码基础,它实现了这个排序向量。根据需要进行扩展:

template <class T, class Compare = std::less<T> >
struct sorted_vector {
 using std::vector;
 using std::lower_bound;
 vector<T> V;
 Compare cmp; 
 typedef typename vector<T>::iterator iterator;
 typedef typename vector<T>::const_iterator const_iterator;
 iterator begin() { return V.begin(); }
 iterator end() { return V.end(); }
 const_iterator begin() const { return V.begin(); }
 const_iterator end() const { return V.end(); }

 //...if needed, implement more by yourself

 sorted_vector(const Compare& c = Compare()) : V(), cmp(c) {}
 template <class InputIterator>
 sorted_vector(InputIterator first, InputIterator last, Const Compare& c = Compare())
 : V(first, last), cmp(c)
 {
 std::sort(begin(), end(), cmp);
 }

 //...

 iterator insert(const T& t) {
     iterator i = lower_bound(begin(), end(), t, cmp);
     if (i == end() || cmp(t, *i))
        V.insert(i, t);
      return i;
 }
 const_iterator find(const T& t) const {
     const_iterator i = lower_bound(begin(), end(), t, cmp);
      return i == end() || cmp(t, *i) ? end() : i;
 }
};

对于更复杂的实现,您还可以考虑 this page .

编辑:或者更好,使用 boost::container::flat_set ,它使用上述思想实现集合,即作为排序向量。

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  std::set<int>::iterator it = s.begin();
  for (; r != 0; r--) it++;
  return *it;
}

这是一种方法,虽然不漂亮;

C++ 17 std::sample

这将是一种方便的方法,尽管不是非常有效(o(n))的方法:

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

int main() {
    std::set<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                3, std::mt19937{std::random_device{}()});
    for (auto i : out)
        std::cout << i << std::endl;
}

但我认为,为了提高效率,你只需要复制到另一种结构: How to select a random element in std::set in less than O(n) time?