Unordered_set迭代器隨機

Question

我閱讀了谷歌關於設計支持快速插入，擦除和擦除隨機元素的類的訪問問題。我在考慮cpp中的unordered_set，插入和擦除已經存在。然後，爲了移除隨機元素，我認爲unordered_set的begin（）方法指向一個隨機元素，我可以獲取它的值並從集合中刪除它。這是否總是作爲從集合中刪除隨機值的工作？謝謝！

編輯：隨意評論，如果你可以想到一些其他的數據結構，並不一定是unordered_set。

Answer 1

我不認爲採取begin()的價值將是足夠隨機的。也許最好自己做一些隨機化。一種方法是 隨機選擇從哈希表桶，並採取begin()「那桶的價值：

#include <unordered_set> 
#include <random> 

// Assume that T is some arbitrary type for which std::hash<T> is defined 
std::unordered_set<T> myset; 

// put some elements into the set 

unsigned bcount = myset.bucket_count(); // get the number of buckets 
std::mt19937 rng(time(0)); // random number generator (seeded with time(0)) 

// returns a number in [0, bcount - 1] 
uniform_int_distribution<unsigned> d(0, bcount - 1); 

// returns a random bucket index 
unsigned rbucket = d(rng); 

// returns the beginning element of the selected bucket 
auto it = myset.begin(rbucket); 
myset.erase(it); // removes the selected element 

這當然比坐begin()更隨機的值，但仍然不統一，因爲水桶的起始元素是首選。如果要保證在整個容器均勻分佈，你可以簡單地採取隨機值r在[0，myset.size()-1]，並通過一系列迭代達到這一元素：

#include <unordered_set> 
#include <random> 

// Assume that T is some arbitrary type for which std::hash<T> is defined 
std::unordered_set<T> myset; 

// put some elements into the set 

std::mt19937 rng(time(0)); // random number generator (seeded with time(0)) 
uniform_int_distribution<unsigned> d(0, myset.size() - 1); 

// returns a random number from [0, myset.size() - 1] 
unsigned r = d(rng); 

// iterates through the container to the r-th element 
auto it = myset.begin(); 
for(; it != myset.end() && r > 0; ++it, r--); 
myset.erase(it); // erasing the selected element 

這消除了一個元素（僞）統一概率，但效率不高，因爲它需要迭代容器。我認爲你不能比使用std::unordered_set做得更好。