std::is_sorted
Объявление
<tbody> </tbody>| Определено в заголовочном файле <algorithm>
|
||
template< class ForwardIt > bool is_sorted( ForwardIt first, ForwardIt last ); |
(1) | (начиная с C++11) (constexpr начиная с C++20) |
template< class ExecutionPolicy, class ForwardIt > bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last ); |
(2) | (начиная с C++17) |
template< class ForwardIt, class Compare > bool is_sorted( ForwardIt first, ForwardIt last, Compare comp ); |
(3) | (начиная с C++11) (constexpr начиная с C++20) |
template< class ExecutionPolicy, class ForwardIt, class Compare > bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare comp ); |
(4) | (начиная с C++17) |
Описание
Проверяет, отсортированы ли элементы диапазона [first, last) в неубывающем порядке.
comp.policy.|
|
(до C++20) |
|
|
(начиная с C++20) |
Параметры
[first, last)
|
— | два итератора задающих диапазон элементов для проверки |
| policy | — | используемая политика выполнения. Подробнее смотрите политика выполнения. |
| comp | — | функциональный объект сравнения (то есть объект, который соответствует требованиям Compare), который возвращает true, если первый аргумент меньше чем (т.е. упорядочен до) второй. Сигнатура функции сравнения должна быть эквивалентна следующему:
Хотя сигнатура не обязательно должна иметь |
| Требования к типам | ||
-ForwardIt должен соответствовать требованиям LegacyForwardIterator.
| ||
-Compare должен соответствовать требованиям Compare.
| ||
Возвращаемое значение
true если элементы диапазона отсортированы в неубывающем порядке,
false в противном случае.
Предусловия
| Этот раздел не завершён |
Постусловия
(нет)
Исключения
Перегрузки с параметром шаблона по имени ExecutionPolicy сообщают об ошибках следующим образом:
- Если выполнение функции, вызванной как часть алгоритма, вызывает исключение и
ExecutionPolicyявляется одной из стандартных политик, вызывается std::terminate. Для любой другойExecutionPolicyповедение определяется реализацией. - Если алгоритму не удаётся выделить память, генерируется std::bad_alloc.
Сложность
Пусть N это std::distance(first, last) тогда:
O(N) сравнений.
Заметки
std::is_sorted Возвращает true для диапазона длины 0 и\или 1 не выполняя сравнений значений элементов диапазона.
Возможная реализация
См. также реализации в libstdc++ и libc++.
| is_sorted (1) |
|---|
template<class ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last)
{
return std::is_sorted_until(first, last) == last;
}
|
| is_sorted (3) |
template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp)
{
return std::is_sorted_until(first, last, comp) == last;
}
|
Пример
#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> v;
assert(std::is_sorted(v.cbegin(), v.cend()) && "an empty range is always sorted");
v.push_back(42);
assert(std::is_sorted(v.cbegin(), v.cend()) && "a range of size 1 is always sorted");
int data[] = {3, 1, 4, 1, 5};
assert(not std::is_sorted(std::begin(data), std::end(data)));
std::sort(std::begin(data), std::end(data));
assert(std::is_sorted(std::begin(data), std::end(data)));
assert(not std::is_sorted(std::begin(data), std::end(data), std::greater<>{}));
}
См. также
(C++11) |
находит наиболее длинный отсортированный префиксный поддиапазон (шаблон функции) |
(C++20) |
проверяет, отсортирован ли диапазон по возрастанию (ниблоид) |