std::sort是否总是比较相等的值？

Question

我正在Leetcode上解决以下问题: https://leetcode.com/problems/contains-duplicate/ 给定一个整数数组nums，如果数组中有重复的数值，则返回true；否则每个元素都不同，则返回false。

我想出的解决方案是:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        try {
            std::sort(nums.begin(), nums.end(), [](int a, int b) {
                if (a == b) {
                    throw std::runtime_error("found duplicate");
                }
                return a < b;
            });
        } catch (const std::runtime_error& e) {
            return true;
        }
        
        return false;
    }
};

这段代码已被leetcode接受，但我仍不确定它是否总是有效。思路是开始对nums数组进行排序，并在比较器内发现重复值时立即中断。排序算法可以按多种方式比较元素。 我预期相等的元素将始终进行比较，但我不确定。 std::sort是否总是比较相等的值，有时会跳过比较它们，因此找不到重复值？

- ks1322

---

你想象一下，std :: sort 如何在不比较值的情况下知道它们相等？ - 273K

排序如何在不至少比较一次的情况下确定以哪种顺序放置这些数字？通常，每两个相邻的数字至少会比较一次。 - ALX23z

也有可能出现误报（False positives）。 - GSerg

这是一个完美的例子，说明编程谜题网站（如leetcode）为何是具有反生产力的。在std::sort比较器中抛出异常？这样的行为在任何工作面试中都不会留下好印象。 - Sam Varshavchik

从比较函数中抛出异常是一种肮脏的技巧，但我真的喜欢这种超越常规思维的方式！点赞！ - Ulrich Eckhardt

Answer 1

std::sort是否总是比较相等的值，或者有时它会跳过比较，因此可能找不到重复的值？

是的，如果存在重复元素，则某些相等值元素将始终进行比较。

让我们假设相反的情况：要排序的初始元素数组{e}包含具有相同值的元素子集，并且有效的排序算法不会为子集中的任何一对元素调用比较运算符<。

然后，我们构造了一个相同大小的元组数组{e,k}，其中第一个元组值来自初始数组，第二个元组值k是任意选择的，并使用元组的词典比较运算符应用相同的排序算法。排序后的元组顺序只有在具有相同值的元素的情况下才可能与排序后的元素{e}的顺序不同，在元组数组的情况下，这将取决于第二个元组值k。

由于我们假设排序算法不会比较任何一对相同值元素，因此它不会比较具有相同第一个元组值的元组，因此算法将无法正确排序它们。这与我们的假设相矛盾，证明了在排序过程中某些相等值元素（如果存在于数组中）将始终进行比较。

- Fedor