Vermeiden Sie Vorlage bei der Initialisierung von `std :: priority_queue` mit hausgemachten` std :: Compare`?

Question

Ist es möglich, die Vorlage im folgenden Code loszuwerden?

Die Idee ist, eine std::priority_queue mit Klassen zu verwenden, die das Compare Konzept über eine selbst gemachte abstrakte Klasse ehren. Einige der Probleme, denen ich gegenüberstand, sind:

• Die Prioritätswarteschlange wird mit einem abstrakten Vergleich nicht init.
• gibt es keine Standardkonstruktoren für Klassen, die von Compare erben, weil sie alle spezifische Parameter haben.
• ein Algorithm ist verantwortlich für die Initialisierung der Datenstruktur von den Compare Instanzen verwendet.
• EDIT: gibt es kann mehrere Implementierungen von Algorithm, unterschiedliche Datenstrukturen mit einem Compare benötigen, und der Benutzer der Klasse sollte in der Lage sein zu entscheiden, welche Vergleichen er verwendet werden soll.

Ich mag nicht das Jenseits gegeben Design, weil die Menschen Algorithm Umsetzung sind nicht wirklich Compare::attach zu nennen gezwungen und die Compare Klasse sollte also einen Zustand Management haben (hier nicht gezeigt).

Es zwingt den Benutzer auch, eine Vergleichsvorlage anzugeben UND die entsprechende Instanz übergeben (weil der Compiler kann nicht im Konstruktor einer Algorithm davon abgeleitet werden). Dies wird durch die make_algo Funktion gemildert, aber ich würde eher vermeiden, diese exotische Konstruktion (nicht dass exotisch, aber immer noch).

Gibt es ein Design, in dem ich die Compare abstrakte Klasse in einer Algorithm anstelle einer Vorlage verwenden kann?

#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: als die Lösung von Barry vorgeschlagen nicht jedem offensichtlich sein mag, hier ist der entsprechende Code:

#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

Da priority_queue auf ein Objekt vom Typ hält Compare, jeder Versuch, Beim Polymorphismus würde es zum Schneiden und Scheitern führen. Aber der Polymorphismus überschreibt das Problem sowieso (wie in der vorherigen Version).

Verwenden Sie einfach Typ löschen. Alle Ihre Komparatoren eine bool operator()(int, int) haben, wie:

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

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

So können sie alle von std::function<bool(int, int)> behandelt werden:

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

Und dann erstellen Sie einfach Ihre Q mit je nachdem, welcher Komparator Sie verwenden möchten:

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