더북(TheBook)

3.6.3 포인터 힙

포인터 힙을 생성할 때는 객체를 비교하는 함수 포인터를 제공해야 한다. 어떻게 작성하는지 예제로 보자.

std::vector<shared_ptr<string>> words
                       { std::make_shared<string>("one"), std::make_shared<string>("two"),
                         std::make_shared<string>("three"), std::make_shared<string>("four") };
std::make_heap(std::begin(words), std::end(words),
         [](const shared_ptr<string>& wp1, const shared_ptr<string>& wp2){ return *wp1 < *wp2; });

make_heap()의 세 번째 인수는 비교 함수를 정의한 람다 표현식이다. 여기서는 간단히 스마트 포인터를 역참조한 string 객체를 비교만 한다. make_heap() 함수 템플릿에는 함수 객체 타입을 위한 매개변수가 있다. priority_queue 컨테이너 어댑터 클래스 템플릿과 달리 템플릿 매개변수는 기본 인수 값을 갖지 않으므로 컴파일러는 함수 호출의 세 번째 인수에서 함수 객체의 타입을 추론한다. make_heap() 함수 템플릿의 세 번째 타입 매개변수에 기본 타입이 지정되어 있다면 우선순위 큐 템플릿에서 한 것처럼 타입 인수를 지정할 수 있다.

push_heap(), pop_heap(), is_heap(heap_until() 함수를 호출할 때도 마지막 인수에 make_heap()에서 사용한 것과 같은 비교 함수를 반드시 지정해야 한다. 람다 표현식에 이름을 지정해서 비교 함수로 제공해도 된다. 또한, sort_heap() 호출에도 비교 함수를 제공해야 한다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.