按相反顺序的优先队列

Question

此网站建议，如果我想要将我的优先队列倒序排序，应使用以下代码：

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

class mycomparison{
    bool reverse;
  public:
    mycomparison(const bool &revparam=false) {reverse=revparam;}
    bool operator() (const int &lhs, const int &rhs) const {
      if (reverse) return (lhs>rhs);
      else         return (lhs<rhs);
    }
};

int main (){
  int myints[]= {10,60,50,20};

  priority_queue<int, vector<int>, mycomparison(true)> first;

  return 0;
}

我感到困扰：

• 我必须在构造函数中指定存储类。
• 我创建了一个仅用于传递给优先级队列的类。

有没有更优雅或更简洁的方法来对优先级队列进行反向排序？

- Richard

---

我猜应该是 priority_queue<int, vector<int>, mycomparison> first(true); - Andy Prowl

我认为你在暗示这是一个与家庭作业相关的问题，@sftrabbit。不是这种情况。我已经使用std优先队列有一段时间了，它的使用方面一直让我感到困扰。我现在正在重构一些代码，并仔细研究比较类；它并不令我满意。 - Richard

我很好奇。反向排序优先队列的使用案例是什么？ - Martin James

@MartinJames，标准优先队列的行为是首先返回最大元素。因此，反向顺序将返回最小元素。（我为听众们陈述这一点，我相信你已经知道了。）在我的情况下，我正在模拟水位上升围绕地形岛屿。水应该首先淹没最低的土地，然后逐渐向更高的海拔移动。但它也在事件调度模拟中很有用，您可以通过跳转到未来的下一个最快事件来快速推进时间。这回答了你的问题吗？ - Richard

@Richard - 嘿，开发人员做一些奇怪的工作 :) - Martin James

Answer 1

你无法避免指定存储容器，但可以避免编写自己的函数对象：

priority_queue<int, vector<int>, std::greater<int> > first;

- juanchopanza

---

@Richard，我不确定我理解了。是谁的自定义类？什么自定义类？ - juanchopanza

这个问题涉及到 int 类型，但我的主要兴趣在于自定义类的优先队列。在这种情况下，您需要为自定义类定义比较器，然后直接使用您的代码即可。 - Richard

问题：priority_queue 中的排序是什么意思？'greater' 不是意味着最大的元素排在第一位吗？为什么 'lesser' 是默认值？ - Noein

@Noein 这是相反的。使用 std::greater<T> 意味着最小的元素在队列的顶部。请参阅 http://en.cppreference.com/w/cpp/container/priority_queue。 - juanchopanza

你不能避免多次指定存储容器，但是你可以定义一个别名模板，例如 namespace my { template<typename T, template<typename> class Comp = std::less> using priority_queue = std::priority_queue<T, std::vector<T>, Comp<T>>; }，并且使用 my::priority_queue<int, std::greater> 的方式。 - Caleth

Answer 2

如果您想要灵活性而不必定义任何类，您可以使用std::function>作为比较器的类型：

#include <functional>

int main ()
{
    int myints[]= {10,60,50,20};

    // Use this is a the type of your comparator
    typedef std::function<bool(int, int)> comp_type;

    // Priority queue using operator < for ordering
    priority_queue<int, vector<int>, comp_type> first(std::less<int>());

    // ...

    // Priority queue using operator > for ordering
    priority_queue<int, vector<int>, comp_type> second(std::greater<int>());

    // ...

    return 0;
}

- Andy Prowl

Answer 3

当我在反转一个结构体的优先队列时，我发现了更简单的解决方案。我从这里修改了解决方案：C++中带有结构体的STL优先队列

struct leaf
{
int symbol;
double probability;
bool operator < (const leaf &o) const 
    {
        return probability > o.probability; // here just reversed the operator
    }
};

priority_queue <leaf> leafs_queue; //queue already reversed

- Wojciech Siudy