我从 Google 了解到一个关于设计支持快速插入、删除和删除随机元素的类的面试问题。我在考虑cpp中的unordered_set,insert和erase已经有了。然后对于删除随机元素,我认为 unordered_set 的 begin() 方法指向一个随机元素,我可以获取它的值并将其从集合中删除。这是否总能起到从集合中删除随机值的作用?谢谢!
编辑:如果您能想到一些其他数据结构,请随意发表评论,不必是 unordered_set。
最佳答案
我认为 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
in [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
做得更好。
关于c++ - Unordered_set迭代器随机,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32644084/