std:: is_sorted_until

範囲 [ 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 << " 個の先頭ソート済み要素\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 個の先頭ソート済み要素
^^^^^^^

関連項目