Question de modèle C++ concernant les comparateurs

Question

Probablement une question C++ très récente. Dites que j'ai une classe, vertex, avec plusieurs propriétés et méthodes. Je veux placer une série de vertices dans une file d'attente, et les faire trier par une propriété spéciale sur la classe de vertex (faire un algo graphique de Dijkstra de base pour l'école oui).

J'ai cependant quelques problèmes pour pénétrer la syntaxe C++. Voici mon code (le vertex n'est pas montré, mais c'est assez simple).

typedef std::priority_queue<benchmark::vertex*, 
        std::vector<benchmark::vertex*>, 
        std::less<benchmark::vertex*> > q_type; 
q_type* q = new q_type(); 
benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1); 
v1->cost = 4; 
benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1); 
v2->cost = 8; 
benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1); 
v3->cost = 6; 
benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1); 
v4->cost = 10; 
benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1); 
v5->cost = 2; 
q->push(v1); 
q->push(v2); 
q->push(v3); 
q->push(v4); 
q->push(v5); 
while (!q->empty()) { 
    std::cout << (*(q->top())).cost << std::endl; 
    q->pop(); 
} 

Ceci produit 2, 10, 6, 8, 4 sur ma machine locale. Je suis en train de tester ceci sur une machine Linux avec GCC (version 4.3.3 de gcc (Ubuntu 4.3.3-5ubuntu4)). Évidemment, je veux qu'il crache les chiffres dans l'ordre.

Comment est-ce que je fais le comparateur, de sorte qu'il regarde et compare vertex.cost, en faisant des comparaisons?

Answer 1

remplacez std::less<benchmark::vertex*> par une fonction ou un foncteur qui prend deux pointeurs de sommets comme paramètres et renvoie true si le premier paramètre appartient avant le second.

std::less<benchmark::vertex*> va comparer les deux pointeurs, de sorte que le résultat que vous avez vu montre leur ordre en mémoire.

Answer 2

std::less<benchmark::vertex*> compare les adresses plutôt que les sommets

// Functor 
struct VertexLess 
{ 
    bool operator (const benchmark::vertex* left, const benchmark::vertex* right) const { 
     return left->id < right->id; 
    } 
}; 

typedef std::priority_queue<benchmark::vertex*,  
        std::vector<benchmark::vertex*>, 
        VertexLess > q_type; 

Answer 3

Bonus version extra-templatey de la réponse de Alexey Malistov:

template <class T, class M, const M T::*member> 
struct MemberGenericDereferenceLess 
{ 
    bool operator()(const T* lhs, const T* rhs) const 
    { 
     return ((*lhs).*member < (*rhs).*member); 
    } 
}; 

typedef std::priority_queue<benchmark::vertex*, 
          std::vector<benchmark::vertex*>, 
          MemberGenericDereferenceLess<benchmark::vertex, 
                 int, 
                 &benchmark::vertex::cost> > q_type; 

j'avais pensé que vous auriez seulement besoin des premier et troisième paramètres de modèle , mais je ne pouvais pas l'obtenir pour inférer class M avec quelques minutes de piratage. (exercice pour les lecteurs)

L'avantage de ceci est que vous pouvez rapidement changer le membre sur lequel vous triez. En supposant que votre vertex ressemble à quelque chose comme ...

namespace benchmark 
{ 
    struct vertex 
    { 
     vertex(double a_, double b_) : a(a_), b(b_) {} 

     double a; 
     double b; 

     int cost; 
    }; 
} 

Vous pourriez avoir votre typedef tri sur a ou b:

typedef std::priority_queue<benchmark::vertex*, 
          std::vector<benchmark::vertex*>, 
          MemberGenericDereferenceLess<benchmark::vertex, 
                double, 
                &benchmark::vertex::a> > q_type; 

typedef std::priority_queue<benchmark::vertex*, 
          std::vector<benchmark::vertex*>, 
          MemberGenericDereferenceLess<benchmark::vertex, 
                double, 
                &benchmark::vertex::b> > q_type; 

Voici un petit programme pilote pour jouer avec:

#include <iostream> 
#include <queue> 
#include <vector> 

namespace benchmark 
{ 
    struct vertex 
    { 
     vertex(double a_, double b_) : a(a_), b(b_) {} 

     double a; 
     double b; 

     int cost; 
    }; 
} 

template <class T, class M, const M T::*member> 
struct MemberGenericDereferenceLess 
{ 
    bool operator()(const T* lhs, const T* rhs) const 
    { 
     return ((*lhs).*member < (*rhs).*member); 
    } 
}; 

int main(int argc, char** argv) 
{ 
    typedef std::priority_queue<benchmark::vertex*, 
           std::vector<benchmark::vertex*>, 
           MemberGenericDereferenceLess<benchmark::vertex, 
                 int, 
                 &benchmark::vertex::cost> > q_type; 
    q_type q; 

    benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1); 
    v1->cost = 4; 
    benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1); 
    v2->cost = 8; 
    benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1); 
    v3->cost = 6; 
    benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1); 
    v4->cost = 10; 
    benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1); 
    v5->cost = 2; 
    q.push(v1); 
    q.push(v2); 
    q.push(v3); 
    q.push(v4); 
    q.push(v5); 
    while(q.empty() == false) 
    { 
     std::cout << q.top()->cost << std::endl; 
     q.pop(); 
    } 

    // Clean up all of those new()s 
    delete v1; 
    delete v2; 
    delete v3; 
    delete v4; 
    delete v5; 

    std::cin.get(); 

    return 0; 
}