fifo_prio_queue.cpp

#include <iostream>
#include <queue> 
#include <vector>

struct node {
    int x, y;
    double t;
    int sq;
     
    node(int _x = 0, int _y = 0, double _t=0) {
        //constructor
        x = _x;
        y = _y;
        t = _t;
        sq = _x * _x + _y * _y;
    }
};
 
struct cmp {
    bool operator()(node a, node b) {
        /*
         The function call operator () can be overloaded for objects
         of class type. When you overload ( ), you are not creating 
         a new way to call a function.
         Rather, you are creating an operator function that can be 
         passed an arbitrary number of parameters.
         priority_queue優先判定為!cmp，所以「由大排到小」需「反向」定義
         實現「最小值優先」
         */
        // return a.x < b.x;
        if(a.x!=b.x){
            return a.x < b.x ; 
        }else{
            return a.t > b.t; // 相同pri 比時間 早近來先做
        }
    }
};
 

int main()
{
    // 實現優先權高先做，優先權相同 先進來的先做
    // FIFO with priority
    // ref: https://yuihuang.com/cpp-stl-priority-queue/
    std::priority_queue <node, std::vector<node>, cmp> pq;
    
    // node( prio, data, time)
    // pq.push(node(1, 2, 0.5));
    // pq.push(node(1, 2, 0.2));
    // pq.push(node(5, 2, 0.6));
    // pq.push(node(1, 5, 0.5));
    // pq.push(node(1, 3, 0.7));
    // pq.push(node(5, 2, 0.1));
    // pq.push(node(1, 4, 0.6));
    
    pq.push(node(1, 2, 1));
    pq.push(node(1, 2, 2));
    pq.push(node(5, 2, 3));
    pq.push(node(1, 5, 4));
    pq.push(node(1, 3, 5));
    pq.push(node(1, 2, 6));
    pq.push(node(5, 2, 7));
    pq.push(node(1, 4, 8));
    pq.push(node(1, 999, 9));
    
    // out
    std::cout<<" size:"  << pq.size() <<std::endl;
    int n_size = pq.size(); //越pop 會越小 不能用pop.size()
    for(int i = 0; i<n_size; i++){
        std::cout<<" x="  << pq.top().x <<" y=" << pq.top().y << " t=" << pq.top().t <<std::endl;
        pq.pop();
    }
    
    std::cout<<"end"<<std::endl;

    return 0;
}