std::sort 将元素与 null 进行比较

Question

我有以下排序算法，它可以对唯一的armor_set指针的std::vector进行排序。由于某些排序算法的属性，它会出现问题并导致未定义的行为，最终将一个有效的lhs与一个nullptr的rhs进行比较。

尽管我多次移动算法，但我无法确定问题所在。我感觉我缺少应该遵循的某种简单规则，关于这个std::sort算法的工作方式。

任何帮助都将不胜感激。

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

- Colin Basnett

---

@KarlKnechtel 是的，我已经进行了双重和三重检查。 - Colin Basnett

你能展示一下 armor_sets 的定义吗？ - David

您应该始终检查指针参数是否为空指针。 - Lee Brindley

@Fendorio 理论上是的，但在这里不需要，因为代码的其他部分保证向量中没有 nullptr。 - Colin Basnett

比较函数必须遵循严格弱序。例如，如果我是排序函数，我会给你两个armor_set指针，然后你会返回一个true/false值。然后我会再次给你这两个armor_set指针，但是顺序相反，你仍需返回相同的true/false值。如果不行——你就输了。简而言之，这就是违反严格弱序的情况。a不可能小于b同时b也小于a。从你有点复杂的比较函数来看，我的猜测是你正在违反这条规则。 - PaulMcKenzie

Answer 1

比较函数必须符合严格弱序。例如，如果我是排序函数，给你两个armor_set指针，问你“哪一个先出现？”，你返回一个true/false值表示哪一个值先出现。然后我再给你同样的两个armor_set指针，但这次交换了它们的顺序。我会问你同样的问题“哪一个先出现？”你做出相同的true/false值的回答。你知道吗——你输了。

简而言之，这就是违反了严格弱序的规则。没有任何可能使得a小于b，同时b又小于a。从您的相对复杂的比较函数来看，我的猜测是您正在违反此规则。

如果您使用的是Visual Studio，则调试运行时会检查是否存在类似此类的排序违规。比较函数被调用两次，第一次按A、B的顺序，第二次按B、A的顺序。比较每个调用的返回值，如果存在违规，则会出现assert()。

- PaulMcKenzie

---

当a=b时，a<b和a>b成立。 - notbad

是的，忘了提到。== 检查似乎会让很多不熟悉 std::sort 工作方式的程序员感到困惑。 - PaulMcKenzie

@notbad 当a==b时，既不满足a<b也不满足a>b。 - Casey

我认为这里的特定问题在于 a<b 意味着 !(b<a)。这是有问题的，因为没有匹配的 return false 来对应 return true 的情况。 - MSalters

@Casey 是的，我犯了一个错误。当a=b时，!(a<b)和!(b<a)成立。 - notbad

Answer 2

比较操作（lambda表达式）是问题所在。在sort中的运算符应该确保定义的顺序是严格弱序。即

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).

您的函数似乎缺失了某些内容，例如：

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

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

当您调用compare(lhr, rhs)时，它可能会根据其他值返回true或false。当您调用compare(rhs, lhs)时，请注意顺序不同，它将始终返回true。不允许同时返回true的compare(a,b)和compare(b,a)，这违反了严格弱序的属性。

- notbad

---

当前算法违反了哪个规则？ - Colin Basnett

@cmbasnett 比较函数中参数的顺序不应影响比较结果，除非它们相等。 - notbad

std::sort不需要一个完全有序，它需要一个严格弱序。 - Casey

Answer 3

具体的失败原因是缺少一个。

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

应该是第二或第三个测试。

- MSalters