algorithm_is_heap_until
algorithm_is_heap_until (힙이 끝나는 위치 찾기)
std::is_heap_until는 대상 범위를 검사해서 first에서 시작하는 가장 큰 힙 범위를 찾아요. 힙 성질이 깨지는 지점을 돌려줘요.
출처: cppreference
본문
std::is_heap_until는 대상 범위 [first, last)를 검사해서 first에서 시작하며 힙을 나타내는 가장 큰 범위의 끝을 찾아요. <algorithm> 헤더에 정의되어 있어요.
template< class RandomIt >
RandomIt is_heap_until( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );
- 1번 오버로드 — 힙 성질을
operator<(즉std::less{})를 기준으로 검사해요. - 2번 오버로드 — 힙 성질을 비교 함수
comp를 기준으로 검사해요. - 병렬 실행 정책을 받는 오버로드도 있어요.
반환값 (Return value)
first에서 시작하는 가장 긴 힙 범위의 끝(past-the-end) 반복자예요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 최대 𝓞(N)번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
auto it = std::is_heap_until(v.begin(), v.end());
std::cout << std::distance(v.begin(), it) << '\n';
std::make_heap(v.begin(), v.end());
it = std::is_heap_until(v.begin(), v.end());
std::cout << std::distance(v.begin(), it) << '\n';
}
출력:
3
6