当 lambda 始终返回 true 时，std::is_sorted 返回 false

Question

请解释一下为什么这段代码会崩溃？

#include <vector>
#include <cassert>
#include <algorithm>

int main() {
    std::vector<int> vt = {1,2,3,4};
    assert(std::is_sorted(vt.begin(), vt.end(), [](const auto& a, const auto& b){ return true;}));
}

https://godbolt.org/

Answer 1

比较函数（lambda 表达式）不正确。它总是返回trueforvt[i] < vt[j]和 for vt[j] < vt[i]。因此，算法的调用具有未定义的行为。

来自 C++ 标准：

为了使 25.4.3 中描述的算法以外的算法正常工作， comp 必须对值进行严格的弱排序。

例如，该算法可以通过以下方式实现

template<class ForwardIterator, class Compare>
bool is_sorted( ForwardIterator first,
    ForwardIterator last,
    Compare comp )
{
    if (first != last)
    {

        for (auto prev = first; ++first != last && !comp( *first, *prev );)
        {
            ++prev;
        }
    }

    return first == last;
}

正如您所看到的，对于排序序列，表达式!comp( *first, *prev )将立即返回 false。