如何使用优先级队列STL对象？

Question

class Person
{
public:
    int age;
};

我想将类Person的对象存储在优先级队列中.

priority_queue< Person, vector<Person>, ??? >

我想我需要为比较事物定义一个类,但我不确定.

还有,当我们写的时候,

priority_queue< int, vector<int>, greater<int> > 

更大的工作如何？

Answer 1

Person在这种情况下,您需要为存储在队列中的类型提供有效的严格弱排序比较.默认是使用std::less<T>,它解析为相当于的东西operator<.这依赖于它自己的存储类型.所以,如果你要实施

bool operator<(const Person& lhs, const Person& rhs); 

它应该没有任何进一步的变化.实施可能是

bool operator<(const Person& lhs, const Person& rhs)
{
  return lhs.age < rhs.age;
}

如果该类型没有自然的"小于"比较,那么提供自己的谓词而不是默认值会更有意义std::less<Person>.例如,

struct LessThanByAge
{
  bool operator()(const Person& lhs, const Person& rhs) const
  {
    return lhs.age < rhs.age;
  }
};

然后像这样实例化队列:

std::priority_queue<Person, std::vector<Person>, LessThanByAge> pq;

关于使用std::greater<Person>比较器,这将使用等效的operator>并且具有创建具有优先级反转WRT的队列的默认情况的效果.它需要一个operator>可以在两个Person实例上运行的存在.

Answer 2

你会写一个比较器类,例如:

struct CompareAge {
    bool operator()(Person const & p1, Person const & p2) {
        // return "true" if "p1" is ordered before "p2", for example:
        return p1.age < p2.age;
    }
};

并将其用作比较器参数:

priority_queue<Person, vector<Person>, CompareAge>

使用greater与默认值相反的排序less,这意味着队列将为您提供最低值而不是最高值.

Answer 3

优先级队列是一种抽象数据类型,它捕获容器的概念,该容器的元素具有附加到它们的"优先级".优先级最高的元素始终显示在队列的前面.如果删除该元素,则下一个最高优先级元素前进到前面.

C++标准库定义了一个类模板priority_queue,具有以下操作:

push:将元素插入prioity队列.

top:从优先级队列中返回(不删除它)最高优先级元素.

pop:从优先级队列中删除优先级最高的元素.

size:返回优先级队列中的元素数.

empty:根据优先级队列是否为空,返回true或false.

以下代码段显示了如何构造两个优先级队列,一个可以包含整数,另一个可以包含字符串:

#include <queue>

priority_queue<int> q1;
priority_queue<string> q2;

以下是优先级队列使用的示例:

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

using namespace std;  // This is to make available the names of things defined in the standard library.

int main()
{
    piority_queue<string> pq; // Creates a priority queue pq to store strings, and initializes the queue to be empty.

    pq.push("the quick");
    pq.push("fox");
    pq.push("jumped over");
    pq.push("the lazy dog");

    // The strings are ordered inside the priority queue in lexicographic (dictionary) order:
    // "fox", "jumped over", "the lazy dog", "the quick"
    //  The lowest priority string is "fox", and the highest priority string is "the quick"

    while (!pq.empty()) {
       cout << pq.top() << endl;  // Print highest priority string
       pq.pop();                    // Remmove highest priority string
    }

    return 0;
}

该程序的输出是:

the quick
the lazy dog
jumped over
fox

由于队列遵循优先级规则,因此字符串将从最高优先级打印到最低优先级.

有时需要创建一个优先级队列来包含用户定义的对象.在这种情况下,优先级队列需要知道用于确定哪些对象具有最高优先级的比较标准.这是通过一个函数对象完成的,该函数对象属于一个重载operator()的类.overloaded()充当<用于确定优先级的目的.例如,假设我们要创建一个优先级队列来存储Time对象.Time对象有三个字段:hours,minutes,seconds:

struct Time {
    int h; 
    int m; 
    int s;
};

class CompareTime {
    public:
    bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
}

根据上述比较标准存储时间的优先级队列定义如下:

priority_queue<Time, vector<Time>, CompareTime> pq;

Here is a complete program:

#include <iostream>
#include <queue>
#include <iomanip>

using namespace std;

struct Time {
    int h; // >= 0
    int m; // 0-59
    int s; // 0-59
};

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2)
    {
       if (t1.h < t2.h) return true;
       if (t1.h == t2.h && t1.m < t2.m) return true;
       if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
       return false;
    }
};

int main()
{
    priority_queue<Time, vector<Time>, CompareTime> pq;

    // Array of 4 time objects:

    Time t[4] = { {3, 2, 40}, {3, 2, 26}, {5, 16, 13}, {5, 14, 20}};

    for (int i = 0; i < 4; ++i)
       pq.push(t[i]);

    while (! pq.empty()) {
       Time t2 = pq.top();
       cout << setw(3) << t2.h << " " << setw(3) << t2.m << " " <<
       setw(3) << t2.s << endl;
       pq.pop();
    }

    return 0;
}

该程序打印从最新到最早的时间:

5  16  13
5  14  20
3   2  40
3   2  26

如果我们希望最早的时间具有最高优先级,我们将重新定义CompareTime,如下所示:

class CompareTime {
public:
    bool operator()(Time& t1, Time& t2) // t2 has highest prio than t1 if t2 is earlier than t1
    {
       if (t2.h < t1.h) return true;
       if (t2.h == t1.h && t2.m < t1.m) return true;
       if (t2.h == t1.h && t2.m == t1.m && t2.s < t1.s) return true;
       return false;
    }
};