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 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); The signature does not need to have const &, but the function object 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) { using namespace std::placeholders; ForwardIt it = std::adjacent_find(first, last, std::bind(comp, _2, _1)); return it == last ? last : std::next(it); } |
[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) |
(parallelism TS)
|
parallelized version of std::is_sorted_until (function template) |