std::is_sorted_until() algorithm
- od C++20
- od C++17
- od C++11
// (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 );
// (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 );
// (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 );
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<
. -
(2) Elements are compared using the given binary comparison function
comp
. -
(3 - 4 ) Same as (1 - 2), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(do C++20)std::is_execution_policy_v<std::is_sorted_until_cvref_t<ExecutionPolicy>>
(od C++20) istrue
.
Parameters
first last | The range of elements to examine. |
policy | The execution policy to use. See execution policy for details. |
p | Comparison function object (i.e. an object that satisfies the requirements of Compare),
which returns The signature of the comparison function should be equivalent to the following:
|
Type requirements
ForwardIt | 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 otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
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;
}
Examples
#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
^^^^^^^
Hover to see the original license.