std::sort comparing elements to null

Question

I have the following sorting algorithm, which sorts an std::vector of unique armor_set pointers. By some property of my sorting algorithm, it chokes up and runs into undefined behavior which ends up comparing a valid lhs to a rhs which is a nullptr.

Despite moving the algorithm around multiple times, I've been unable to discern the problem. I feel as though I'm missing some sort of simple rule I should be following regarding how this std::sort algorithm works.

Any help would be appreciated.

std::vector<armor_set*> armor_sets;

//insertion of unique armor sets here

std::sort(armor_sets.begin(), armor_sets.end(), [](armor_set* lhs, armor_set* rhs)
{
    auto lhs_collectible_count = collectible_mgr::get().count(lhs->needed_collectible);
    auto rhs_collectible_count = collectible_mgr::get().count(rhs->needed_collectible);

    if(lhs_collectible_count > 0 && rhs_collectible_count == 0)
    {
        return true;
    }
    else if(lhs_collectible_count == rhs_collectible_count)
    {
        return lhs->sort_index > rhs->sort_index;
    }
    else
    {
        auto lhs_collectibles_needed_count = lhs_collectible_count - lhs->collectibles_needed;
        auto rhs_collectibles_needed_count = rhs_collectible_count - rhs->collectibles_needed;

        return lhs_collectibles_needed_count > rhs_collectibles_needed_count;
    }
});

Answer 1

The comparison function must follow a strict-weak-ordering.

For example, If I am the sort function, I give you two armor_set pointers, ask you "which one comes first?" and you return a true/false value denoting which value comes first. I then give you the same two armor_set pointers but this time, change the order of items. I ask you the same question "which comes first?". You then return the same true/false value. Guess what -- you lose.

That in a nutshell is a violation of the strict weak ordering. There is no way a < b, and at the same time b < a. Looking at your somewhat complex comparison function, my guess is that you're violating this rule.

If you're using Visual Studio, the debug runtime does this exact check for ordering violations like this. The comparison function is called twice, the first time with A,B order, and the second time with B,A order. The return values for each call are compared, and an assert() will occur if there is a violation.

Answer 2

The Compare operation (lambada) is the problem. The operator in sort should make sure the defined order is strict weak order. i.e

1)For all x, it is not the case that x < x (irreflexivity).
2)For all x, y, if x < y then it is not the case that y < x (asymmetry).
3)For all x, y, and z, if x < y and y < z then x < z (transitivity).
4)For all x, y, and z, if x is incomparable with y, and y is incomparable with z, 
    then x is incomparable with z (transitivity of incomparability).

You function seems miss it. For example:

armor_set* lhs{
 lhs->needed_collectible=0;
 ....
}

armor_set* rhs{
 lhs->needed_collectible=1;
 ....
}

When you call compare(lhr, rhs), it may return true or false depends on other value. While you call compare(rhs, lhs), note the order is different, it will always return true. Both compare(a,b) and compare(b,a) return true is not allowed, which violates the property of strict weak order.

Answer 3

The specific failure is a missing

if(lhs_collectible_count == 0 && rhs_collectible_count > 0)
{
    return false ;
}

which should be the second or third test.