CODEWITHSUNDEEP
c++sortingstlvectorstl-algorithm
miloszmaki
miloszmaki

Reputation: 1645

std::sort fails on std:vector of pointers

The following code crashes while sorting the vector.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

struct Foo
{
    int x;
    // int y;
    Foo() : x(0) {}
};

struct Cmp
{
    bool operator() (Foo* p1, Foo *p2) const
    {
        if (p1->x != p2->x) return p1->x < p2->x;
        // if (p1->y != p2->y) return p1->y < p2->y;
        return true;
    }
};

int main()
{
    vector<Foo*> v;
    for (int i=0; i<17; i++) // weird thing, doesn't crash if
                             // I put a number less than 17 !!!
    {
        Foo *ptr = new Foo();
        if (ptr) v.push_back(ptr);
    }
    sort(v.begin(), v.end(), Cmp());

    return 0;
}

Why is this so?

Upvotes: 5

Views: 3230

Answers (1)

Nicol Bolas
Nicol Bolas

Reputation: 473537

bool operator() (Foo* p1, Foo *p2) const
{
    if (p1->x != p2->x) return p1->x < p2->x;
    return true;
}

std::sort requires a sort function that creates a strict-weak ordering. This does not. This is <=, which is not a strict-weak ordering. If lhs and rhs are equial then comp(lhs, rhs) and comp(rhs, lhs) must both return false.

Your function does not. Thus, you get undefined behavior.

Upvotes: 23

Related Questions