c++ - 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.