时间戳

首页 > 解决方案 > std::is_sorted 的奇怪行为

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

问题描述

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

给定一个比较器（c）和未排序的 std::strings 向量（v）。我使用 std::sort(v.begin(),v.end(),comarator)。然后使用相同的参数调用 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));
}

标签： c++algorithmsortingcompareassert

解决方案

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

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

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

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

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

推荐阅读