STL 우선 순위 대기열 : 리조트가 언제/어떻게 발생합니까?

Question

구조체의 STL priority_queue (우선 순위가 구조체의 일부 특성을 기반으로하는 경우)와 구조체 중 하나의 특성이 변경되어 새로운 순서가 달라 지므로 우선 순위 큐가 자체적으로 리조트를 알 수 있습니까? ? 아니면 큐에서 제거하고 다시 입력해야합니까? push() 및 pop()이 호출 될 때 정렬이 완료되는 것을 읽었지 만 확실히하고 싶습니다.

Answer 1

설명하는 것을 수행 할 방법이 없습니다.

는 우선 순위 큐에 상품을 밀어 세 가지 방법이있다 :

1. push() (이 기준 이동하거나에서 항목을 복사하는 것이 아니라 복용을 의미한다) 다른 용기 또는 전달
2. 을 큐가 생성 될 때 반복자 범위 (복사 또는 이동을 생성 한 다음 사본에 힙을 만들거나 원본에 대한 참조가 유지되지 않음)
3. emplace() (이는 큐 내부에 새 항목을 만드는 것을 의미합니다. HOUT 는 액세스 요소)

유일한 방법에 대한 참조를 얻을 수있는 것은 CONST 참조를 반환 top() 기능을한다.

따라서 항목을 푸시 할 때 항목에 대한 참조를 유지하거나 이미 대기열에있는 항목에 대한 참조가 아닌 참조를 얻는 방법은 없습니다. 따라서 대기열 항목을 직접 수정하는 방법은 없습니다.

이론상으로 정렬 순서에 영향을 줄 수있는 수정 방법은 대기열의 항목에 외부 개체에 대한 포인터가 포함되어 있고 정렬 순서가 외부 개체의 내용에 따라 달라지는 경우입니다. 이 경우 큐 항목이 큐 포인트를 가리키는 동안 해당 외부 개체를 분명히 수정할 수 있습니다. 정렬 순서가 무효화 될 것입니다. – 우선 순위 큐는 수정에 대해 알지 못하기 때문에 우선 순위 큐를 업데이트하지 않습니다.

Answer 2

priority_queuepush() 및 pop() 멤버 함수 범위로 전달 된 하부 용기의 전체 내용과 push_heap() 및 pop_heap() 라이브러리 함수의 거동의 관점에서 정의된다. "유효한 힙한다"(즉, 추가되는 항목이기 때문에하는 push_heap()에 컨테이너의 마지막 항목 제외)

그 기능은 범위가 필요합니다. 컨테이너가 더 이상 유효한 힙이 아니도록 포함 된 요소를 수정하면 정의되지 않은 동작이 발생합니다.

그런 식으로 요소를 수정해야하는 경우 요소를 제거하고 수정 한 다음 다시 추가해야합니다. 또는 내용을 엉망으로 만든 다음 make_heap()을 호출하여 힙을 다시 작성할 수 있습니다.

C++ 11 23.6.4.3 "priority_queue members", 25.4.6.1 "push_heap"및 25.4.6.2 "pop_heap"을 참조하십시오.

Answer 3

확실히 올바른 방법으로 재정렬되지는 않지만 적어도 보장 할 수는 없습니다. priority_queue의 push() 및 pop()은 기본 힙 구조의 std :: push_heap() 및 std :: pop_heap()을 호출하기 만하면됩니다.

push(const value_type& x) 

의 효과 C 큐의 기본적인 용기이고, 여기서 (23.2.3.2.2)가 C++ 03 표준에 따라

c.push_back(x); 
push_heap(c.begin(), c.end(), comp); 

이다

comp 주문 기능. 유효한 힙한다 -

한 요건 push_heap는

범위 [1, 성]이다.

에 따라 C++ 03 표준의 25.3.6.1에 따른다.

priority_queue의 기존 구조를 수정하면 힙 구조가 손상되고 make_heap을 사용하여 다시 만들어야 유효한 힙 구조가됩니다.

priority_queue는 메소드 중 하나를 호출하여 통지되지 않으므로 외부 참조/포인터를 사용하여 요소를 수정했는지 알 길이 없습니다.

요소를 제거하고 다시 추가하여 원하는 것을 달성해야합니다. 완전히 다른 컨테이너를 사용하여 std :: map과 같이 제거하고 다시 추가 할 요소에 대한 유연성을 확보 할 수 있습니다.