c++ - 获得std::set中间(中位数)的有效方法？

Question

std::set 是一个排序树。它提供了 begin 和 end 方法，因此我可以获得最小值和最大值以及 lower_bound 和 upper_bound 用于二进制搜索。但是，如果我想让迭代器指向中间元素(或者如果那里有偶数个元素，则其中之一)怎么办？

有没有一种有效的方法(O(log(size)) 而不是 O(size)) 来做到这一点？

{1} => 1
{1,2} => 1 or 2
{1,2,3} => 2
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2})
{1,312,10000,14000,152333} => 10000

PS:Same question in Russian.

Answer 1

根据您插入/删除项目与查找中间/中位数的频率，一种可能比显而易见的解决方案更有效的解决方案是为中间元素保留一个持久迭代器，并在您插入/删除项目时更新它放。有一堆需要处理的边缘情况(奇数与偶数项目，删除中间项目，空集等)，但基本思想是当您插入一个小于当前中间项目的项目时，您的中间迭代器可能需要递减，而如果您插入更大的迭代器，则需要递增。删除则相反。

在查找时，这当然是 O(1)，但它在每次插入/删除时也有本质上 O(1) 的成本，即 N 次插入后的成本是 O(N)，这需要在足够长的时间内摊销查找次数，使其比暴力破解更有效。