为什么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算法，但我认为避免这种比较并不会加快算法速度（或者比较不会损害算法的复杂性）。如果您愿意，我可以查看确切的报价。