c++ - std::is_sorted 的奇怪行为

Question

我正在学习 C++ 中的断言，我遇到了 std::is_sorted 的奇怪行为。

给定一个比较器 (c) 和未排序的 std::strings vector (v)。我使用 std::sort(v.begin(),v.end(),comparator)。然后用相同的参数调用 std::is_sorted。结果是假的，为什么会这样？

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <cassert>
int main(){
    auto comparator([](std::string a , std::string b) {return a.length() - b.length();} );
    std::vector<std::string> v {"y" , "yyyy" , "yy" ,
                                 "yy" , "yyyyyyy" , "yyy"};
    assert(false == std::is_sorted(v.begin() , v.end(),comparator));
    std::sort(v.begin(), v.end(),comparator);
    assert(true == std::is_sorted(v.begin() , v.end(),comparator));
}

Answer 1

您的谓词无法正常工作。如果你打算按字符串长度排序，你需要

auto comparator([](std::string a , std::string b) {return a.length() < b.length();} );

你贴出的原始谓词返回字符串长度差，是整数类型，在被std::sort调用时可以转化为bool，并做result对于不同于 0 的所有内容，在 true 中，否则为 false。因此，每个不相等的字符串长度都会导致谓词被评估为 true，并且由于谓词始终为“true”，具有不同字符串长度的序列元素将被无限交换。这会导致未定义的行为。

这里的术语是谓词必须实现“严格的弱排序”，例如记录在案在 cppreference .感谢@FrançoisAndrieux 和@Peter 在这方面的评论。

还可以考虑通过 const std::string& 或 std::string_view 传递参数以避免不必要的复制。