C++ 条件语句问题导致意外行为

Question

#include "bits/stdc++.h"

using namespace std;

vector<int> findMedian(vector<int> &arr, int n) {
    priority_queue<int> maxheap; // Store smaller elements (left half)
    priority_queue<int, vector<int>, greater<int>> minheap; // Store larger elements (right half)
    vector<int> medians;

    for (int i = 0; i < n; i++) {
        maxheap.push(arr[i]);

        // Ensure smaller elements are in the maxheap 
        if (minheap.size() > 0 && maxheap.top() > minheap.top()) {
            minheap.push(maxheap.top());
            maxheap.pop();
        }

        // Maintain a balance between sizes of the two heaps
        if (minheap.size() > maxheap.size() + 1) {
            maxheap.push(minheap.top());
            minheap.pop();
        } else if (maxheap.size() > minheap.size() + 1) {
            minheap.push(maxheap.top());
            maxheap.pop();
        }

        // Calculate the median based on whether the total count of elements is even or odd
        if ((minheap.size() + maxheap.size()) % 2 == 0) {
            medians.push_back((minheap.top() + maxheap.top()) / 2); 
        } else { // Implied 'else' here since the size difference can't be more than 1
            if (maxheap.size() > minheap.size()) {
                medians.push_back(maxheap.top());
            } else { // Must be minheap.size() > maxheap.size() 
                medians.push_back(minheap.top());
            }
        }
    }

    return medians;
}

但是如果我将这两行代码更改为

if (maxHeap.size() - minHeap.size() > 1)

和

else if (minHeap.size() - maxHeap.size() > 1)

那么代码会给出 SIGSEGV 运行时错误，即使这两行代码在数学上是等效的。

我错过了什么吗？

Answer 1

[...]即使这两行代码在数学上是等价的

他们不是。

std::vector::size

返回

std::vector::size_type

，这是一个无符号类型。无符号整数不能为负数。如果用较小的无符号值减去较大的无符号值，结果不是负数，但会回绕。

0U - 1U

是最大无符号值。

以下代码打印相同的值 3 次：

#include <iostream>
#include <limits>
#include <vector>


int main(){
    std::vector<int> x{1};
    std::vector<int> y{};

    std::cout << y.size()-x.size() << "\n";
    std::cout << std::numeric_limits<std::vector<int>::size_type>::max() << "\n";
    std::cout << 0LU - 1LU;
}

（第三个可能会有所不同，具体取决于

std::vector<int>::size_type

的宽度）

这就是两条线不一样的原因。常见的解决方法是在工作代码中执行的操作，以避免环绕的方式重写表达式：

if (minheap.size() > maxheap.size() + 1) ...

当

+1

使

maxheap.size()

环绕时（即当

maxheap.size()

是

std::vector<int>::size_type

可以表示的最大值时），这仍然可能失败。然而，这种情况比一个容器比另一个容器拥有更多元素的可能性要小得多。

为了完整起见，我提到

std::ssize

返回自 C++20 以来可用的有符号值。