std::is_sorted_until
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, |
(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
.
Contents |
[edit] Parameters
first, last | - | the range of elements to examine | |||||||||
comp | - | comparison function which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. |
|||||||||
Type requirements | |||||||||||
-
ForwardIt must meet the requirements of ForwardIterator .
|
[edit] 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.
[edit] Complexity
linear in the distance between first
and last
[edit] 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) { if (first != last) { ForwardIt next = first; while (++next != last) { if (comp(*next, *first)) return next; first = next; } } return last; |
[edit] 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::random_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
[edit] See also
(C++11)
|
checks whether a range is sorted into ascending order (function template) |