std::is_sorted_until
| Defined in header <algorithm>
|
||
template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );
|
(1) | (since C++11) (constexpr since C++20) |
template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last,
Compare comp );
|
(2) | (since C++11) (constexpr since C++20) |
template< class ExecutionPolicy, class ForwardIt >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last );
|
(3) | (since C++17) |
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 source range [first, last) and finds the largest sorted range beginning at first.
operator<(until C++20)std::less{}(since C++20).comp.policy.true:
|
|
(until C++20) |
|
|
(since C++20) |
Parameters
| first, last | - | the pair of iterators defining the source range |
| 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:
While the signature does not need to have |
| policy | - | the execution policy to use |
| Type requirements | ||
-ForwardIt must meet the requirements of LegacyForwardIterator.
| ||
-Compare must meet the requirements of Compare.
| ||
Return value
The past-the-end iterator of the largest range found.
Complexity
Given N as std::distance(first, last):
operator<(until C++20)std::less{}(since C++20).comp.Exceptions
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Notes
std::is_sorted_until returns last for empty ranges and ranges of length one.
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
#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';
}
}
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
(C++20) |
finds the largest sorted subrange (algorithm function object) |
(C++11) |
checks whether a range is sorted (function template & algorithm function object) |
(C++20) |