std::is_heap_until

Определено в заголовочном файле `<algorithm>`
	(1)
template< class RandomIt > RandomIt is_heap_until( RandomIt first, RandomIt last );		(с C++11) (до C++20)
template< class RandomIt > constexpr RandomIt is_heap_until( RandomIt first, RandomIt last );		(с C++20)
template< class ExecutionPolicy, class RandomIt > RandomIt is_heap_until( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(с C++17)
	(3)
template< class RandomIt, class Compare > RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );		(с C++11) (до C++20)
template< class RandomIt, class Compare > constexpr RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );		(с C++20)
template< class ExecutionPolicy, class RandomIt, class Compare > RandomIt is_heap_until( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );	(4)	(с C++17)

Проверяет диапазон [first, last) и находит наибольший диапазон, начинающийся с first, который является кучей.

1) Свойство кучи проверяется относительно operator<.

3) Свойство кучи проверяется относительно comp.

2,4) То же, что и (1,3), но выполняется в соответствии с policy. Эти перегрузки не участвуют в разрешении перегрузки, если

`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) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` запрещено, а также `Type1` за исключением случаев, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt можно было разыменовать и затем неявно преобразовать в оба из них.
Требования к типу
-`RandomIt` должно удовлетворять требованиям LegacyRandomAccessIterator.
-`Compare` должно удовлетворять требованиям Compare.

Возвращаемое значение

Последний итератор it для которого диапазон [first, it) является кучей.

Сложность

Линейная по std::distance(first, last).

Исключение

Перегрузки с параметром шаблона ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной в рамках алгоритма, вызывает исключение, и ExecutionPolicy является одной из стандартных стратегий, std::terminate вызывается. Для любой другой ExecutionPolicy, поведение определяется реализацией.
Если алгоритм не может выделить память, выбрасывается std::bad_alloc.

Примечания

Куча относительно comp (максимальная куча) — это диапазон случайного доступа диапазон [first, last), который имеет следующие свойства:

Дано \(\scriptsize N\)N как last - first, для всех целых i где \(\scriptsize 0 < i < N\)0 < i < N, bool(comp(first[(i - 1) / 2], first[i])) является false.
Новый элемент может быть добавлен с использованием std::push_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).
*first может быть удален с помощью std::pop_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).

Пример

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
 
    std::make_heap(v.begin(), v.end());
 
    // probably mess up the heap
    v.push_back(2);
    v.push_back(6);
 
    auto heap_end = std::is_heap_until(v.begin(), v.end());
 
    std::cout << "all of v:  ";
    for (const auto& i : v)
        std::cout << i << ' ';
    std::cout << '\n';
 
    std::cout << "only heap: ";
    for (auto i = v.begin(); i != heap_end; ++i)
        std::cout << *i << ' ';
    std::cout << '\n';
}

Вывод:

all of v:  9 5 4 1 1 3 2 6
only heap: 9 5 4 1 1 3 2

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применено к	Поведение, как опубликовано	Правильное поведение
LWG 2166	C++11	требование кучи не соответствовало достаточно точно определению максимальной кучи	требование улучшено

См. также

is_heap (C++11)	проверяет, является ли заданный диапазон максимальной кучей (шаблон функции)
make_heap	создаёт максимальную кучу из диапазона элементов (шаблон функции)
push_heap	добавляет элемент в максимальную кучу (шаблон функции)
pop_heap	удаляет наибольший элемент из максимальной кучи (шаблон функции)
sort_heap	преобразует максимальную кучу в отсортированный по возрастанию диапазон элементов (шаблон функции)
ranges::is_heap_until (C++20)	находит наибольший поддиапазон, являющийся максимальной кучей (niebloid)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/is_heap_until