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

C&C++标准库

std::

is_heap_until

函数模板 <algorithm>

default (1)

template <class RandomAccessIterator>
  RandomAccessIterator is_heap_until (RandomAccessIterator first,
                                      RandomAccessIterator last);

custom (2)

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

查找不是按堆顺序排列的第一个元素

返回range [first,last)中第一个下述元素的迭代器: 如果该范围被认为是堆(就像使用make_heap构造)，则该元素不在有效位置上。
first 和返回的迭代器之间的范围是一个堆。

如果整个范围是一个有效的堆，则函数返回last。

第一个版本使用 operator< 比较元素，第二个版本使用comp操作符比较元素.

☲ 参数

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

☉ 返回值

一个迭代器，指向范围内的第一个这样的元素: 如果该范围是堆，则该元素的位置不合法，如果所有元素都被有效，或如果该范围内包含的元素少于两个，则该元素的位置为last.

☣ 示例

// is_heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::is_heap_until, std::sort, std::reverse
#include <vector>       // std::vector

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

  std::sort(foo.begin(),foo.end());
  std::reverse(foo.begin(),foo.end());

  auto last = std::is_heap_until (foo.begin(),foo.end());

  std::cout << "The " << (last-foo.begin()) << " first elements are a valid heap:";
  for (auto it=foo.begin(); it!=last; ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

大多数的实现都认为一个范围按倒序排序就是一个有效的堆:
可能的输出:
The 9 first elements are a valid heap: 9 8 7 6 5 4 3 2 1

✥ 复杂度

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

⇄ 数据竞争

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

☂ 异常安全性

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

🍄 另请参阅

is_heap	测试range是否为heap(函数模板)
make_heap	从范围构建堆(函数模板)
is_sorted_until	对堆元素进行排序(函数模板)