配对优先级队列

Question

我正在尝试将对存储在优先级队列中,并且我使用比较函数来比较每对的第二个值.

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

class CompareDist
{
public:
    bool operator()(pair<int,int> n1,pair<int,int> n2) {
        return n1.second>n2.second;
    }
};
int main()
{
    priority_queue<pair<int,int>,CompareDist> pq;
}

当我编译这个时,我得到一个错误

error: no type named ‘value_type’ in ‘class CompareDist’

可能是什么原因.我是STL的新手.

Answer 1

这就是priority_queue的样子:

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

换句话说,CompareDist应该是第三个参数,第二个参数应该是容器(有value_type),如下所示:

priority_queue<pair<int,int>,vector<pair<int,int>>,CompareDist> pq;

另请注意,这priority_queue就是所谓的"容器适配器".另一个容器用作底层容器,priority_queue具有用于访问它的特殊成员函数.容器适配器的另一个例子是std :: stack.