C le tas de min avec un type défini par l'utilisateur

Question

Je suis en train de mettre en œuvre un tas min en c ++ pour un type struct que j'ai créé. J'ai créé un vecteur de type, mais il plantait quand je make_heap sur elle, ce qui est compréhensible, car il ne sait pas comment comparer les articles dans le tas. Comment puis-je créer un tas min (c'est l'élément supérieur est toujours le plus petit dans le tas) pour un type struct?

Le struct est ci-dessous:

struct DOC{

int docid;
double rank;

};

Je veux comparer les structures DOC utilisant l'élément de rang. Comment puis-je faire?

J'ai essayé d'utiliser une file d'attente prioritaire avec une classe de comparaison, mais aussi crashé, et il semble aussi stupide d'utiliser une structure de données qui utilise un tas comme base sous-jacente quand ce que je vraiment besoin est un tas de toute façon.

Merci beaucoup, BSG

Answer 1

Ajouter un opérateur de comparaison:

struct DOC{

    int docid;
    double rank;
    bool operator<( const DOC & d ) const {
       return rank < d.rank;
    }
};

Les structures peuvent presque toujours utile d'avoir un constructeur, donc j'ajouter:

DOC( int i, double r ) : docid(i), rank(r) {]

à la struct ainsi.

Answer 2

Il suffit de créer votre propre « foncteur » pour la comparaison. Puisque vous voulez un « tas min » votre fonction de comparaison doit se comporter comme supérieure à l'opérateur:

#include <iostream>
#include <vector>
#include <algorithm>

struct doc {
    double rank;
    explicit doc(double r) : rank(r) {}
};

struct doc_rank_greater_than {
    bool operator()(doc const& a, doc const& b) const {
        return a.rank > b.rank;
    }
};

int main() {
    std::vector<doc> docvec;
    docvec.push_back( doc(4) );
    docvec.push_back( doc(3) );
    docvec.push_back( doc(2) );
    docvec.push_back( doc(1) );
    std::make_heap(docvec.begin(),docvec.end(),doc_rank_greater_than());
    std::cout << docvec.front().rank << '\n';
}

Il est important que vous utilisez toujours la même fonction de comparaison dans d'autres opérations tas.