C++11

// <algorithm> 
// 默认(1)
template <class RandomAccessIterator>
    RandomAccessIterator is_heap_until (
        RandomAccessIterator first,
        RandomAccessIterator last);
// 自定义(2)    
template <class RandomAccessIterator,
    class Compare>
    RandomAccessIterator is_heap_until (
        RandomAccessIterator first,
        RandomAccessIterator last
        Compare comp);

检测给定范围中满足堆结构的最大子范围。

该函数等价于:

template<class _RanIt,
class _Pr>
    _RanIt is_heap_until(_RanIt _First, _RanIt _Last, _Pr _Pred)
{	// find extent of range that is a heap ordered by _Pred
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Pred);
    return (_Rechecked(_First,
        _Is_heap_until(_Unchecked(_First), _Unchecked(_Last), _Pred,
        _Dist_type(_First))));
}

template<class _RanIt,
class _Diff,
class _Pr> inline
    _RanIt _Is_heap_until(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *)
{	// find extent of range that is a heap ordered by _Pred
    _Diff _Size = _Last - _First;

    if (2 <= _Size)
        for (_Diff _Off = 0; ++_Off < _Size;)
            if (_DEBUG_LT_PRED(_Pred, *(_First + (_Off - 1) / 2),
                *(_First + _Off)))
                return (_First + _Off);
    return (_Last);
}
  • firstlast

    分别指向指定范围中初始及末尾位置的随机访问迭代器(Random-access Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    comp

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 返回指向某个元素的迭代器,该元素最先出现且使其之前的范围不为堆。

    如果所有元素都在合适的位置,即整个序列符合堆结构,则返回 last

    如果范围中元素个数小于 2则返回 last

  • 参照 std::sort 以获得与自定义函数谓词、函数对象谓词、对象数组、lambda 表达式 C++11、初始化列表 std::initializer_list C++11 等相关的例子。

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
    
        void IsHeapUntil_1() {
            // 构造 vector 对象
            CLASSFOO_VECTOR(int, foo, { 0, 3, 6, 8, 10, -2, 13 });
    
            std::vector<int>::iterator it;
            it = std::is_heap_until(foo.begin(), foo.end());
            if (foo.end() != it)
                std::cout << *it << std::endl;
            std::make_heap(foo.begin(), foo.end());
            it = std::is_heap_until(foo.begin(), foo.end());
            if (foo.end() == it)
                std::cout << "The entire range is a heap." << std::endl;
        }
    }
    int main()
    {
        ClassFoo::IsHeapUntil_1();
        return 0;
    }

    3
    The entire range is a heap.

  • 复杂度

    O(N)N 等值于 std::distance(first,last)

    数据争用相关

    范围 [first,last) 中的所有元素都有可能被访问改过。

    异常安全性相关

    如果元素比较或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)