std::is_sorted_until

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

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

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

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

检查范围 [first, last) 并找到起始于 first 的最大范围，其中元素按非降序排序。

参数

返回值

起始于 first 的最大有序范围的上界，该范围内的元素按升序排列。即满足范围 [ first , it ) 为有序的最后一个迭代器 it 。

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

复杂度

给定 \(\scriptsize N\) N 为 std:: distance ( first, last ) ：

异常

带有名为 ExecutionPolicy 模板参数的重载按以下方式报告错误：

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

可能的实现

另请参阅 libstdc++ 和 libc++ 中的实现。

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

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;
}

示例

#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 (const 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 个初始有序元素
^
4 5 9 3 1 1 : 3 个初始有序元素
^^^^^
9 3 1 4 5 1 : 1 个初始有序元素
^
1 3 5 4 1 9 : 3 个初始有序元素
^^^^^
5 9 1 1 3 4 : 2 个初始有序元素
^^^
4 9 1 5 1 3 : 2 个初始有序元素
^^^
1 1 4 9 5 3 : 4 个初始有序元素
^^^^^^^

另见