std::is_sorted_until() 算法

自 C++20 起

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

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

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

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

自 C++17 起

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

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

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

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

自 C++11 起

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

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

检查范围 [first; last)，并查找从 first 开始的最大范围，其中元素以非降序排列。

如果对于指向序列的任何迭代器 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_until_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

返回值

从 first 开始的最大范围的上限，其中元素按升序排序。也就是说，它是最后一个迭代器 it，其范围 [first; it) 已排序。

对于空范围和长度为一的范围返回 last。

复杂度

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

异常

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

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

可能的实现

is_sorted_until (1)

template<class ForwardIt>
constexpr //< since C++20
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last)
{
    return std::is_sorted_until(first, last, std::less<>());
}

is_sorted_until (2)

template<class ForwardIt, class Compare>
constexpr //< since C++20
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last, Compare comp)
{
    if (first != last)
    {
        ForwardIt next = first;
        while (++next != last)
        {
            if (comp(*next, *first))
                return next;
            first = next;
        }
    }
    return last;
}

示例

Main.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <random>
#include <string>

int main()
{
    std::random_device rd;
    std::mt19937 g(rd());
    const int N = 6;
    int nums[N] = {3, 1, 4, 1, 5, 9};

    const int min_sorted_size = 4;

    for (int sorted_size = 0; sorted_size < min_sorted_size;)
    {
        std::shuffle(nums, nums + N, g);
        int *const sorted_end = std::is_sorted_until(nums, nums + N);
        sorted_size = std::distance(nums, sorted_end);
        assert(sorted_size >= 1);

        for (auto i : nums)
            std::cout << i << ' ';
        std::cout << " : " << sorted_size << " initial sorted elements\n"
                  << std::string(sorted_size * 2 - 1, '^') << '\n';
    }
}

可能输出

4 1 9 5 1 3  : 1 initial sorted elements
^
4 5 9 3 1 1  : 3 initial sorted elements
^^^^^
9 3 1 4 5 1  : 1 initial sorted elements
^
1 3 5 4 1 9  : 3 initial sorted elements
^^^^^
5 9 1 1 3 4  : 2 initial sorted elements
^^^
4 9 1 5 1 3  : 2 initial sorted elements
^^^
1 1 4 9 5 3  : 4 initial sorted elements
^^^^^^^