is_heap-c和c++中文资料站

C&C++标准库

std::

is_heap

函数模板 <algorithm>

default (1)

template <class RandomAccessIterator>
  bool is_heap (RandomAccessIterator first, RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>
  bool is_heap (RandomAccessIterator first, RandomAccessIterator last,
                Compare comp);

测试范围是否为堆

如果range [first,last)是一个堆，则返回true，就像使用make_heap构造的那样。
第一个版本使用 operator< 比较元素，第二个版本使用comp操作符比较元素.

☲ 参数

first, last: 指向序列的初始和最终位置的随机访问迭代器。使用的范围是[first,last)，它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
comp: 二元函数，接受范围内的两个元素作为参数，并返回一个可转换为bool类型的值。返回的值表示作为第一个参数传递的元素是否被认为在它定义的特定严格弱排序中位于第二个参数之前。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。

☉ 返回值

如果range [first,last)是一个堆(就像用make_heap构造的)则为True，否则为false。

如果range [first,last)包含的元素少于两个，函数总是返回true。

☣ 示例

// is_heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::is_heap, std::make_heap, std::pop_heap
#include <vector>       // std::vector

int main () {
  std::vector<int> foo {9,5,2,6,4,1,3,8,7};

  if (!std::is_heap(foo.begin(),foo.end()))
    std::make_heap(foo.begin(),foo.end());

  std::cout << "Popping out elements:";
  while (!foo.empty()) {
    std::pop_heap(foo.begin(),foo.end());   // moves largest element to back
    std::cout << ' ' << foo.back();         // prints back
    foo.pop_back();                         // pops element out of container
  }
  std::cout << '\n';

  return 0;
}

输出:
Popping out elements: 9 8 7 6 5 4 3 2 1

✥ 复杂度

first and last的距离是线性减1: 比较元素对，直到找到不匹配的元素。

⇄ 数据竞争

范围 [first,last)内的对象被访问。

☂ 异常安全性

如果任何元素比较或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。

🍄 另请参阅

is_heap_until	找到第一个不是堆顺序的元素(函数模板)
make_heap	从范围构建堆(函数模板)
sort_heap	对堆元素进行排序(函数模板)