std::is_sorted的怪异行为

Question

我正在c++中学习断言，我偶然发现了std::is_sorted的奇怪行为。

给定比较器(C)和未排序向量(V)的std：：字符串。我使用std：：排序(v.begin()，v.end()，比较器)。然后用相同的参数调用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调用时可以转换为std::sort，并且对于与0、false不同的所有东西都会产生true。因此，每个不相等的字符串长度都会导致谓词被求值为true，而具有不同字符串长度的序列元素将由于谓词始终为"true“而被无限交换。这将导致未定义的行为。

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

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

Answer 2

按照C++标准(28.7排序及相关操作)

2比较是函数对象类型(23.14)。应用于类型比较对象的函数调用操作的返回值，当上下文转换为bool时(第7条)，如果调用的第一个参数小于第二个参数，则为true，否则为false。假定排序关系的算法始终使用比较法。假设comp不会通过取消引用的迭代器应用任何非常数函数。

这个lambda表达式

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

如果两个字符串的长度不等，则始终返回(上下文转换的值) true。

所以对于这个向量

std::vector<std::string> v {"y" , "yyyy" , "yy" ,
                             "yy" , "yyyyyyy" , "yyy"};

lambda表达式在位置false和3处返回相邻元素"yy"和"yy"的"yy"。

例如，如果您将中间值放置在位置2和3之间，例如

std::vector<std::string> v {"y" , "yyyy" , "yy" , "y",
                             "yy" , "yyyyyyy" , "yyy"};

然后第一个断言

assert(false == std::is_sorted(v.begin() , v.end(),comparator));

失败了。

因此，需要正确地定义比较函数。例如

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

此外，lambda表达式的参数应该是常量引用。

考虑到，如果编译器支持C++ 17，那么还可以通过以下方式重写lambda表达式

auto comparator( []( const std::string &a , const std::string &b ) 
                 {
                     return std::size( a ) < std::size( b ); 
                 } );