c++ - 为什么 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

Answer 1

如果 std::sort 是作为快速排序实现的，那么在这种情况下，您将当前元素与枢轴元素进行比较。我手边没有我的 Sedgewick 算法，但我认为避免这种比较不会加快算法速度(或者这种比较不会损害算法的复杂性)。如果您愿意，我可以查看确切的报价。