使用自制的 std::Compare 初始化 std::priority_queue 时避免使用模板？

Question

是否可以去掉下面代码中的模板？

想法是使用 std::priority_queue 和 classes 通过自制摘要 class 来纪念 Compare 概念。我遇到的一些问题是：

优先级队列不会用抽象比较初始化。
从 Compare 继承的 classes 没有默认构造函数，因为它们都有特定的参数。
一个Algorithm负责初始化Compare个实例使用的数据结构。
编辑： 可能存在 Algorithm 的多个实现，使用不同的数据结构需要 Compare，[=57= 的用户] 应该能够决定他想使用哪个比较。

我不喜欢下面给出的设计，因为实现 Algorithm 的人并没有真正被迫调用 Compare::attach，因此 Compare class 应该有一个状态管理（不是显示在这里）。

它还强制用户指定一个比较模板并传递相应的实例（因为编译器无法在 Algorithm 的构造函数中推断它）。 make_algo 函数可以缓解这种情况，但我宁愿避免这种奇特的构造（不是那个奇特的，但仍然如此）。

有没有一种设计可以让我在 Algorithm 中使用 Compare 摘要 class 而不是模板？

#include <vector>
#include <queue>

class Compare
{
private:
    std::vector<int>* _costs;
protected:
    std::vector<int>& costs() {return *_costs;}
    int cost(const int i) const {return (*_costs)[i];}
public:
    Compare() : _costs(nullptr) {}
    void attach(std::vector<int> & costs_) {_costs = &costs_;}
    virtual bool operator()( const int a, const int b ) const = 0;
};

struct CompCosts : public Compare
{
    virtual bool operator()( const int a, const int b ) const
    {
        return this->cost(a) < this->cost(b);
    }
};

struct CompEps : public Compare
{
    const int eps;
    CompEps(const int e) : Compare(), eps(e) {}
    virtual bool operator()( const int a, const int b ) const
    {
        return this->cost(a)-eps < this->cost(b)+eps;
    }
};


template<typename C>
struct Algorithm
{
    C & comp;
    Algorithm(C& comp_) : comp(comp_) {}
    virtual void operator()() const = 0;
};

template<typename C>
struct Algo : public Algorithm<C>
{
    Algo(C & comp_) : Algorithm<C>(comp_) {}
    virtual void operator()() const
    {
        std::vector<int> costs;
        this->comp.attach(costs);
        std::priority_queue<int, std::vector<int>, C > queue(this->comp);
    }
};

template<typename C>
Algo<C> make_algo(C& comp)
{
    return Algo<C>(comp);
}


int main()
{
    CompCosts compc;
    Algo<CompCosts> algo0(compc);
    auto algo1 = make_algo(compc);

    CompEps compe(1);
    Algo<CompEps> algo2(compe);
    auto algo3 = make_algo(compe);
}

EDIT2：由于Barry提出的解决方案可能不是很明显，这里是相应的代码：

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <cassert>

struct Compare
{
    virtual bool operator()( const int a, const int b, const std::vector<int>& costs ) const =0;
};

struct CompCosts : public Compare
{
    virtual bool operator()( const int a, const int b, const std::vector<int>& costs ) const
    {
        return costs[a] < costs[b];
    }
};

struct CompEps : public Compare
{
    const int eps;
    CompEps(const int e) : Compare(), eps(e) {}
    virtual bool operator()( const int a, const int b, const std::vector<int>& costs ) const
    {
        return costs[a]-eps < costs[b]+eps;
    }
};


struct Algorithm
{
    std::function<bool(const int, const int, const std::vector<int>& costs )> comp;

    Algorithm(
            std::function<
                bool(const int, const int, const std::vector<int>& costs )
            > comp_
        ) : comp(comp_) {}
    virtual void operator()() const = 0;
};

struct Algo : public Algorithm
{
    Algo(std::function<bool(const int, const int, const std::vector<int>& costs )> comp_) : Algorithm(comp_) {}
    virtual void operator()() const
    {
        std::vector<int> costs{3,2,1};

        using namespace std::placeholders;
        std::function<bool(const int, const int)> f = std::bind(comp, _1, _2, std::cref(costs));

        std::priority_queue<int, std::vector<int>, std::function<bool(const int, const int )> > queue(f);
    }
};


int main()
{
    CompCosts compc;
    Algo algo0(compc);
    algo0();

    CompEps compe(0);
    Algo algo2(compe);
    algo2();
}

Answer 1

由于 priority_queue 持有 Compare 类型的对象，因此任何多态性尝试都会导致切片并失败。但是无论如何，多态性确实是对问题的过度思考（就像我在之前的修订版中所做的那样）。

只需使用类型擦除。您所有的比较器都会有一个 bool operator()(int, int)，例如：

struct CompCosts
{
    std::vector<int> const& costs;

    bool compare(int lhs, int rhs) const
    {
        return costs[lhs] < costs[rhs];
    }
};

所以他们都可以被std::function<bool(int, int)>处理:

using Q = std::priority_queue<int, std::vector<int>, std::function<bool(int, int)>>;

然后只需使用您想使用的比较器创建 Q：

Q queue_by_cost(CompCosts{costs});
Q queue_by_eps(CompEps{costs});

使用自制的 std::Compare 初始化 std::priority_queue 时避免使用模板？

Avoid template when initializing `std::priority_queue` with home-made `std::Compare`?

c++

templates

compare

priority-queue