Avoid template when initializing `std::priority_queue` with home-made `std::Compare`?
<p>Is it possible to get rid of the template in the following code?</p>

<p>The idea is to use a <code>std::priority_queue</code> with classes honouring the <code>Compare</code> concept via an home-made abstract class.
Some of the problems I faced are: </p>

<ul>
<li>The priority queue wont init with an abstract Compare.</li>
<li>there is no default constructors for classes inheriting from <code>Compare</code>, because they all have specific parameters.</li>
<li>an <code>Algorithm</code> is responsible for initializing the data structure used by the <code>Compare</code> instances.</li>
<li><strong>EDIT:</strong> there may exists several implementations of <code>Algorithm</code>, using different data structures needing a <code>Compare</code>, and the user of the class should be able to decide which Compare he want to use.</li>
</ul>

<p>I dislike the design given hereafter because people implementing <code>Algorithm</code> are not really forced to call <code>Compare::attach</code> and the <code>Compare</code> class should thus have a state management (not shown here).</p>

<p>It also force the user to indicate a compare template AND pass the corresponding instance (because the compiler cannot infer it in the constructor of an <code>Algorithm</code>). This is mitigated by the <code>make_algo</code> function, but I would rather avoid this exotic construction (not <em>that</em> exotic, but still).</p>

<p><strong>Is there a design in which I can use the <code>Compare</code> abstract class in an <code>Algorithm</code> instead of a template?</strong></p>

<pre class="lang-cpp prettyprint-override"><code>#include &lt;vector&gt;
#include &lt;queue&gt;

class Compare
{
private:
    std::vector&lt;int&gt;* _costs;
protected:
    std::vector&lt;int&gt;&amp; costs() {return *_costs;}
    int cost(const int i) const {return (*_costs)[i];}
public:
    Compare() : _costs(nullptr) {}
    void attach(std::vector&lt;int&gt; &amp; costs_) {_costs = &amp;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-&gt;cost(a) &lt; this-&gt;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-&gt;cost(a)-eps &lt; this-&gt;cost(b)+eps;
    }
};


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

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

template&lt;typename C&gt;
Algo&lt;C&gt; make_algo(C&amp; comp)
{
    return Algo&lt;C&gt;(comp);
}


int main()
{
    CompCosts compc;
    Algo&lt;CompCosts&gt; algo0(compc);
    auto algo1 = make_algo(compc);

    CompEps compe(1);
    Algo&lt;CompEps&gt; algo2(compe);
    auto algo3 = make_algo(compe);
}
</code></pre>

<p><strong>EDIT2: as the solution proposed by Barry may not be obvious to everybody, here is the corresponding code</strong>:</p>

<pre><code>#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;queue&gt;
#include &lt;functional&gt;
#include &lt;cassert&gt;

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

struct CompCosts : public Compare
{
    virtual bool operator()( const int a, const int b, const std::vector&lt;int&gt;&amp; costs ) const
    {
        return costs[a] &lt; 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&lt;int&gt;&amp; costs ) const
    {
        return costs[a]-eps &lt; costs[b]+eps;
    }
};


struct Algorithm
{
    std::function&lt;bool(const int, const int, const std::vector&lt;int&gt;&amp; costs )&gt; comp;

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

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

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

        std::priority_queue&lt;int, std::vector&lt;int&gt;, std::function&lt;bool(const int, const int )&gt; &gt; queue(f);
    }
};


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

    CompEps compe(0);
    Algo algo2(compe);
    algo2();
}
</code></pre>