Why does std::sort compare the element to itself

Question

As the subject says, why does the below code compare some of the elements to themselves?

#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;
}

I tried the above code on Windows, Linux and OpenBSD, it seems on Windows it doesn't compare the element to itself, but both on Linux and OpenBSD it does. My guess is that it's because of different libraries being used.

On Linux I get output similar to this:

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

Answer 1

If std::sort is implemented as Quick sort, there is the case, that you compare the current element to the pivot element. I don't have my Sedgewick Algorithms at hand, but I think avoiding this comparison does not speed the algorithm up (or the comparison does no harm to the algorithms complexity). I can look the exact quote up, if you like.