std::is_sorted() 算法

自 C++20 起

// (1)
template< class ForwardIt >
constexpr bool is_sorted( ForwardIt first, ForwardIt last );

// (2)
template< class ForwardIt, class Compare >
constexpr bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class ForwardIt >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

// (4)
template< class ExecutionPolicy, class ForwardIt, class Compare >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                Compare comp );

自 C++17 起

// (1)
template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );

// (2)
template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class ForwardIt >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

// (4)
template< class ExecutionPolicy, class ForwardIt, class Compare >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                Compare comp );

自 C++11 起

// (1)
template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );

// (2)
template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

检查范围 [first; last) 中的元素是否按非降序排序。

如果对于指向序列的任何迭代器 it 以及任何非负整数 n（使得 it + n 是指向序列元素的有效迭代器），comp(*(it + n), *it) 求值为 false，则序列相对于比较器 comp 是已排序的。

• (1) 元素使用 operator< 进行比较。

• (2) 元素使用给定的二元比较函数 comp 进行比较。

• (3 - 4) 与 (1 - 2) 相同，但根据 policy 执行。

  重载决议

  这些重载只有在 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>  (直到 C++20) std::is_execution_policy_v<std::is_sorted_cvref_t<ExecutionPolicy>>  (自 C++20 起) 为 true 时才参与重载决议。

参数

first last	要检查的元素范围。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
p	比较函数对象（即满足 Compare 要求的对象），如果第一个参数“小于”第二个参数，则返回 true。 比较函数的签名应等效于以下内容 bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受所有类型（可能是 const）Type 和 Type2 的值，无论值类别如何（因此不允许 Type1&，也不允许 Type1，除非对于 Type1 移动等同于复制 (自 C++11 起)） `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

ForwardIt

LegacyForwardIterator

返回值

如果范围中的元素按非降序排序（也适用于空范围和长度为一的范围），则为 true。

复杂度

与 first 和 last 之间的距离成线性关系。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果在算法执行过程中调用的函数抛出异常且 ExecutionPolicy 是标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

可能的实现

is_sorted (1)

template<class ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last)
{
    return std::is_sorted_until(first, last) == last;
}

is_sorted (2)

template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp)
{
    return std::is_sorted_until(first, last, comp) == last;
}

示例

Main.cpp

#include <algorithm>
#include <iostream>
#include <iterator>

int main()
{
    int digits[] = {3, 1, 4, 1, 5};

    for (auto i : digits) std::cout << i << ' ';
    std::cout << ": is_sorted: " << std::boolalpha
              << std::is_sorted(std::begin(digits), std::end(digits)) << '\n';

    std::sort(std::begin(digits), std::end(digits));

    for (auto i : digits) std::cout << i << ' ';
    std::cout << ": is_sorted: "
              << std::is_sorted(std::begin(digits), std::end(digits)) << '\n';
}

输出

3 1 4 1 5 : is_sorted: false
1 1 3 4 5 : is_sorted: true