C++ std::sort 自定义比较器在比较器 returns true 时无限期运行

Question

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

当运行这段代码时，它不会停止，并永远运行：

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 的数量时，它也能正常工作。（它适用于 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() 函数中的一些重要概念？

Answer 1

这个比较器：

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

违反了std::sort比较器必须建立strict-weak-ordering的要求。请注意，此函数 returns true 与参数的顺序无关，这意味着 2 个元素都可以小于另一个，这实际上没有意义。违反 std::sort 的这一要求会调用未定义的行为（这足以解释您看到的不同 vector 大小的不同行为）。

另一方面，这个比较器：

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

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

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

C++ std::sort 自定义比较器在比较器 returns true 时无限期运行

C++ std::sort custom comparator runs indefinitely when the comparator returns true

c++

sorting

stl

strict-weak-ordering