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

Question

这个问题有一个附加的约束.

我愿意允许不均匀的选择,只要它不偏不倚.

鉴于" 集合通常实现为二叉搜索树 ",我希望它们包含某种深度或大小信息以进行平衡,我希望你可以对树进行某种加权随机游走.但是,我不知道有任何远程可移植的方式来做到这一点.

编辑:约束不是分摊的时间.

Answer 1

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

Answer 2

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

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

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

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