如何在std::set中选择随机元素？

Question

如何在

std::set

中选择随机元素？

我天真地尝试过这个：

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  return *(s.begin() + r); // compile error
}

但是

operator+

这样是不允许的。

Answer 1

您可以使用

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);
  auto r = rand() % s.size(); // not _really_ random
  auto n = *select_random(s, r);
}

哪里

template<typename S>
auto select_random(const S &s, size_t n) {
  auto it = std::begin(s);
  // 'advance' the iterator n times
  std::advance(it,n);
  return it;
}

Answer 2

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?

Answer 3

第一个解决方案：O(log n) 时间/O(1) 空间（不均匀！）

上面评论中的假设，可以在 O(log(n)) 中完成（与 O(n) 对于

std::advance

），无需向量（使用 O(n) 更多空间）使用我描述的方法here。

本质上，你：

• 检查集合是否为空（如果是，则没有希望）
• 生成随机值
• 如果已经存在，则返回它，否则插入它
• 获取一个迭代器

  it

• 如果末尾有

  *(it++)

  ，则获取随机元素为

  *(set.begin())

  或

  it

• 在删除插入的元素之前不要返回它

n.b：正如Aaron所指出的，该元素不是随机选择的。您需要构建与集合中的元素具有相同分布的随机元素，以实现均匀轮询。 第二个解决方案：

O(1)

时间 / O(n) 空间（均匀）

davidhigh

已经给出了向量的解决方案，但是存在一个问题，因为当你pop堆栈中的一个元素时，你将必须在O(n)中执行线性搜索，或者你可以每个重建你的向量当你想要检索一个随机元素时，但这也是O(n)。 为了避免这个问题并将插入/删除保持为

O(log n)

，您可以保留 std::unordered_set 并使用与第一个解决方案

类似的方法

来获取 O(1) 中的随机元素. p.s：如果你的元素很大，你可以使用一组无序的指针（带有修改后的哈希器）来节省一些内存。

Answer 4

本文

中给出的解决方法可能会很方便。 主要思想是使用排序向量，然后查找函数

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;
 }
};

对于更复杂的实现，您还可以考虑

此页面

。 编辑：或者更好的是，使用

boost::container::flat_set

，它使用上面的想法实现集合，即作为排序向量。

Answer 5

将是一种方法，尽管不漂亮；

Answer 6

// making set
unordered_set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);

// logic
int idx = rand()%s.size();
auto it = s.begin();
for (int i = 0; i < idx; i++)
{
    it++;
}
return *it;

Answer 7