I derived from std::priority_queue to implement a few specialized methods. One of these methods somekind of a fixed queue when I add an element and the queue is full, the smallest element is dropped from the queue.
template<typename T,
typename Sequence = std::vector<T>,
typename Compare = std::less<typename Sequence::value_type> >
class fixed_priority_queue : public std::priority_queue<T, Sequence, Compare> {
friend class BCQueue_; // to access maxSize_
public:
fixed_priority_queue(unsigned int maxSize)
: maxSize_(maxSize) {}
void insertWithOverflow(const T& x) {
if (this->size() == maxSize_) {
auto beg = this->c.begin();
auto end = this->c.end();
auto min = std::min_element(beg, end);
if(x > *min) {
*min = x;
std::make_heap(beg, end);
}
}
else {
this->push(x);
}
}
// ...
private:
fixed_priority_queue() {}
const unsigned int maxSize_;
};
This is my comparator I use:
class ScoreLessThan : public std::binary_function<
std::shared_ptr<CCandidate>, std::shared_ptr<CCandidate>, bool> {
public:
bool operator()(
const std::shared_ptr<CCandidate>& a, const std::shared_ptr<CCandidate>& b) const {
return a->score > b->score;
}
};
My derived fixed_priority_queue class I wrap to keep functionality a little separated, so finally I have this:
class BCQueue_ : public fixed_priority_queue<
std::shared_ptr<CCandidate>, std::vector<std::shared_ptr<CCandidate> >, ScoreLessThan> {
public:
BCQueue_(size_t maxSize)
: fixed_priority_queue(maxSize) {}
bool willInsert(float score) {
return size() < maxSize_ || top()->score < score;
}
};
I can use this like:
BCQueue_ queue(30);
The CCandidate
is just a holder for some data. One property is the score
field, that I use in the comparator above.
When I use above class with CCandidate as raw pointer all compiles with problem and works fine, now I want to replace the raw pointer with std::shared_ptr
(as I did above) and I get a compilation error:
... 199:5: error: no match for ‘operator>’ in ‘x >min.__gnu_cxx::__normal_iterator::operator* [with _Iterator = std::shared_ptr*, _Container = std::vector >, __gnu_cxx::__normal_iterator::reference = std::shared_ptr&]()’
...
... :199:5: note: candidates are:
... :199:5: note: operator>(int, int)
... :199:5: note: no known conversion for argument 2 from ‘std::shared_ptr’ to ‘int’
Maybe this is a simple issue. I am not shure if I defined the comparator properly or if I need to change the comparison in insertWithOverflow()
x > *min
, actually I do not know what I should change there.
I should mention, that I have found the implementation of `insertWithOverflow' here on stackoverflow which just fits what I need. See here: How to make STL's priority_queue fixed-size
Like said, with raw pointers all this is no problem. Could somebody please help me out on this. Thanks in advance!
You need to use the specified comparison function everywhere in your function:
using std::priority_queue<T, Sequence, Compare>::comp;
void insertWithOverflow(const T& x) {
if (this->size() == maxSize_) {
auto beg = this->c.begin();
auto end = this->c.end();
auto min = std::min_element(beg, end, comp);
if(comp(*min, x)) {
*min = x;
std::make_heap(beg, end, comp);
}
}
else {
this->push(x);
}
}