c++ - 优先级队列中的结构比较

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;
}

输出: 第一个:test3 第二个:test2 第三个:test1

但我想首先获得优先级最高的数据包。我该如何解决这个问题？谢谢!

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 packet* s，然后返回 true/false (如果第一个的优先级 > 或 < 第二个的优先级)

我还添加了vector<packet*>容器类型为std::priority_queue使其成为默认容器(在其上构建堆)。更多信息在这里: http://en.cppreference.com/w/cpp/container/priority_queue