c++这样创建优先队列中的第三个参数decltype(&cmp)是什么意思？

Question

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);

cmp是如下自定义的一个函数，是为了按照pair中的第二关键字降序排列

static bool cmp(pair<int, int>& m, pair<int, int>& n) {
    return m.second > n.second;
}

还有为什么q后面还要加上一个(cmp)

我在网上搜索的创建优先队列都是下面这样子，但没说第三个参数是自定义函数的时候该怎么写

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

Answer 1

请看优先级队列的定义：

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

 

std::priority_queue 是一个模板类，有三个模板类型参数，分别是：

1. 参数1: 优先级队列的元素类型 T ，例如问题里第一个例子，元素类型 T 是 std::pair<int,int> ，后面两个例子，元素类型 T 是 int
2. 参数2: 优先级队列内部具体用那种容器(Container) 存储参数1指定的元素类型，例如问题里的 vector< pair<int,int> > 和 vector<int>。实际上，第2个模板参数是有默认类型参数的，默认类型参数是 vector<T> ，T 取决于参数1指定的类型是什么。
3. 参数3: 参数3需要指定一个实现了 operator< 操作符的类（叫做仿函数或者函数对象，实际上就是类，只是调用时写起来像函数一样），比较操作符的实现符合 严格弱顺序 strict weak order  语义，请参考资料3。模板参数3也是有默认类型，默认是 std::less<typename Container::value_type> ，其中 Container 指的是参数2，Container::value_type 指的是参数2类内部的声明的其元素值的类型。
4. 最后，decltype 用于类型自动推断，传入&cmp函数指针，decltype自动推断出第3个模版参数类型应该是什么。总的来说，如果你的元素类型已经符合严格弱顺序排序，只要自定优先级队列的第1个模版参数即可。

 

参考：

1. std::priority_queue https://en.cppreference.com/w/cpp/container/priority_queue
2. std::less  https://en.cppreference.com/w/cpp/utility/functional/less
3. strict weak order https://en.cppreference.com/w/cpp/concepts/strict_weak_order
4. decltype https://en.cppreference.com/w/cpp/language/decltype