déclaration d'une priority_queue en c++ avec un comparateur personnalisé

Question

J'essaie de déclarer un priority_queue of nodes en utilisant bool Compare(Node a, Node b) comme fonction de comparaison (qui est en dehors de la classe des nœuds).

Ce que j'ai actuellement est :

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

Pour une raison quelconque, je reçois Error: "Compare" is not a type name

En changeant la déclaration en priority_queue <Node, vector<Node>, bool Compare>

me donne Error: expected a '>'

J'ai aussi essayé :

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

Comment dois-je déclarer correctement mon priority_queue ?

Answer 1

Note - Vous pouvez également vérifier d'autres réponses, en particulier celle qui concerne le decltype et le lambda.

---

Vous devez déclarer une classe Compare et la surcharge operator() pour le faire comme ça :

class Foo
{

};

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

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

Si, pour une raison ou une autre, vous ne pouvez pas assister au cours, vous pourriez utiliser std::function pour cela :

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

La réponse acceptée montre comment utiliser une classe ou une std::function comme comparateur. On peut aussi passer un pointeur de fonction, comme La réponse de cute_ptr a déjà montré. Cependant, la syntaxe pour le faire est beaucoup plus simple que ce qui a été montré :

class Node;
bool Compare(Node a, Node b);

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

En d'autres termes, il n'est pas nécessaire d'encoder explicitement le type de la fonction, vous pouvez laisser le compilateur le faire pour vous en utilisant la commande decltype .

Ceci est très utile si le comparateur est un lambda. Vous ne pouvez pas spécifier le type d'un lambda autrement qu'en utilisant la fonction decltype . Par exemple :

auto compare = [](Node a, Node b) { return a.foo < b.foo; }
std::priority_queue<Node, std::vector<Node>, decltype(compare)> openSet(compare);

Answer 3

Le troisième paramètre de modèle doit être une classe qui a operator()(Node,Node) surchargés. Vous devrez donc créer une classe de cette façon :

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

Et ensuite vous utiliserez cette classe comme troisième paramètre du modèle comme ceci :

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

Answer 4

Je réponds directement à votre question :

J'essaie de déclarer un priority_queue de nœuds, en utilisant bool Compare(Node a, Node b) as the comparator function

Ce que j'ai actuellement est :

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

Pour une raison quelconque, j'obtiens Error :

"Compare" is not a type name

Le compilateur vous dit exactement ce qui ne va pas : Compare n'est pas un nom de type, mais une instance d'une fonction qui prend deux Nodes et renvoie un bool .
Ce dont vous avez besoin, c'est de spécifier le type de pointeur de fonction :
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

Answer 5

Vous devez d'abord définir la comparaison. Il y a trois façons de le faire :

1. utiliser la classe
2. utiliser struct (qui est identique à class)
3. utiliser la fonction lambda.

Il est facile d'utiliser les classes/structures car elles sont faciles à déclarer. Il suffit d'écrire cette ligne de code au-dessus de votre code en cours d'exécution.

struct compare{
  public:
  bool operator()(Node& a,Node& b) // overloading both operators 
  {
      return a.w < b.w: // if you want increasing order;(i.e increasing for minPQ)
      return a.w > b.w // if you want reverse of default order;(i.e decreasing for minPQ)
   }
};

Code d'appel :

priority_queue<Node,vector<Node>,compare> pq;