0

因此，在使用自定义比较器对向量进行排序时，我在边缘情况下遇到了这种非常奇怪的行为。

运行此代码时，它不会停止，而是永远运行：

int main() {
    auto comp = [](int lhs, int rhs) {
        return true;
    };
    
    vector<int> vec{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    sort(vec.begin(), vec.end(), comp);
    
    for (int num : vec)
        cout << num;
    
    return 0;
}

但是，当我将 更改为true时false，它可以完美运行。

auto comp = [](int lhs, int rhs) {
    return false;
};

更奇怪的是，当我减少0要排序的 's 的数量时，它也可以完美地工作。（它适用于 16 或更少0，当我再添加一个0使其成为 17 时，程序不会再次停止。（如果长度超过 16，g++ 会切换到另一种排序算法吗？）

vector<int> vec{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

为什么会这样？我是否遗漏了 C++sort()函数中的一些重要概念？

4

1 回答 1

3

这个比较器：

auto comp = [](int lhs, int rhs) {
   return true;
};

违反了std::sort比较器必须建立严格弱排序的要求。请注意，true无论参数的顺序如何，此函数都会返回，这意味着两个元素都可以小于另一个，这实际上没有意义。违反此要求会std::sort调用未定义的行为（这足以解释您在不同vector尺寸下看到的不同行为）。

另一方面，这个比较器：

auto comp = [](int lhs, int rhs) {
    return false;
};

很好。它基本上说没有元素比任何其他元素都少（即它们都是等价的）。这满足strict-weak-ordering，因此std::sort可以正常工作。

当然，std::sort不会对第二个比较器做任何有用的事情，因为所有元素都已经“排序”了。不过，这可能会重新排序元素；但如果您使用std::stable_sort，则保证原始范围不变。

于 2020-09-25T11:28:36.920 回答