如何使优先级队列使用自定义变量 a class (Ascending/descending)

Question

我在使用 C++ 中的 priority_queue 时遇到问题，我有一个优先级队列向量，优先级队列包含几个 Person 对象。现在我想让 priority_queue 根据对象的年龄优先处理 Person 对象。所以我有这样的东西：

class Person
{
public:
  string name;
  int height;
  int age;
};

std::vector<std::priority_queue<Person*>> Persons;

我如何确保无论何时将某人添加到优先队列之一，都会根据他们的年龄对他们进行优先排序？我将如何按 ascending/descending 顺序执行此操作？

Answer 1

std::priority_queue 有一个满足您需要的界面。它需要三个模板参数：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

第三个是您需要更改以处理元素比较的内容。

// make a functor to do the comparisons
struct comparator
{
    bool operator()(Person* lhs, Person* rhs) const {
        // sort by age
        return lhs->age < rhs->age; // switch the sign for reverse order
    }
};

// have a type alias for convenience (typedef is fine too)
using pqueue = std::priority_queue<Person*, std::vector<Person*>, comparator>;

int main() 
{
    std::vector<pqueue> persons; 
}

Answer 2

你可以这样实现：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;



class Person
{
public:
    string name;
    int height;
    int age;

};

struct OrderByAge
{
    bool operator() (Person const &a, Person const &b) { return a.age > b.age; }
};


int main() 
{
    vector<priority_queue<Person, std::vector<Person>,OrderByAge> > personPQVec{ 1 };

    Person p1{ "nitendra",5,39 };
    Person p2{ "bhosle",6,34 };
    Person p3{ "nit",4,33 };


    personPQVec[0].push(p1);
    personPQVec[0].push(p2);
    personPQVec[0].push(p3);


    while (!personPQVec[0].empty()) {

        cout << "Name: " << (personPQVec[0]).top().name << ", age: " << (personPQVec[0]).top().age << endl;
        (personPQVec[0]).pop();
    }
    system("pause");
    return 0;
}

Answer 3

您可以将谓词作为第三个参数传递来检测排序顺序，为您的 Person*

声明两个谓词

struct AscendingPersonPredicate
{
    bool operator() ( Person* p1, Person* p2) const
    {
        return p1->age < p2->age;
    }
};

struct DescendingPersonPredicate
{
    bool operator() ( Person* p1, Person* p2) const
    {
        return p1->age > p2->age;
    }
};

然后将您的向量声明为：

std::priority_queue<Person*, vector<Person*>, AscendingPersonPredicate> Persons;

或

std::priority_queue<Person*, vector<Person*>, DescendingPersonPredicate> Persons;

Answer 4

你实际上不需要包装你的 priority_queue 的额外向量，因为 priority_queue 本身有 2 个额外的默认参数：（第一个是类型，在您的例子中是 Person*），第二个是容器类型，第三个是比较谓词。您可以在下面看到使用 lambda 函数作为优先级队列的比较谓词。

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

using namespace std;

class Person
{
public:
    string name;
    int height;
    int age;

    Person(string n, int h, int a): name(n), height(h), age(a) {}
};


ostream& operator<<(ostream &cout, const Person* p) {
    return cout << p->name << " height=" << p->height << " age=" << p->age << " ";
}

int main()
{
    auto cmp = [](const Person* pl, const Person* pr) {
        return (pl->age < pr->age);
    };

    priority_queue<Person*, vector<Person*>, decltype(cmp)> persons(cmp);

    persons.push(new Person("a", 100, 10));
    persons.push(new Person("b", 120, 20));
    persons.push(new Person("c", 110, 15));

    while (!persons.empty()) {
        cout << persons.top() << endl;
        persons.pop();
    }

    return 0;
}

如何使优先级队列使用自定义变量 a class (Ascending/descending)

How to make a priority queue use a variable from custom a class (Ascending/descending)

c++

priority-queue