std::is_sorted 的奇怪行为

Question

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

给定一个比较器 (c) 和 std::strings 的未排序向量 (v)。我使用 std::sort(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();} );

你贴的原谓词returns字符串长度差，是整型，被std::sort调用时可以转成bool，结果是true 对于不同于 0 的所有内容，否则为 false。因此，每 non-equal 个字符串长度都会导致谓词被评估为 true，并且由于谓词始终为 "true"，因此具有不同字符串长度的序列元素将被无限交换。这会导致未定义的行为。

这里的术语是谓词必须实现一个 "strict weak ordering"，它被记录在例如在 cppreference 上。感谢@FrançoisAndrieux 和@Peter 在这方面的评论。

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

Answer 2

根据C++标准（28.7排序及相关操作）

2 Compare is a function object type (23.14). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool (Clause 7), yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

这个 lambda 表达式

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

总是returns（上下文转换值）true如果两个字符串的长度不相等。

所以对于这个向量

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

lambda-expression returns false 相邻元素 "yy" 和 "yy" 在位置 2 和 3.

例如，如果您将在位置 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 ); 
                 } );

std::is_sorted 的奇怪行为

Weird behavior of std::is_sorted

c++

sorting

algorithm

assert

compare