Namespaces
Variants

std:: is_heap_until

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
(C++11)
is_heap_until
(C++11)
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
ヘッダ <algorithm> で定義
template < class RandomIt >
RandomIt is_heap_until ( RandomIt first, RandomIt last ) ;
(1) (C++11以降)
(constexpr since C++20)
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以降)
(constexpr since 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 < (C++20以前) std:: less { } (C++20以降) に関するものです。
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 の要件を満たすオブジェクト）。最初の引数が2番目の引数より 小さい 場合に 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 の要件を満たさなければならない。

戻り値

範囲 [ first , it ) がヒープとなる最後のイテレータ 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());
    // ヒープを乱す可能性がある
    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)
最大ヒープである最大の部分範囲を見つける
(アルゴリズム関数オブジェクト)