std::is_sorted
Содержание |
[править] Объявление
| Определено в заголовочном файле <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, |
(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, |
(4) | (начиная с C++17) |
[править] Описание
Проверяет, отсортированы ли элементы диапазона [first, last) в неубывающем порядке.
|
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> не равно true. |
(до C++20) |
|
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> не равно true. |
(начиная с C++20) |
[править] Параметры
[first, last)
|
— | два итератора задающих диапазон элементов для проверки |
| policy | — | используемая политика выполнения. Подробнее смотрите политика выполнения. |
| comp | — | функциональный объект сравнения (то есть объект, который соответствует требованиям Compare), который возвращает true, если первый аргумент меньше чем (т.е. упорядочен до) второй. Сигнатура функции сравнения должна быть эквивалентна следующему: bool cmp(const Type1& a, const Type2& b); Хотя сигнатура не обязательно должна иметь const&, функция не должна изменять переданные ей объекты и должна иметь возможность принимать все значения типа (возможно, const) |
| Требования к типам | ||
-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) |
проверяет, отсортирован ли диапазон по возрастанию (ниблоид) |
