为什么std::sort要将元素与自身进行比较

Question

正如标题所述，为什么下面的代码要将一些元素与它们自身进行比较？

#include <iostream>
#include <vector>
#include <algorithm>

class a {
public:
    a(int value): value(value) {}
    ~a() {}

    bool operator<(const a& rhs) const {
        if(this->value == rhs.value)
            std::cout << this << " " << this->value << "\t" 
                << &rhs << " " << rhs.value << std::endl;
        if(this->value < rhs.value)
            return true;
        return false;
    }

    int value;
};

int main(int argc, char* argv[]) {
    std::vector<a> vec;

    for(int i = 0; i < 17; i++)
        vec.push_back(a(i));

    std::sort(vec.begin(), vec.end());
    return 0;
}

我在Windows、Linux和OpenBSD上尝试了以上代码，似乎在Windows上它不会将元素与自身进行比较，但在Linux和OpenBSD上都会。我的猜测是因为使用了不同的库。

在Linux上，我得到类似以下的输出：

0x96be0d0 8     0xbfc2945c 8
0xbfc2945c 8    0x96be0d0 8

- user3358771

---

在我的Linux系统上（GCC 4.8.1），比较谓词从不比较相同地址的项目。 - Fred Foo

你的类没有==运算符，那么sort如何判断不同地址上的元素是否相同呢？ - Barmar

似乎引入了临时变量，因此地址不同。实现似乎没有进行优化。 - Groovy

为什么不呢？这并不代价高昂，但避免做它可能会造成代价。 - Walter

天真地认为，a < b相对于&a == &b ? false : a < b来说是更短的代码。然而每次比较都需要进行额外的&a == &b测试，只是为了避免在少数自比较中使用a < b测试。一般情况下，这不是一个好的权衡。 - Oktalist

Answer 1

如果std::sort实现为快速排序，那么有一种情况是将当前元素与枢轴元素进行比较。我手头没有Sedgewick的算法，但我认为避免这种比较并不能加快算法速度（或者说这种比较对算法的复杂性没有影响）。如果您愿意，我可以查找确切的引用。

- usr1234567

---

std::sort 几乎从不被实现为快速排序（严格来说）。它通常被实现为一种引入排序（intro-sort），它是部分快排、部分堆排、部分插入排序的结合。 - Mooing Duck

避免进行比较不能作为一个全面的陈述是不可能的。考虑当比较函数非常昂贵时，而测试是否将要将一个元素与其本身进行比较非常便宜的情况。那么避免比较确实会加速算法。 - Don Hatch