Defined in header <algorithm> | ||
---|---|---|
template< class ForwardIt > ForwardIt is_sorted_until( ForwardIt first, ForwardIt last ); | (1) | (since C++11) |
template< class ForwardIt, class Compare > ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp ); | (2) | (since C++11) |
Examines the range [first, last)
and finds the largest range beginning at first
in which the elements are sorted in ascending order. The first version of the function uses operator<
to compare the elements, the second uses the given comparison function comp
.
Parameters
first, last | - | the range of elements to examine |
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:
The signature does not need to have |
Type requirements | ||
- ForwardIt must meet the requirements of ForwardIterator . |
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.
Complexity
linear in the distance between first
and last
.
Possible implementation
First version |
---|
template<class ForwardIt> ForwardIt is_sorted_until(ForwardIt first, ForwardIt last) { if (first != last) { ForwardIt next = first; while (++next != last) { if (*next < *first) return next; first = next; } } return last; } |
Second version |
template <class ForwardIt, class Compare> ForwardIt is_sorted_until(ForwardIt first, ForwardIt last, Compare comp) { using namespace std::placeholders; ForwardIt it = std::adjacent_find(first, last, std::bind(comp, _2, _1)); return it == last ? last : std::next(it); } |
Example
#include <iostream> #include <algorithm> #include <iterator> #include <random> 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; int sorted_size = 0; do { std::shuffle(nums, nums + N, g); int *sorted_end = std::is_sorted_until(nums, nums + N); sorted_size = std::distance(nums, sorted_end); for (auto i : nums) std::cout << i << ' '; std::cout << " : " << sorted_size << " initial sorted elements\n"; } while (sorted_size < min_sorted_size); }
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++11) | checks whether a range is sorted into ascending order (function template) |
std::experimental::parallel::is_sorted_until
(parallelism TS) | parallelized version of std::is_sorted_until (function template) |
Please login to continue.