std :: sort比较元素为null [英] std::sort comparing elements to null

问题描述

我有以下排序算法，该算法对唯一的 armor_set 指针的 std :: vector 进行排序。由于我的排序算法的某些特性，它阻塞并运行不确定的行为，最终将有效的 lhs 与 rhs 这是 nullptr 。

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.

尽管多次移动算法，但我一直无法辨别问题。我觉得好像缺少某种简单的规则，关于这种 std :: sort 算法的工作方式，我应该遵循。

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.

任何帮助将不胜感激。

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

推荐答案

比较函数必须遵循严格弱顺序。

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

例如，如果我是sort函数，我给你两个armour_set指针，问你哪个先出现？然后您返回一个真/假值，表示哪个值在前。然后，我给您同样的两个armour_set指针，但是这次更改项目的顺序。我问你同样的问题哪个先到？。然后，您返回相同的true / false值。猜猜-您输了。

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.

总而言之，这违反了严格的弱排序。 a< b ，同时 b<一个。看一下您比较复杂的比较功能，我想您是在违反此规则。

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.

如果您使用的是Visual Studio，则调试运行时将对此类排序违规进行准确的检查。比较函数被调用两次，第一次以A，B顺序，第二次以B，A顺序。比较每个调用的返回值，如果发生冲突，则将产生assert（）。

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.

这篇关于std :: sort比较元素为null的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！