std::is_heap_until
ja.cppreference.net から
| ヘッダ <algorithm>
|
||
template< class RandomIt >
RandomIt is_heap_until( RandomIt first, RandomIt last );
|
で定義 (1) | (C++11 以降) (C++20 以降 constexpr) |
template< class ExecutionPolicy, class RandomIt >
RandomIt is_heap_until( ExecutionPolicy&& policy,
RandomIt first, RandomIt last );
|
(2) | (C++17 以降) |
template< class RandomIt, class Compare >
RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );
|
(3) | (C++11 以降) (C++20 以降 constexpr) |
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<(C++20 まで)std::less{}(C++20 以降) に関するものです。3) チェックするヒーププロパティは
comp に関するものです。2,4) (1,3) と同じですが、
policy に従って実行されます。 これらのオーバーロードは、以下の式の値が
true である場合にのみオーバーロード解決に参加します:
|
|
(C++20 まで) |
|
|
(C++20 以降) |
引数
| first, last | - | 調べる要素の 範囲 を定義するイテレータのペア |
| policy | - | 使用する 実行ポリシー |
| comp | - | 比較関数オブジェクト (即ち、Compare の要件を満たすオブジェクト)。最初の引数が 2 番目よりも true小さい 場合に を返します。比較関数のシグネチャは以下と同等であるべきです:
シグネチャに |
| 型要件 | ||
-RandomIt は LegacyRandomAccessIterator の要件を満たさなければなりません。
| ||
-Compare は Compare の要件を満たさなければなりません。
| ||
戻り値
範囲 it がヒープであるような最後のイテレータ [first, it)。
計算量
N を std::distance(first, last) とすると:
1,2) O(N) 回の比較を
operator<(C++20 まで)std::less{}(C++20 以降) を使用して行います。3,4) O(N) 回の比較関数
comp の適用を行います。例外
テンプレートパラメータ ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告します:
- アルゴリズムの一部として呼び出された関数が例外を送出し、かつ
ExecutionPolicyが 標準ポリシー のいずれかである場合、std::terminate が呼ばれます。その他のExecutionPolicyについては、動作は処理系定義です。 - アルゴリズムがメモリの確保に失敗した場合、std::bad_alloc が送出されます。
例
このコードを実行
#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++11) |
指定された範囲が最大ヒープかどうか調べる (関数テンプレート & アルゴリズム関数オブジェクト) |
(C++20) |
|
| 要素の範囲から最大ヒープを作成する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| 要素を最大ヒープに追加する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| 最大ヒープから最大の要素を削除する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| 最大ヒープを昇順にソートされた要素の範囲に変換する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
(C++20) |
最大ヒープである最大の部分範囲を見つける (アルゴリズム関数オブジェクト) |