优先级队列中的结构比较

Question

我想在我的应用程序中获得最优先的“数据包”。数据包是一个基本结构，只包含两个字段：名为name的std :: string和作为优先级的整数。我的代码如下：

#include <iostream>
#include <queue>

using namespace std;

typedef struct packet {
    int priority;
    std::string name;

    friend bool operator<(const packet& a, const packet& b) {
        return a.priority > b.priority;
    }

}
packet;

int main() {
    std::priority_queue<packet*> packets; //I must use packet* as pointer (restriction).

    packet* p1 = new packet();
    packet* p2 = new packet();
    packet* p3 = new packet();

    p1->priority = 200;
    p2->priority = 20;
    p3->priority = 89;

    p1->name= "test";
    p2->name = "test2";
    p3->name = "test3";

    packets.push(p1);
    packets.push(p2);
    packets.push(p3);

    std::cout << "first: " << packets.top()->name;
    packets.pop();
    std::cout << "second: " << packets.top()->name;
    packets.pop();
    std::cout << "third: " << packets.top()->name;
    packets.pop();

    return 0;
}

输出：第一：测试3秒：测试2第三：测试1

但我希望首先获得最优先的数据包。我该怎么做才能解决这个问题？谢谢！

Answer 1

#include <iostream>
#include <queue>

using namespace std;

typedef struct packet {
    int priority;
    std::string name;

    friend bool operator<(const packet& a, const packet& b) {
        return a.priority > b.priority;
    }

}
packet;

struct comparator
{
    bool operator()(const packet * a, const packet *b)
    {
        return a->priority > b->priority;
    }
};

//comparator f; edit - no need for this forgot to comment oops

int main() {
    std::priority_queue<packet*,vector<packet*>,comparator> packets; // i add comparator and vector<packet*> here

    packet* p1 = new packet();
    packet* p2 = new packet();
    packet* p3 = new packet();

    p1->priority = 200;
    p2->priority = 20;
    p3->priority = 89;

    p1->name= "test";
    p2->name = "test2";
    p3->name = "test3";

    packets.push(p1);
    packets.push(p2);
    packets.push(p3);

    std::cout << "first: " << packets.top()->name;
    packets.pop();
    std::cout << "second: " << packets.top()->name;
    packets.pop();
    std::cout << "third: " << packets.top()->name;
    packets.pop();

    return 0;
}

在你的std::priority_queue中你需要提供一个comparator来比较元素并优先考虑它们。

我这样做使用struct comparator和bool operator()(packet * a, packet *b)这样做是为了让你用2个()s调用比较器对象packet*然后返回true/false（如果首先的优先级是>或<第二个的优先级）

我还将vector<packet*>容器类型添加到std::priority_queue，以使其成为默认容器（堆上构建的容器）。更多信息：http://en.cppreference.com/w/cpp/container/priority_queue