如何在 O(n) 时间内选择 std::set 中的随机元素？

Question

这个问题增加了约束。

我愿意允许不统一的选择，只要不偏不倚。

鉴于“集合通常实现为二叉搜索树”，我希望他们会包含某种用于平衡的深度或大小信息，我希望您可以对树进行某种加权随机游走。但是我不知道有任何远程便携式方法可以做到这一点。

编辑：约束不适用于摊销时间。

Answer 1

引入大小等于 set 的数组。使数组元素保存集合中每个元素的地址。生成以数组/集合大小为界的随机整数R，在由R索引的数组元素中选取地址并取消引用它以获取集合的元素。

Answer 2

我不知道如何仅使用 std::set 来完成此操作，因此您可能需要不同的数据结构。正如维克多·索罗金（Victor Sorokin）所说，你可以将集合与向量组合起来。使用 map 和 vector 代替 set。映射::迭代器>。每个键的值都是向量的索引，向量的每个元素都指向映射元素。向量元素没有特定的顺序。添加元素时，将其放在向量的末尾。当删除一个元素并且它不是向量中的最后一个元素时，请将最后一个元素移动到已删除元素的位置。

Answer 3

如果您知道集合中元素的分布，则可以随机选择键（具有相同的分布）并使用std::set::lower_bound。不过，这样的情况有很多。

int main() {
    std::set<float> container;
    for(float i=0; i<100; i += .01)  
        container.insert(i);
    //evenish distribution of 10000 floats between 0 and 100.
    float key = std::rand() *10000f / RAND_MAX; //not random, sue me
    std::set<float>::iterator iter = container.lower_bound(key); //log(n)
    std::cout << *iter;
    return 0;
}

Answer 4

您可以使用此构造函数来制作地图的随机排序副本

template <class InputIterator>
set(InputIterator f, InputIterator l,
    const key_compare& comp)

..并传递一个比较键的哈希值（或其他一些确定性传播函数）的比较器。然后根据这个新的值获取“最小”键地图。

您可以构建一次地图，然后在对“随机”元素的多个请求中分摊成本。

Answer 5

对于 std::unordered_set; s:

1) 在 min(s)..max(s) 中取随机 R

2) if R in >s：返回 R

3)

newIter = s.insert(R).first;
newIter++;
if (newIter == s.end()) {
    newIter = s.begin();
}
auto result = *newIter;
s.erase(R);
return result;

对于有序集 (std::set)，概率取决于元素之间的距离。 unordered_set 通过哈希随机化。

我希望这能有所帮助。

PS 将 std::set 转换为 std::set> （其中对中的第一个元素是第二）使该方法适用于任何可哈希的 V。