c++ - 在 C++ 中创建一个包含不同类型事件的最小优先级队列

Question

class Event
{
    // Overloading the comparison operators
    friend bool operator < (const Event& e1, const Event& e2);
    friend bool operator == (const Event& e1, const Event& e2);

public:
    Event() {};
    enum EvtType {arrival_1, arrival_2, arrival_3, arrival_4, arrival_5, arrival_6};
    Event(EvtType type, double etime):
        _type(type), _etime(etime) {}

    EvtType get_Type()
    {
       return _type;
    }

    double get_time()
    {
       return _etime;
    }

protected:
    EvtType _type;
    double _etime;
};



bool operator < (const Event& e1, const Event& e2)
{
return e2._etime < e1._etime;
}

bool operator == (const Event& e1, const Event& e2)
{
     if(e1._etime != e2._etime)return false;
     if(e1._type == (Event::arrival_2 && Event::arrival_3 &&    Event::arrival_4 && Event::arrival_5 && Event::arrival_6)) return true;
     return false;
}


priority_queue <Event> FEL;

我创建了一个名为“事件”的类，其中包含多种类型的事件和发生时间。在此之后，我想创建一个优先队列“FEL”来包含这些事件及其时间。然而，一般来说，优先级队列总是根据所有最大值对事件进行排序。

我如何根据最小值对这些事件进行排序，以便在我调用 FEL.top() 时，我将获得时间最短的事件。

我试图通过使用 bool 运算符来解决这个问题。但它仍然有问题。任何人请帮助解决这个问题。

非常感谢

Answer 1

std::priority_queue容器适配器是一个最大队列结构。它利用“较少”比较器以最大 项始终排在第一位的方式对排队的项进行排序。因此，如果您想首先处理最小的项目，您需要一个比较器，它的作用与您最初看起来很自然的相反。

举个简单的例子，假设你有一个 vector int值，并且您希望它们按最大到最小的优先顺序排列。这是 std::priority_queue<int> 的自然默认操作操作.它使用 std::less<int>确定项目的顺序(哪个在前，哪个在后)，并根据这些结果确保最大的出现在队列中的第一个。考虑下面的例子，它有两个 int队列，一个使用std::less<int>另一个std::greater<int>比较:

#include <iostream>
#include <algorithm>
#include <queue>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<> dist(1,10);

    std::priority_queue<int, std::vector<int>, std::less<int>> q1;
    std::priority_queue<int, std::vector<int>, std::greater<int>> q2;

    for (int i=0; i<20; ++i)
    {
        int value = dist(rng);
        q1.push(value);
        q2.push(value);
    }

    std::cout << "q1: ";
    for (; !q1.empty(); q1.pop())
        std::cout << q1.top() << ' ';
    std::cout << '\n';

    std::cout << "q2: ";
    for (; !q2.empty(); q2.pop())
        std::cout << q2.top() << ' ';
    std::cout << '\n';
}

输出(变化)

q1: 10 10 8 8 8 7 6 6 5 5 5 4 4 4 3 3 3 2 1 1 
q2: 1 1 2 3 3 3 4 4 4 5 5 5 6 6 7 8 8 8 10 10 

如您所见，在确定排序时使用“更大”比较器作为其 less-op 的队列会提供您所寻求的结果。我们只需要将这样的东西放入您的队列及其 Event类型

---

您需要一个与默认顺序相反的比较器:

#include <iostream>
#include <algorithm>
#include <queue>

class Event
{
public:
    enum EvtType { arrival_1, arrival_2, arrival_3, arrival_4, arrival_5, arrival_6 };

    Event(EvtType type = arrival_1, double etime = 0.0)
        : _type(type)
        , _etime(etime)
    {}

    EvtType get_Type() const { return _type; };
    double get_Time() const { return _etime; }

protected:
    EvtType _type;
    double _etime;
};

struct EventLess
{
    bool operator()(const Event& lhs, const Event& rhs) const
    {
        return (lhs.get_Time() > rhs.get_Time());
    }
};

int main()
{

    std::priority_queue<Event, std::vector<Event>, EventLess> q;
    q.push(Event(Event::arrival_1, 3.0));
    q.push(Event(Event::arrival_2, 2.0));
    q.push(Event(Event::arrival_3, 1.0));
    q.push(Event(Event::arrival_1, 1.0));
    q.push(Event(Event::arrival_2, 2.0));
    q.push(Event(Event::arrival_3, 3.0));

    while (!q.empty())
    {
        const Event& e = q.top();
        std::cout << e.get_Type() << ' ' << e.get_Time() << '\n';
        q.pop();
    }
}

输出

2 1
0 1
1 2
1 2
0 3
2 3

注意时间值(第二个)是从小到大排列的。这是因为我们的比较器 EventLess说“时间较大的项目比时间较小的项目‘少’”，队列自然会将这些项目推到队列中，而不是将它们提升到顶部。使这项工作成功的原因很简单:

struct EventLess
{
    bool operator()(const Event& lhs, const Event& rhs) const
    {
        return (lhs.get_Time() > rhs.get_Time());
    }
};

这里我们告诉调用者(队列适配器)给定两个元素，具有更大时间值的元素应该被认为“小于”具有更小时间值的元素。然后队列将项目从大到小排序。

我想您了解自定义比较的必要性。我只是觉得你不明白 std::priority_queue作品。这是一个最大队列。你只需要让它相信你对 max 的定义是不同的。