Минимальная "куча" C++ с пользовательским типом
Я пытаюсь реализовать минимальную "кучу" в C++ для типа структуры, который я создал. Я создал вектор типа, но он отказал, когда я использовал make_heap на нем, который понятен, потому что он не знает, как сравнить объекты в "куче". Как я создаю минимальную "кучу" (то есть, вершина всегда является самой маленькой в "куче") для типа структуры?
Структура ниже:
struct DOC{
int docid;
double rank;
};
Я хочу сравнить структуры DOC с помощью участника разряда. Как я сделал бы это?
Я пытался использовать приоритетную очередь с классом компаратора, но это также отказало, и также кажется глупым использовать структуру данных, которая использует "кучу" в качестве ее базовой основы, когда то, в чем я действительно нуждаюсь, является "кучей" так или иначе.
Большое спасибо, bsg
2 ответа
Добавить оператор сравнения:
struct DOC{
int docid;
double rank;
bool operator<( const DOC & d ) const {
return rank < d.rank;
}
};
Структуры почти всегда могут иметь конструктор, поэтому я бы также добавил:
DOC( int i, double r ) : docid(i), rank(r) {]
в структуру.
Просто создайте свой собственный «функтор» для сравнения. Поскольку вам нужна «минимальная куча», ваша функция сравнения должна вести себя как оператор «больше»:
#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';
}
Важно, чтобы вы всегда использовали одну и ту же функцию сравнения в дальнейших операциях с кучей.