c++ - Priority_queue 大小的意外行为

Question

我正在为这个问题编写代码。当我遇到问题时，整数流的中位数。请注意，此问题不是算法问题，而是 priority_queue 大小的模糊行为。

#include <bits/stdc++.h>
using namespace std;
priority_queue<double> small;
priority_queue<double, vector<double>, greater<double> > large;
void rebalance()
{
    cout << "Initial size\n";
    cout << "small " << small.size() << " large " << large.size() << endl;
    if (small.size() - large.size()>1)
    {
        large.push(small.top());
        small.pop();
    }
    else if (large.size() - small.size()>1)
    {
        cout << "Unexpectedly goes here\n";
        cout << "garbage size difference " << large.size() - small.size() << endl;
        small.push(large.top());
        large.pop();
    }
}
void addNum(int num) {
    if (small.size() == 0 || num<small.top())
    {
        small.push(num);
    }
    else
    {
        large.push(num);
    }
    rebalance();
}

double findMedian() {
    if (small.size() == large.size())
    {
        double ans = (small.top() + large.top()) / 2.0;
        return ans;
    }
    else if (small.size()>large.size())
    {
        return (double)small.top();
    }
    else
    {
        return (double)large.top();
    }
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    int num = 5;
    addNum(num);
    cout << findMedian() << endl;
    return 0;
}

这段代码的输出是

   Initial size
   small 1 large 0
   Unexpectedly goes here
   garbage size difference 18446744073709551615
   fish: “./a.out” terminated by signal SIGSEGV (Address boundary error)

在rebalance 函数中，small 的初始大小为1，large 为0，这表明循环不应进入 if 条件或 else if 条件，而是循环进入 else if 条件，其大小为垃圾值。为什么会发生这种情况？此外，我尝试将小尺寸和大尺寸保存在一个整数变量中，然后在条件中比较它们，这导致代码被接受。因此算法处理正确性。

是什么导致了这个垃圾值？

Answer 1

在

else if(large.size()-small.size()>1)

size() 返回一个无符号数。一个无符号数永远不会是负数，所以如果它是一个负数，它会环绕到它可能是的最大数，然后从那里倒退。由于 large 的大小为 0 而 small 的大小为 1 那么 0 - 1 给你 18446744073709551615。我相信你正在尝试做的事情应该表达为

if(small.size() < large.size())
{
    small.push(large.top());
    large.pop():
} 
else if(large.size() < small.size())
{
    large.push(small.top());
    small.pop();
}