I have modified the code from this stackoverflow q/a to fit my needs. How to make STL's priority_queue fixed-size . It has worked reasonably well, but there is a problem with the queue size when the queue is empty. In a normal priority_queue, I have noticed that pop() continues to function even when the queue is empty, but the queue will still register as empty. I suppose this is the best functionality that I can hope for without severely modifying the stl priority_queue code. Here is my modified priority_queue:
#include <queue>
#include <algorithm>
template<class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class fixed_priority_queue : public std::priority_queue<T,Container,Compare> {
public :
//FIXME pass comparator as function pointer
fixed_priority_queue(unsigned int size) :
std::priority_queue<T,Container,Compare>(),fixed_size(size) {}
void inline push(const T &x) {
// If we've reached capacity, find the FIRST smallest object and replace
// it if 'x' is larger'
if(this->size() == fixed_size)
{
// 'c' is the container used by priority_queue and is a protected member.
std::vector<Msg*>::iterator beg = this->c.begin();
std::vector<Msg*>::iterator end = this->c.end();
std::vector<Msg*>::iterator min = std::min_element(beg, end,
this->comp);
if(x > *min)
{
*min = x;
// Re-make the heap, since we may have just invalidated it.
std::make_heap(beg, end);
}
}
// Otherwise just push the new item.
else
{
//fixed_priority_queue<T,Container,Compare>::push(x);
std::priority_queue<T,Container,Compare>::push(x);
}
}
private :
//FIXME pass comparator as function pointer
fixed_priority_queue() : std::priority_queue<T,Container,Compare>()
{fixed_size = 10;} // Default size 10.
const unsigned int fixed_size;
// Prevent heap allocation
void * operator new (size_t);
void * operator new[] (size_t);
void operator delete (void *);
void operator delete[] (void *);
};
Here is my custom compare function:
class MsgCmp {
public:
bool operator() (const Msg *m1, const Msg *m2) const {
return m1->get_type() < m2->get_type();
}
};
I call it from another file as follows:
// Construct with fixed_size parameter
fixed_priority_queue <Msg*,vector<Msg*>,MsgCmp> q(2);
q.push(&smsg);
q.push(&dmsg);
cout << "queue size: " << q.size() << endl;
cout <<q.top()->repr()<<endl;
cout << "popping top element" << endl;
q.pop();
cout << "queue size: " << q.size() << endl;
cout <<q.top()->repr()<<endl;
cout << "popping top element" << endl;
q.pop();
cout << "empty?\t" << q.empty() << endl;
cout << "queue size: " << q.size() << endl;
cout << "pushing dynamic element" << endl;
q.push(&new_dmsg);
cout << "pushing dynamic element" << endl;
q.push(&dmsg);
cout << "pushing static element" << endl;
q.push(&smsg);
cout << "queue size: " << q.size() << endl;
cout <<q.top()->repr()<<endl;
cout << "popping top element" << endl;
q.pop();
cout << "empty?\t" << q.empty() << endl;
cout << "queue size: " << q.size() << endl;
cout <<q.top()->repr()<<endl;
cout << "popping top element" << endl;
q.pop();
cout << "empty?\t" << q.empty() << endl;
cout << "queue size: " << q.size() << endl;
cout <<q.top()->repr()<<endl;
cout << "popping top element" << endl;
q.pop();
cout << "empty?\t" << q.empty() << endl;
cout << "queue size: " << q.size() << endl;
And here is the output. I am annotating the output with '#'. My queue sorts by type, with higher types having higher priority:
queue size: 2
type 1
7,5,3,1,3,9,5,
popping top element
queue size: 1
type 0
5,3,1,3,9,5,7,4,8,0,
popping top element
empty? 1
queue size: 0
pushing dynamic element # type 1
pushing dynamic element # type 1
pushing static element # type 0
# so far the output is consistent with the intended functionality
queue size: 2
type 0 # As you can see, the sorting is no longer correct.
# Maybe this is related, maybe not.
5,3,1,3,9,5,7,4,8,0,
popping top element
empty? 0
queue size: 1
type 1
7,5,3,1,3,9,5,
popping top element
empty? 1
queue size: 0
# Queue is empty, but still showing top element. This is also true of
# STL priority_queues, though.
type 1
7,5,3,1,3,9,5,
popping top element
# For some reason, the queue is no longer empty.
empty? 0
# Psychobilly freakout.
queue size: 18446744073709551615
So it seems as if the queue size parameter is somehow given garbage values after the queue is empty. Possibly related to this, my queue, when instantiated as size 1, will not show that empty() is true after a single element is popped.
