namespace std::ranges {
template <random_access_iterator I,
sentinel_for<I> S,
class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I
is_heap_until(I first,
S last,
Comp comp = {},
Proj proj = {}); // (1) C++20
template <random_access_range R,
class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
is_heap_until(R&& r,
Comp comp = {},
Proj proj = {}); // (2) C++20
}
概要
範囲がヒープ化されているか判定し、ヒープ化されていない最初の要素を指すイテレータを取得する。
- (1): イテレータ範囲を指定する
- (2): Rangeを直接指定する
戻り値
distance(first, last) < 2 の場合は last を返す。そうでない場合、[first,last] 内のイテレータ i について、[first,i) が heap であるような最後の i を返す。
計算量
線形時間
例
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = {3, 1, 4};
std::cout << std::boolalpha;
std::cout << "before: is heap? "
<< (std::ranges::is_heap_until(v) == v.end()) << std::endl;
std::ranges::make_heap(v);
std::cout << " after: is heap? "
<< (std::ranges::is_heap_until(v) == v.end()) << std::endl;
}
18
#include <iostream>#include <vector>#include <algorithm>int main(){ std::vector<int> v = {3, 1, 4}; std::cout << std::boolalpha; std::cout << "before: is heap? " << (std::ranges::is_heap_until(v) == v.end()) << std::endl; std::ranges::make_heap(v); std::cout << " after: is heap? " << (std::ranges::is_heap_until(v) == v.end()) << std::endl;}出力
before: is heap? false
after: is heap? true
バージョン
言語
- C++20
処理系
- Clang: ??
- GCC: 10.1.0 ✅
- ICC: ??
- Visual C++: 2019 Update 10 ✅