std :: is_sorted的怪异行为

Question

我正在学习c ++中的断言，并且遇到了std :: is_sorted的怪异行为。

给定一个比较器（c）和std :: strings的未排序向量（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();} );

您发布的原始谓词返回字符串长度差，该长度是整数类型，可以bool由调用时转换为std::sort，并且导致的结果true不同于0，false否则。因此，每个不相等的字符串长度都会导致该谓词被评估为true，并且由于谓词一直都为“ true”，因此具有不同字符串长度的序列元素将被无限交换。这导致未定义的行为。

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

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