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
提示： 同样的问题有俄语版本。
根据您插入/移除项与查找中间/中位数的频率，比明显做法更高效的可能解决方案是保持对中间元素的持久迭代器，并在插入/删除集合中的项时更新它。这将需要处理一堆边缘情况（奇数和偶数项，移除中间项，空集等），但基本思想是，当您插入小于当前中间项的项时，您的中间迭代器可能需要减少，而如果您插入较大的项，则需要增加。从移除的角度看则相反。
在查找时，这当然是O（1），但每次插入/删除也实质上具有O（1）成本，即N次插入后的O（N），需要分摊到足够数量的查找中，才能使其比暴力方法更高效。
根据你插入/删除项目与查找中间/中位数的频率，可能比显而易见的解决方案更有效的解决方案是保持对中间元素的持久迭代器，并在插入/删除项目时更新它。需要处理一堆边缘情况（奇数 vs 偶数数量的项目，删除中间项目，空集等），但基本想法是当您插入小于当前中间项的项目时，您的中间迭代器可能需要递减，而如果您插入大于当前中间项的项，则需要递增。删除操作则相反。
void balance(multiset<int> &small, multiset<int> &big)
{
while (true)
{
int ssmall = small.size();
int sbig = big.size();
if (ssmall == sbig || ssmall + 1 == sbig) break; // OK
if (ssmall < sbig)
{
// big to small
auto v = big.begin();
small.emplace(*v);
big.erase(v);
}
else
{
// small to big
auto v = small.end();
--v;
big.emplace(*v);
small.erase(v);
}
}
}
auto medium = big.begin();
cout << *medium << endl;
auto v = big.begin();
if (v != big.end() && new_item > *v)
big.emplace(new_item );
else
small.emplace(new_item );
balance(small, big);
std :: set如果存在重复项，就不会“失败”，因为按定义它不能有这样的。我建议你创建一个关于std::multiset的新问题，并将此答案移动到那里。 PS.版主可以在不丢失分数的情况下在问题之间移动答案。 - R2RT获取二叉搜索树的中间节点的时间复杂度为O(size)。您可以使用std::advance()来获取，具体方法如下：
std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
std::advance 在这种情况下只是调用 ++ 对应的次数。 - Qwertiy请注意，std::set不会存储重复的值。如果您插入以下值{1, 2, 3, 3, 3, 3, 3, 3, 3}，您将检索到的中位数是2。
std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;
如果想在计算中位数时包括重复项，可以使用 std::multiset（例如：{1, 2, 3, 3, 3, 3, 3, 3, 3} 的中位数为 3）：
std::multiset<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;
如果你仅仅是为了获取中位数而需要数据排序，我认为使用普通的 std::vector + std::sort 更好。
在进行大样本测试和多次迭代后，我使用 std::vector 和 std::sort 完成测试只用了5秒钟，而使用 std::set 或 std::multiset 则需要13到15秒。当然，实际表现会因数据大小和重复值数量的不同而有所差异。
std::multiset，以防止像我这样的人犯同样的错误。但你是对的，它并没有直接回答问题。但是，在次要答案中提供更多信息不会有害吧？ - Norgannon正如 @pmdj 所说，我们使用迭代器来跟踪中间元素。以下是以下内容的代码实现：
class RollingMedian {
public:
multiset<int> order;
multiset<int>::iterator it;
RollingMedian() {
}
void add(int val) {
order.insert(val);
if (order.size() == 1) {
it = order.begin();
} else {
if (val < *it and order.size() % 2 == 0) {
--it;
}
if (val >= *it and order.size() % 2 != 0) {
++it;
}
}
}
double median() {
if (order.size() % 2 != 0) {
return double(*it);
} else {
auto one = *it, two = *next(it);
return double(one + two) / 2.0;
}
} };
随意复制并使用此代码的任何部分。如果没有重复，也可以使用set而不是multiset。
vector<int> data;
// fill data
std::sort(data.begin(), data.end());
auto median = data[data.size() / 2];
O(n)，但我希望插入和查询都能以O(lb(n))的速度工作。我知道使用隐式键的Decart树可以实现这一点，但我不想实现它，而是希望std::set足够好以实现这一点。 - Qwertiystd::nth_element和std::vector。 - D Drmmr