如何在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); 

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

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

Answer 2

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

会做的一种方式，虽然不漂亮;

Answer 3

如果随机访问很重要，并且您可以忍受O（N）平均插入工作量，那么在this paper中给出的解决方法可能会很方便。

主要的想法是使用排序后的向量，然后查找函数std::lower_bound。这个查找需要O（log N），就像在一个正常的集合中一样。此外，（随机）插入需要O（N），因为所有后续元素必须像在法向量中一样移位（并且可能会执行重新分配）。然而，后面的插入是不变的（除了重新分配，你可以通过调用reserve()来避免这种情况，使用足够大的存储空间）。

最后，问题的主要观点：随机访问是O（1）。只需从[0, V.size()-1]的统一分布中抽取一个随机数i，并返回相应的元素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，它使用上述思想实现该集合，即作为排序向量。

Answer 4

首个解决方案： O（log n）的时刻/ O（1）空间

一个虚拟的评论上面，它可以在O（日志完成（不统一！） （n））（vs O（n） for std::advance）通过使用我描述的方法here而没有载体（使用O（n）更多空间）。

从本质上讲，你：

• 检查，如果设置为空（如果是，是没有希望的）
• 生成一个随机值
• 如果已经有恢复它在其他插入
• 得到一个迭代器it它
• 如果it末
得到或随机元素为 *(it++)
• 换来的却没有删除元素之前您插入

n.b：由于亚伦元素指出，随机没有选择均匀。您需要构建与集合中的元素具有相同分布的随机元素以进行统一轮询。

二解决方案： O（1）时刻/ Ø在空间（统一）（N）

davidhigh已经给了向量的解决方案，但有一个问题，因为当你pop您的堆栈元素，您将不得不在O（n）中执行线性搜索，或者您可以在每次要检索随机元素时重建矢量，但也是O（n）。

为了避免这个问题，并保持插入/删除对O（log n）的，你可以保持一个std::unordered_set并使用similar method的第一个解决方案中获得一个随机元素O（1）。如果你的元素很大，你可以使用一组无用的指针（带有修改的散列函数）来节省一些内存。

Answer 5

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?