使用模板和优先队列的函数

Question

我正在尝试使用 Fibonacci 堆和优先级队列编写 Dijkstra 算法。所以我有一个斐波那契堆 class（结构）

template<class T>
struct Fib {
    ...
};

和一个函数

template <template <class> class T>
void dijkstra(...) {
    T<std::pair<double, int> > heap;
    ...
}

问题是：

dijkstra<Fib>(...);                 // OK
dijkstra<std::priority_queue>(...); // doesn't compile

为什么编译不通过，我该如何正确编写？

Answer 1

当您编写如下参数时：

template<class> class T

需要一个带有单个模板参数的 class 模板。 Fib就是这样一个class的模板，就需要T。但是，std::priority_queue 不采用单个模板参数。它需要三个，即使默认为两个：

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

如果您使用的是 C++11，您可以简单地增强 dijkstra 以采用任意 class 模板：

template<template<class...> class T>
//                     ^^^
void dijkstra(...) {

或者为std::priority_queue写一个单模板参数别名：

template <class T>
using vector_less_pq = std::priority_queue<T>;

Function with template and Priority Queue