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

Question

The accepted answer I've seen for swapping out a priority queue comparator is to overload the operator in a new compare 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;
}

However, I want to implement several (10+) different compare functions for queue and choose one at run time when pq is created in main(). Do I have to make 10 different compare classes or is there an easier way to do this?

No need for classes at all. You can define compare functions (`bool compareN (const &Foo, const &Foo) { ... }`) or use [lambda expressions](https://en.cppreference.com/w/cpp/language/lambda). — user4581301, Sep 17 '20 at 05:23
What is the scope of these compare functions? Can I put them in Foo itself? — knowads, Sep 17 '20 at 05:28
@knowads You pass it when constructing the queue, the queue copies the comparer and never changes it. Can't store in the items. — Soonts, Sep 17 '20 at 05:32
You could put the functions in `Foo`, but it's recommended that you don't. If a function can be a [free function](https://stackoverflow.com/questions/4861914/what-is-the-meaning-of-the-term-free-function-in-c), let it be free. This generally improves reuse. [See a more complete explanation in the C++ Core Guidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rc-member) — user4581301, Sep 17 '20 at 05:33
You need to implement a container adaptor just like `std::priority_queue`, but which reorders the wrapped container if the ordering function changes. — Some programmer dude, Sep 17 '20 at 05:40
If you have one queue and you set the ordering at construction, you'll want a factory function, or similar, because in `if (case) {std::priority_queue, Compare> pq(cmpfunc1); }` `pq` will go out of scope at the end of the `if`'s body. — user4581301, Sep 17 '20 at 05:51

score 2 · Accepted Answer · edited Sep 17 '20 at 05:47

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

You don't have to. The priority_queue requires that the comparator taking a Foo and return bool - with the default one is std::less

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

In your case, you may use a lambda, or a pointer to function for that purpose. For example,

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);

score 1 · Answer 2 · answered Sep 17 '20 at 05:30

Use a function for comparer template argument, pass the instance of the function to the constructor of the queue, see second constructor there.

For the type, you can use C++ function object std::function<bool(const Foo& a, const Foo& b)>, or C function pointer i.e. bool(*)(const Foo& a, const Foo& b).

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

2 Answers2