CODEWITHSUNDEEP
c++sortingcomparison
user3358771
user3358771

Reputation: 307

Why does std::sort compare the element to itself

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

Upvotes: 9

Views: 885

Answers (1)

usr1234567
usr1234567

Reputation: 23294

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.

Upvotes: 2

Related Questions