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

Je suis en train de déclarer un priority_queue of nodes, à l'aide de bool Compare(Node a, Node b) comme le comparateur de fonction (ce qui est en dehors de la classe de nœud).

Ce que j'ai actuellement est:

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

Pour une raison quelconque, je suis Error: "Compare" is not a type name

La modification de la déclaration de 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?

InformationsquelleAutor Steven Morad | 2013-04-19

c++priority-queue std

79

Vous devez déclarer une classe Compare et de la surcharge operator(), comme ceci:
```
class Foo
{

};

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

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, Compare> pq;
    return 0;
}
```
Ou, si pour certaines raisons, ne peuvent pas se rendre dans la classe, vous pouvez utiliser std::function pour elle:
```
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;
}
```
- Parfait, juste ce que je cherchais. Je n'ai jamais pensé à faire une classe à part. Serait le premier exemple être considéré comme meilleur style?
- Je préfère utiliser la classe avec surchargé operator(), il semble plus simple.
- Pourquoi faisons-nous la surcharge de l'opérateur () ? Est-ce lié à la façon dont priority_queues sont mis en œuvre à l'interne? la surcharge > ou < a de sens intuitivement, mais () exploitant n'est pas tellement
- la question est sur le passage d'un personnalisé comparaison pour la pritority_queue. Il est possible de surcharger operator< et de l'utilisation intégrée de std::less de comparaison, cependant, la bool Compare(Node a, Node b) déclarée en dehors de la classe Node, selon la question.
- Je ne suis pas d'accord avec la std::function solution. Voir ma réponse ci-dessous.
- la syntaxe de l'aide () est sur le passage d'une fonction comme paramètre à une autre fonction, non pas sur les opérateurs. Ceci est également connu comme un foncteur. Voir ce lien: en.wikipedia.org/wiki/Function_object
InformationsquelleAutor awesoon
14

Accepté la réponse vous fait croire que vous devez utiliser une classe ou un std::function comme comparateur. Ce n'est pas vrai! Comme cute_ptr réponse montre, vous pouvez passer un pointeur de fonction du constructeur. Toutefois, la syntaxe de le faire est beaucoup plus simple que de s'y manifeste:
```
class Node;
bool Compare(Node a, Node b);

priority_queue<Node, vector<Node>, decltype(&Compare)> openSet(Compare);
```
Qui est, il n'est pas nécessaire de coder explicitement la fonction de type de l', vous pouvez laisser le compilateur faire pour vous à l'aide de decltype.

C'est très utile si le comparateur est un lambda. Vous ne pouvez pas spécifier le type d'un lambda dans tout autre moyen que d'utiliser decltype. Par exemple:
```
auto compare = [](Node a, Node b) { return a.foo < b.foo; }
priority_queue<Node, vector<Node>, decltype(compare)> openSet(compare);
```
- C'est fantastique, je me demande s'il y a des pièges potentiels (questions) ici. J'adorerais voir cette réponse d'obtenir plus de visibilité et de discussion.
- J'utilise cette méthode régulièrement (en général Compare est un lambda, ce qui est impossible d'écrire une déclaration pour), je ne sais pas de tous les pièges. Si vous souhaitez donner cette réponse plus de visibilité, upvote il! 😉
- Déjà fait 🙂 Merci pour la réponse
- Si vous deviez le faire pour une fonction lambda, où placeriez-vous le corps de la fonction lambda? Voulez-vous le stocker dans une variable f à l'avance et ensuite remplacer Compare avec f?
- Oui, Compare peut être une fonction lambda là, comme dans les auto Compare = [](){};. Mais vous devez l'utiliser decltype(Compare), plutôt que de decltype(&Compare).
InformationsquelleAutor Cris Luengo
13

Le troisième paramètre de modèle doit être une classe qui a operator()(Node,Node) surchargé.
Ainsi, vous aurez à créer une classe de cette façon:
```
class ComparisonClass {
    bool operator() (Node, Node) {
        //comparison code here
    }
};
```
Et puis vous allez utiliser cette classe comme le troisième paramètre de modèle comme ceci:
```
priority_queue<Node, vector<Node>, ComparisonClass> q;
```
- L'opérateur méthode doit être public.
- Le troisième modèle n'a pas besoin d'être une classe. Il peut être le type d'une fonction.
InformationsquelleAutor Mic
5

Répondre directement à votre question:
Je suis en train 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 une Erreur:
```
"Compare" is not a type name
```
Le compilateur est vous dire exactement quel est le problème: Compare n'est pas un nom de type, mais une instance d'une fonction qui prend deux Nodes et renvoie un bool.

Ce que vous avez besoin est de préciser la fonction de pointeur de type:

std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

InformationsquelleAutor cute_ptr

On peut également utiliser une fonction lambda.

auto Compare = [](Node &a, Node &b) { //compare };
std::priority_queue<Node, std::vector<Node>, decltype(Compare)> openset(Compare);

InformationsquelleAutor bornfree

Vous devez vous connecter pour publier un commentaire.