priority_queue
priority_queue (std::priority_queue — 우선순위 큐)
std::priority_queue는 컨테이너 어댑터로, 기본적으로 가장 큰 원소를 상수 시간에 참조할 수 있게 해 주는 우선순위 큐예요. 삽입·추출은 로그 시간이에요.
출처: cppreference
본문
우선순위 큐는 컨테이너 어댑터로, 기본적으로 가장 큰 원소를 상수 시간에 참조할 수 있게 해 주며, 삽입·추출에는 로그 시간이 들어요. 사용자 제공 Compare로 순서를 바꿀 수 있어요. 예를 들어 std::greater<T>를 쓰면 가장 작은 원소가 top()에 나타나요.
priority_queue 작업은 임의 접근 컨테이너에서 힙을 관리하는 것과 비슷하지만, 컨테이너의 구조를 직접 망가뜨리지 않는다는 장점이 있어요. 그러므로 std::priority_queue 사용자는 내부 컨테이너의 힙 불변식을 깨지 않도록 주의해야 해요.
스택과 마찬가지로 반복자를 제공하지 않아요.
템플릿 매개변수
T: 저장된 원소의 타입.Container: 원소를 보관하는 내부 컨테이너 타입. 기본값은std::vector<T>.Compare: 값을 비교하는 Compare 타입. 기본값은std::less<typename Container::value_type>.
멤버 타입
container_type=Containervalue_type=Container::value_typesize_type=Container::size_typereference/const_reference— 참조 타입
멤버 함수
- 생성자/파괴자,
operator= - 원소 접근:
top - 용량:
empty,size - 수정자:
push,push_range,emplace,pop,swap
참고
기본 생성자는 내부 힙을 구성해요. top은 const_reference를 반환하므로 값을 직접 수정할 수는 없어요(프라이빗 컨테이너 접근 제한).