C++ 实现具有不同优先级函数的优先级队列的最佳方法是什么？

Question

我看到的关于换出优先级队列比较器的公认答案是在新的比较器中使运算符过载 class。

class Foo
{

};

class Compare
{
public:
    bool operator() (Foo, Foo)
    {
        return true;
    }
};

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, Compare> pq;
    return 0;
}

但是，我想为队列实现几个（10+）个不同的比较函数，并在运行时间在 main() 中创建 pq 时选择一个。我必须进行 10 次不同的比较 class 还是有更简单的方法来做到这一点？

Answer 1

使用比较器模板参数的函数，将函数的实例传递给队列的构造函数，参见second constructor there。

对于类型，您可以使用 C++ 函数对象 std::function<bool(const Foo& a, const Foo& b)>，或 C 函数指针，即 bool(*)(const Foo& a, const Foo& b)。

Answer 2

Do I have to make 10 different compare classes or is there an easier way to do this?

你不必。 priority_queue 要求比较器采用 Foo 和 return bool - 默认为 std::less

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

在您的情况下，您可以使用 lambda 或用于该目的的函数指针。例如，

using cmp1 = bool(*)(const Foo&, const Foo&);
bool FooCmp1(const Foo& f1, const Foo& f2)
{
     // do real comparison..
     return true;
}

priority_queue<Foo, std::vector<Foo>, cmp1> pq(FooCmp1);

C++ 实现具有不同优先级函数的优先级队列的最佳方法是什么？

C++ What's the best way to implement a Priority Queue with varying priority functions?

c++

priority-queue