std::pop_heap
ja.cppreference.net より
| ヘッダ <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)から最初の要素を削除する効果があります。
1)
[first, last) は operator<(C++20まで)std::less{}(C++20から) に関してヒープです。2)
[first, last) は comp に関してヒープです。以下の条件のいずれかが満たされる場合、動作は未定義です:
[first,last)が空である。[first,last)が対応する比較器に関してヒープではない。
|
が |
|
(C++11から) |
引数
| first, last | - | 変更する (ルート要素を取り出す) 空でない二分ヒープレンジを定義するイテレータのペア |
| comp | - | 比較関数オブジェクト (つまり Compare の要件を満たすオブジェクト)。最初の引数が 2 番目の引数よりtrue小さい場合に を返します。比較関数のシグネチャは以下と同等である必要があります:
シグネチャに |
| 型要件 | ||
-RandomIt は LegacyRandomAccessIterator の要件を満たす必要があります。
| ||
-Compare は Compare の要件を満たす必要があります。
| ||
計算量
与えられた N を std::distance(first, last) としたとき:
1) 2log(N) 回以下の
operator<(C++20まで)std::less{}(C++20から) を使用した比較。2) 2log(N) 回以下の比較関数
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) |
最大ヒープから最大の要素を削除する (アルゴリズム関数オブジェクト) |