std::pop_heap
来自 cppreference.com
定义在头文件 <algorithm> 中 |
||
template< class RandomIt > void pop_heap( RandomIt first, RandomIt last ); |
(1) | (从 C++20 开始为 constexpr) |
template< class RandomIt, class Compare > void pop_heap( RandomIt first, RandomIt last, Compare comp ); |
(2) | (从 C++20 开始为 constexpr) |
交换位置 first 的值和位置 last - 1 的值,并将子范围 [
first,
last - 1)
变成堆。这将从堆 [
first,
last)
中移除第一个元素。
2)
[
first,
last)
是一个相对于 comp 的堆。如果满足以下任何条件,则行为未定义
-
[
first,
last)
为空。 -
[
first,
last)
不是一个相对于相应比较器的堆。
|
(直到 C++11) |
|
(从 C++11 开始) |
内容 |
[编辑] 参数
first, last | - | 要修改的非空堆 |
comp | - | 比较函数对象(即满足 Compare 要求的对象),如果第一个参数小于第二个参数,则返回 true。 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 虽然签名不需要 const&,但该函数不能修改传递给它的对象,并且必须能够接受类型(可能是 const) |
类型要求 | ||
-RandomIt 必须满足 LegacyRandomAccessIterator 的要求。 | ||
-Compare 必须满足 Compare 的要求。 |
[编辑] 复杂度
假设 N 为 std::distance(first, last)
2) 对比较函数 comp 进行调用,最多进行 2log(N) 次。
[编辑] 示例
运行此代码
#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++11) |
检查给定范围是否为最大堆 (函数模板) |
(C++11) |
找到最大堆的最大子范围 (函数模板) |
从元素范围创建一个最大堆 (函数模板) | |
将最大堆转换为按升序排序的元素范围 (函数模板) | |
(C++20) |
从最大堆中删除最大元素 (niebloid) |