日志中STL集/映射中的随机元素

Question

由于C++ STL集合/图作为红黑树实现的,它应该是不仅可以做insert,delete和find在O(log n)的时间,而且getMin,getMax,getRandom.据我所知,前两个有相同的begin()和end()(是正确的吗？).最后一个怎么样？我怎样才能做到这一点？

到目前为止我唯一的想法就是使用advance随机参数,然而这需要线性时间......

编辑:'随机'应指均匀分布

Answer 1

begin()等效于一个getMin操作,但end()返回一个超过最大值的迭代器,所以它就是rbegin().

至于getRandom:假设你的意思是以一致的概率随机获得任何项目,这可能在AVL树中的O(lg n)时间内,但我不知道如何在红黑树中有效地做到这一点.你怎么知道给定节点左右有多少个子树而不计算n/2 = O(n)时间？既然std::set并且std::map不直接访问它们的底层树,你将如何遍历它？

我看到三种可能的解决方案

• 改为使用AVL树;
• vector与元素保持平行map或set平行;
• 使用带有排序和随机访问视图的Boost :: MultiIndex容器.

编辑:Boost.Intrusive也可以做到这一点.