geeksforgeeks - declarando una prioridad_cinta en c++ con un comparador personalizado

priority queue default order c++

Question

Estoy tratando de declarar una priority_queue of nodes , utilizando bool Compare(Node a, Node b) como la función de comparación (que está fuera de la clase de nodo).

Lo que tengo actualmente es:

priority_queue<Node, vector<Node>, Compare> openSet;

Por alguna razón, recibo un Error: "Compare" is not a type name

Cambio de la declaración a priority_queue <Node, vector<Node>, bool Compare>

me da Error: expected a ''>''

También he intentado:

priority_queue<Node, vector<Node>, Compare()> openSet;
priority_queue<Node, vector<Node>, bool Compare()> openSet;
priority_queue<Node, vector<Node>, Compare<Node, Node>> openSet; 

¿Cómo debo declarar correctamente mi priority_queue ?

Answer 1

Debe declarar un operator() Compare y sobrecarga de clase operator() para esto de la siguiente manera:

class Foo
{

};

class Compare
{
public:
    bool operator() (Foo, Foo)
    {
        return true;
    }
};

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, Compare> pq;
    return 0;
}

O, si por alguna razón no puedes hacerlo como clase, podrías usar std::function para ello:

class Foo
{

};

bool Compare(Foo, Foo)
{
    return true;
}

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, std::function<bool(Foo, Foo)>> pq(Compare);
    return 0;
}

Answer 2

El tercer parámetro de la plantilla debe ser una clase que tenga el operator()(Node,Node) sobrecargado. Así que tendrás que crear una clase de esta manera:

class ComparisonClass {
    bool operator() (Node, Node) {
        //comparison code here
    }
};

Y luego usarás esta clase como el tercer parámetro de la plantilla como este:

priority_queue<Node, vector<Node>, ComparisonClass> q;

Answer 3

La respuesta aceptada le hace creer que debe usar una clase o una std::function como comparador. ¡Esto no es verdad! La respuesta de cute_ptr mostró cómo pasar una función al constructor, pero hay una forma más simple:

priority_queue<Node, vector<Node>, decltype(&Compare)> openSet(Compare);

Es decir, no es necesario codificar explícitamente el tipo de función, puede dejar que el compilador haga eso por usted.

Answer 4

Respondiendo su pregunta directamente:

Estoy tratando de declarar una priority_queue de cola de nodos, utilizando bool Compare(Node a, Node b) as the comparator function

Lo que tengo actualmente es:

priority_queue<Node, vector<Node>, Compare> openSet;

Por alguna razón, estoy recibiendo error:

"Compare" is not a type name

El compilador le está diciendo exactamente lo que está mal: Compare no es un nombre de tipo, sino una instancia de una función que toma dos Nodes y devuelve un valor bool .
Lo que necesitas es especificar el tipo de puntero de función:
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)