# std::is_sorted_until

From cppreference.com
< cpp‎ | algorithm

Defined in header `<algorithm>` |  |
| (1) |
template< class ForwardIt > ForwardIt is_sorted_until( ForwardIt first, ForwardIt last ); |  | (since C++11) (until C++20)
template< class ForwardIt > constexpr ForwardIt is_sorted_until( ForwardIt first, ForwardIt last ); |  | (since C++20)
template< class ExecutionPolicy, class ForwardIt > ForwardIt is_sorted_until( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last ); | (2) | (since C++17)
| (3) |
template< class ForwardIt, class Compare > ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp ); |  | (since C++11) (until C++20)
template< class ForwardIt, class Compare > constexpr ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp ); |  | (since C++20)
template< class ExecutionPolicy, class ForwardIt, class Compare > ForwardIt is_sorted_until( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare comp ); | (4) | (since C++17)

Examines the range `[`first`,` last`)` and finds the largest range beginning at first in which the elements are sorted in non-descending order.

A sequence is sorted with respect to a comparator comp if for any iterator `it` pointing to the sequence and any non-negative integer `n` such that `it + n` is a valid iterator pointing to an element of the sequence, comp(*(it + n), *it) evaluates to false.

1) Elements are compared using `operator<`.
3) Elements are compared using the given binary comparison function comp.
2,4) Same as (1,3), but executed according to policy. These overloads do not participate in overload resolution unless

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true. | (until C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true. | (since C++20)

### Parameters

first, last | - | the range of elements to examine
policy | - | the execution policy to use. See execution policy for details.
comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1& a, const Type2& b); While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, `Type1&` is not allowed, nor is `Type1` unless for `Type1` a move is equivalent to a copy (since C++11)). The types Type1 and Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to both of them. ​
Type requirements
- `ForwardIt` must meet the requirements of LegacyForwardIterator.

### Return value

The upper bound of the largest range beginning at first in which the elements are sorted in ascending order. That is, the last iterator `it` for which range `[`first`,` it`)` is sorted.

Returns last for empty ranges and ranges of length one.

### Complexity

Linear in the distance between `first` and `last`.

### Exceptions

The overloads with a template parameter named `ExecutionPolicy` report errors as follows:

- If execution of a function invoked as part of the algorithm throws an exception and `ExecutionPolicy` is one of the standard policies, std::terminate is called. For any other `ExecutionPolicy`, the behavior is implementation-defined.
- If the algorithm fails to allocate memory, std::bad_alloc is thrown.

### Possible implementation

See also the implementations in libstdc++ and libc++.

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

### Example

Run this code

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

Possible output:

    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
    ^^^^^^^

### See also

is_sorted (C++11) | checks whether a range is sorted into ascending order (function template)
ranges::is_sorted_until (C++20) | finds the largest sorted subrange (niebloid)

Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/is_sorted_until&oldid=150224"