c++ - 正确实现 std::sort

Question

我正在尝试衡量各种搜索算法使用的比较次数。我的代码相当简单——给定一个对象 vector ，然后调用std::sort(students.begin(), students.end());

我在我的 Student 类中实现了一个比较运算符，如下所示:

bool Student::operator < (Student s) const {
    compareCount++;
    return number < s.getNumber();
}

其中 compareCount 是一个静态变量。然而，我的结果令人费解。

为什么 std::sort 需要对一个双元素列表进行两次比较？这让我觉得我的代码的某些部分不正确。

Answer 1

“为什么 std::sort 需要对一个双元素列表进行两次比较？” - 这是在“调试”模式下完成的吗？我用 Visual Studio 2005 对此进行了测试——它对小数组使用插入排序(大小 < 32，否则它使用快速排序或堆排序)。在“发布”模式下，它进行一次比较。在 Debug模式下，它检查调用者提供的比较例程以确保它是 < 与 <= ，因此进行了两次调用:

{   // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
if (!_Pred(_Left, _Right))
    return (false);
else if (_Pred(_Right, _Left))
    _DEBUG_ERROR2("invalid operator<", _Where, _Line);
return (true);
}