C ++ min montón con tipo definido por el usuario

Question

Estoy tratando de poner en práctica un montón min en C ++ para un tipo de estructura que creé. He creado un vector del tipo, pero se estrelló cuando utilicé make_heap en él, lo cual es comprensible, ya que no sabe cómo comparar los elementos de la pila. ¿Cómo se crea un montón min-(es decir, el elemento superior es siempre el más pequeño en el montón) para un tipo de estructura?

El struct es a continuación:

struct DOC{

int docid;
double rank;

};

Quiero comparar las estructuras DOC utilizando el miembro de rango. ¿Cómo puedo hacer esto?

He intentado utilizar una cola de prioridad con una clase de comparación, sino que también se estrelló, y también parece tonto para usar una estructura de datos que utiliza un montón como base subyacente cuando lo que realmente necesita es un montón de todos modos.

Muchas gracias, bsg

Answer 1

Añadir un operador de comparación:

struct DOC{

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

Las estructuras pueden casi siempre útil tener un constructor, así que también añadiría:

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

a la struct también.

Answer 2

Simplemente crear su propia "funtor" para la comparación. Puesto que usted quiere un "min heap" su función de comparación debe comportarse como el operador mayor que:

#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';
}

Es importante que utilice siempre la misma función de comparación en otras operaciones de lixiviación.