Wie Implementieren Methode Sortierung für ein C++ priority_queue mit Zeigern

Question

Meine Priorität Warteschlange erklärt wie:

std::priority_queue<*MyClass> queue; 

class MyClass { 
    bool operator<(const MyClass* m) const; 
} 

nicht, um die Elemente in der Warteschlange zu sortieren.

Was ist los? Ich würde nicht gerne eine andere (Compare) Klasse implementieren.

Antwort Zusammenfassung:

Das Problem ist, werden die Zeiger Adressen sortiert. Der einzige Weg, dies zu vermeiden, ist eine Klasse, die die Zeiger vergleicht.

std::priority_queue<*MyClass, vector<*MyClass>, MyClass::CompStr > queue; 

class MyClass { 
    struct CompStr { 
     bool operator()(MyClass* m1, MyClass* m2); 
    } 
} 

Answer 1

Geben Sie die Que den Vergleich functor ptr_less.

Wenn Sie wollen, dass die ptr_less mit dem Rest der std-Bibliothek (Bindemittel, Komponisten, ...) kompatibel zu sein:

template<class T> 
struct ptr_less 
    : public binary_function<T, T, bool> { 
     bool operator()(const T& left, const T& right) const{ 
      return ((*left) <(*right)); 
     } 
}; 

std::priority_queue<MyClass*, vector<MyClass*>, ptr_less<MyClass*> > que; 

Ansonsten können Sie mit der vereinfachten Version wegkommen:

struct ptr_less { 
    template<class T> 
    bool operator()(const T& left, const T& right) const { 
     return ((*left) <(*right)); 
    } 
}; 

std::priority_queue<MyClass*, vector<MyClass*>, ptr_less > que; 

Answer 2

Der Betreiber <() Sie bietet ein MyClass-Objekt mit einem Zeiger auf ein MyClass Objekt vergleichen hast:

nun als umgesetzt. Aber deine Warteschlange enthält nur Zeiger (glaube ich). Sie benötigen eine Vergleichsfunktion, die zwei Zeiger als Parameter akzeptiert.

All dies basiert auf einigen Annahmen - bitte posten Sie Ihren tatsächlichen Code, kopieren und einfügen.

Answer 3

Da Ihre priority_queue nur Zeigerwerte enthält, verwendet sie den Standardvergleichsoperator für die Zeiger - dies sortiert sie nach Adresse, die offensichtlich nicht das ist, was Sie wollen. Wenn Sie priority_queue ändern, um die Klasseninstanzen nach Wert zu speichern, wird der von Ihnen definierte Operator verwendet. Oder Sie müssen eine Vergleichsfunktion bereitstellen.

Answer 4

nicht über die Prioritätswarteschlange Sachen sicher, weil ich nie, aber es benutzt habe eine gerade Art zu tun, können Sie dies tun:

class A 
{ 
    friend struct ComparePtrToA; 
public: 
    A(int v=0):a(v){} 
private: 
    int a; 
}; 

struct ComparePtrToA 
{ 
    bool operator()(A* a1, A* a2) {return a1->a < a2->a;} 
}; 

#include <vector> 
#include <algorithm> 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    vector<A*> someAs; 
    someAs.push_back(new A(1)); 
    someAs.push_back(new A(3)); 
    someAs.push_back(new A(2)); 
    sort(someAs.begin(), someAs.end(), ComparePtrToA()); 
} 

Beachten Sie die Speicherlecks, dies ist nur ein Beispiel ...

Weiterer Hinweis: Dies ist keine Implementierung der Prioritätswarteschlange! Der Vektor ist nur ein Beispiel für die Verwendung des Funktors, den ich erstellt habe, um zwei Objekte über ihre Zeiger zu vergleichen. Obwohl mir bewusst ist, was eine Prioritätswarteschlange ist und wie sie funktioniert, habe ich nie die STL-Funktionen verwendet, die sie implementieren.

Update: Ich denke TimW macht einige gültige Punkte. Ich weiß nicht, warum er so oft abgelehnt wurde. Ich denke, meine Antwort verbessert werden kann wie folgt:

class A 
{ 
public: 
    A(int v=0):a(v){} 
    bool operator<(const A& rhs) { return a < rhs.a; } 
private: 
    int a; 
}; 

struct ComparePtrToA 
{ 
    bool operator()(A* a1, A* a2) {return *a1 < *a2;} 
}; 

, die sauberer ist (vor allem, wenn Sie einen Container von Werten berücksichtigen zu müssen, anstatt Zeigern - keine weiteren Arbeiten erforderlich wären).