std::pop_heap
| Определено в заголовке <algorithm>
|
||
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
|
(1) | (constexpr начиная с C++20) |
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (constexpr начиная с C++20) |
Заменяет значение в позиции first и значение в позиции last - 1 и превращает поддиапазон [first, last - 1) в кучу. Это приводит к удалению первого элемента из кучи [first, last).
[first, last) является кучей по отношению к operator<(до C++20)std::less{}(начиная с C++20).[first, last) является кучей по отношению к comp.Если выполняется любое из следующих условий, поведение не определено:
[first,last)пуст.[first,last)не является кучей по отношению к соответствующему компаратору.
|
(до C++11) |
|
(начиная с C++11) |
Параметры
| first, last | - | пара итераторов, определяющая непустую бинарную кучу диапазон элементов для изменения (извлечение корневого элемента) |
| comp | - | функциональный объект сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true если первый аргумент меньше второго.Сигнатура функции сравнения должна быть эквивалентна следующей:
Хотя сигнатура не обязана содержать |
| Требования к типам | ||
-RandomIt должен соответствовать требованиям LegacyRandomAccessIterator.
| ||
-Compare должен соответствовать требованиям Compare.
| ||
Сложность
Дано N как std::distance(first, last):
operator<(до C++20)std::less{}(начиная с C++20).comp.Пример
#include <algorithm>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
void println(std::string_view rem, const auto& v)
{
std::cout << rem;
if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
std::cout << v;
else
for (int e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
println("after make_heap: ", v);
std::pop_heap(v.begin(), v.end()); // moves the largest to the end
println("after pop_heap: ", v);
int largest = v.back();
println("largest element: ", largest);
v.pop_back(); // actually removes the largest element
println("after pop_back: ", v);
}
Вывод:
after make_heap: 9 5 4 1 1 3
after pop_heap: 5 3 4 1 1 9
largest element: 9
after pop_back: 5 3 4 1 1
Сообщения об ошибках
Следующие отчёты о дефектах, изменяющих поведение, были применены ретроактивно к ранее опубликованным стандартам C++.
| DR | Применено к | Поведение в опубликованном виде | Корректное поведение |
|---|---|---|---|
| LWG 1205 | C++98 | поведение было неясным, если [first, last) пуст
|
поведение не определено в этом случае |
Смотри также
| добавляет элемент в максимальную кучу (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
(C++11) |
проверяет, является ли данный диапазон максимальной кучей (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
(C++11) |
находит наибольший поддиапазон, являющийся максимальной кучей (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
| создаёт максимальную кучу из диапазона элементов (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| превращает максимальную кучу в диапазон элементов, отсортированных по возрастанию (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
(C++20) |
удаляет наибольший элемент из максимальной кучи (функциональный объект алгоритма) |