std::is_sorted() algorithm
- od C++20
- od C++17
- od C++11
// (1)
template< class ForwardIt >
constexpr bool is_sorted( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class Compare >
constexpr bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class ForwardIt >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );
// (4)
template< class ExecutionPolicy, class ForwardIt, class Compare >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Compare comp );
// (1)
template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class ForwardIt >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );
// (4)
template< class ExecutionPolicy, class ForwardIt, class Compare >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Compare comp );
// (1)
template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );
Checks if the elements in range [first
; last
) 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_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
true
if the elements in the range are sorted in non-descending order (also 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 (1)
template<class ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last)
{
return std::is_sorted_until(first, last) == last;
}
is_sorted (2)
template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp)
{
return std::is_sorted_until(first, last, comp) == last;
}
Examples
#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
int digits[] = {3, 1, 4, 1, 5};
for (auto i : digits) std::cout << i << ' ';
std::cout << ": is_sorted: " << std::boolalpha
<< std::is_sorted(std::begin(digits), std::end(digits)) << '\n';
std::sort(std::begin(digits), std::end(digits));
for (auto i : digits) std::cout << i << ' ';
std::cout << ": is_sorted: "
<< std::is_sorted(std::begin(digits), std::end(digits)) << '\n';
}
3 1 4 1 5 : is_sorted: false
1 1 3 4 5 : is_sorted: true
Hover to see the original license.