Namespaces
Variants

    std::is_heap_until

    来自 zh.cppreference.net
     
    C++
     
    算法库
    受约束算法和范围算法 (C++20)
    受约束算法，例如 ranges::copy、ranges::sort，...
    排序和相关操作
    划分操作
    (C++11)    
    (C++11)

    排序操作
    二分搜索操作
    (在已划分的范围上)
    集合操作（在已排序的范围上）
    合并操作（在已排序的范围上）
    堆操作
    最小/最大操作
    (C++11)
    (C++17)
    字典序比较操作
    (C++20)
    排列操作


     
    定义于头文件 <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 时，这些重载才参与重载决议：

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(C++20 前)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(C++20 起)

    参数

    first, last - 定义要检查的元素范围的一对迭代器
    policy - 使用的执行策略
    comp - 比较函数对象（即满足 Compare 要求的对象），如果第一个参数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 的要求。

    返回值

    使范围 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)
    		 找出最大子范围，该子范围是最大堆
    (算法函数对象)