priority_queue 使用自定义 cmp

Question

我试图实现按事件字段排序的事件队列。所以我写了类似的东西：

struct MyAlgo 
{
   MyAlgo() {
      // some random generation of positions
      for (auto pos : RandomPostions)
        Queue.push({SiteEvent, pos, NULL});
   }
   struct Event
   {
      EventType Type;
      FVector2D Pos;
      Node* Arc;
   }
   bool cmp(const Event& a, const Event& b) { return a.Pos.Y > a.Pos.Y; }
   std::priority_queue<Event, std::vector<Event>, decltype(&cmp)> Queue;
}

在并且我的队列中没有有序元素。怎么了？

Answer 1

您需要一个静态函数（以匹配比较操作的签名）。此外，您需要限定名称：

static bool cmp(const Event& a, const Event& b) {
    return a.Pos.Y > b.Pos.Y;
}
std::priority_queue<Event, std::vector<Event>, decltype(&MyAlgo::cmp)>
    Queue { &MyAlgo::cmp };

此外，请注意比较本身存在缺陷（它将变量与自身进行比较，导致 Undefined Behaviour 因为不一致的弱总排序。

简化

将比较器设为函数对象：

struct Cmp {
    bool operator()(const Event& a, const Event& b) const {
        return a.Pos.Y > b.Pos.Y;
    }
};
std::priority_queue<Event, std::vector<Event>, Cmp> Queue;

现在你不能忘记将 cmp 实例传递给构造函数。

现场演示

Live On Coliru

#include <queue>
#include <iostream>
#include <array>

enum class EventType { SiteEvent };
struct FVector2D {
    float X, Y;
    friend std::ostream& operator<<(std::ostream& os, FVector2D const& fv)
    {
        return os << "{" << fv.X << "," << fv.Y << "}";
    }
};

struct Node {
};

struct MyAlgo {
    MyAlgo()
    {
        // some random generation of positions
        for (auto pos : {FVector2D{1, 22}, {2, 3}, {8, 33}}) {
            Queue.push({EventType::SiteEvent, pos, nullptr});
        }
    }

    struct Event {
        EventType Type;
        FVector2D Pos;
        Node*     Arc = nullptr;

        friend std::ostream& operator<<(std::ostream& os, Event const& ev) {
            return os << ev.Pos;
        }
    };

    struct Cmp {
        bool operator()(const Event& a, const Event& b) const {
            return a.Pos.Y > b.Pos.Y;
        }
    };
    std::priority_queue<Event, std::vector<Event>, Cmp> Queue;
};

int main()
{
    MyAlgo algo;

    while (not algo.Queue.empty()) {
        std::cout << algo.Queue.top() << "\n";
        algo.Queue.pop();
    }
}

版画

{2,3}
{1,22}
{8,33}

priority_queue 使用自定义 cmp

priority_queue with custom cmp

c++

queue

简化

现场演示