declarar una cola de prioridad en c++ con un comparador personalizado

Question

declarar una cola de prioridad en c++ con un comparador personalizado

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

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

Cambiar 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?

48

c++std priority-queue

Author: Steven Morad, 2013-04-19

Source

4 answers

El tercer parámetro de plantilla debe ser una clase que tiene 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 así:

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

9

Author: Mic,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-04-19 18:46:18

Respondiendo a su pregunta directamente:

Estoy tratando de declarar un priority_queue de nodos, usando 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 un 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 bool.
Lo que necesita es especificar el tipo de puntero de función:
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

3

Author: cute_ptr,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-11-13 11:27:16

La respuesta aceptada te hace creer que debes usar una clase o a 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 hay necesidad de codificar explícitamente el tipo de la función, puede dejar que el compilador lo haga por usted.

2

Author: Cris Luengo,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-02-05 20:56:27

score 58 · Accepted Answer

Debes declarar una clase Compare y sobrecargarla operator() para ello 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;
}