c++ - 在 O(log(n)) 时间内从 std::set 中随机选择一个元素

Question

有没有办法从 O(log(n)) 中的 std::set 中随机选择一个元素，或者甚至更好的 O(1) 时间？它不需要有一个非常均匀的分布，只是一些相当随机的东西(虽然显然 Even 更好)

查看 std::set::extract 似乎很有希望因为它可能会在恒定时间内将 set 分成两半，但我找不到识别靠近根的节点的好方法，我可以使用 node_type 文档find 没有详细介绍。

如果所有其他方法都失败了，可以将内容复制到一个 std::map 中，其中包含我认为的随 secret 钥是 O(n log(n)) 时间，这将使我分摊 O(log(n)) 时间，但这不是首选解决方案因为在我不想要所有东西的情况下需要一些开销

Answer 1

如果集合中的元素本身均匀分布在某个值域中，那么您可以在该域中生成一个随机值，并使用 std::set::lower_bound 获得第一个值集合中包含的不小于随机值的元素。

鉴于您不需要极其均匀的分布，集合中元素的均匀性要求可能不是非常必要。一个元素被选中的可能性取决于它与其前身元素的相对距离。

对于均匀分布，我认为没有比 *std::next(std::begin(s), random_index) 更好的了，它的复杂度是线性的。

---

要获得具有均匀分布和对数渐近复杂度的良好通用解决方案，您需要除 std::set 之外的另一种数据结构。

特别是，一个不错的选择是 Order statistic tree它通过将其子树的大小添加到节点中来扩充搜索树。 OST有一个Select(i)操作，类似于数组下标操作，同样可以在索引0...N之间随机选择一个元素。

另一种选择是使用排序数组。 sorted 属性可用于保留 std::set 具有的对数查找属性。

不幸的是，标准库既没有顺序统计树，也没有排序数组集。