如何在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?