개체의 우선 순위 큐를 사용하는 C++

Question

개체의 우선 순위 큐를 만들고 싶습니다. 특히 (int, int) 쌍입니다. 대기열에는 우선 순위가 지정된 쌍이 있어야합니다. 당신이 볼 수 있듯이 그것은 상단에 남아 있도록

#include <iostream> 
#include <queue> 

using namespace std;  

class saPair{ 
public: 
    int s; 
    int a; 
    double priority; 
    saPair(int s, int a, double priority){ 
     this->s = s; 
     this->a = a; 
     this->priority = priority; 
    } 
}; 

// the priority menmber variable determines the priority in the queue 
// highest priority pair of (int, int) stays on the top 
bool operator< (const saPair& x, const saPair& y) { 
    return x.priority < y.priority; 
} 


int main() 
{ 
    priority_queue<saPair> pq; 
    pq.push(saPair(0,0, 0.3)); 
    pq.push(saPair(0,1, 0.1)); 
    pq.push(saPair(0,3, 0.5)); 
    pq.push(saPair(0,3, 5)); 

    cout << pq.top().a << endl; 
    pq.pop(); 
    cout << pq.top().a << endl; 
    pq.pop(); 
    cout << pq.top().a << endl; 


} 

은 쌍 (0,3)은 가장 높은 우선 순위를 가지고있다. 하지만 구현의 문제는 다른 우선 순위로 (0,3) 쌍을 다시 추가하면 이미 존재하는 (0,3) 쌍의 우선 순위를 바꾸는 대신 새 요소를 대기열에 추가한다는 것입니다.

내 요구 사항에 잘못된 데이터 구조를 선택했다고 느낍니다. < 연산자에 대한 연산 오버로드로 새로운 saPair (int, int) 클래스를 정의하여 키 값을 가져 오는 맵핑을 시도했습니다. 하지만 그게 제대로 작동하지 않는 것 같습니다 ..

진행 방법에 대한 제안이 있으십니까? 또는 수정

Answer 1

컨테이너에 대한 다중 키 액세스가 필요합니다 : 우선 순위에 따라 정렬 (또는 최소한 priority_queue의 우선 순위에 따라 바이너리 힙이 있어야 함)하고 쌍 값을 원한다면 고유하므로 쌍 값 조회가 필요합니다.

표준 라이브러리에는 기본 해결책이 없지만 직접 제작하는 것은 어렵지 않습니다.

페어가 이미 컨테이너에 있는지 확인하기 위해 std::set<saPair>을 추가로 저장하는 것이 좋습니다. 이 방법으로 당신은 당신의 priority_queue을 그대로 유지할 수 있으며, 구현하는데 너무 많은 노력을 기울이지 않을 것입니다.

그렇지 않으면 std::set는 작업을 할 수 없을 것입니다,하지만 saPair에 operator<을 추가하는 것을 잊지 (또는 std::pair로 교체)하지 마십시오.

또 다른 옵션은 수동으로 추가 할 때마다 priority_queue 쌍을 확인하는 것입니다. 점차적으로 std::set 솔루션보다 나 빠지긴하지만, 실제로는 더 빠를 수도 있습니다. 그리고 공간을 절약 할 수 있습니다. 그러나 std::set을 사용하면 코드가 훨씬 더 명확해질 것이라고 생각합니다.

또 다른 솔루션은 boost::multi_index이며 원하는 다중 색인 컨테이너를 쉽게 만들 수 있습니다. 그러나 우선 순위에 따라 강력한 순서를 지정할 필요가 없다는 사실을 활용할 수 있다고 생각하지 않으므로 priority_queue과 같이 선형 연속 레이아웃을 갖지 않습니다.