priority queue with time limit

[charian0920]

hi c++ guru. i need your help... i'm new in hardcore c++ and currently working on a c++ container namely the priority_queue. i don't have problem using the priority_queue itself but i have this additional requirement to also consider the age of the items in the queue. my current implementation only deals with the priority of the items in the queue by overloading the "<" operator. i don't know yet what to do when considering the age of the items in the priority_queue. any help is greatly appreciated... PS: sample code would be a great help... :) charian

[Arman S]

More certainty needed; is age another field in the queue item or you mean the time that an item has lived in the queue. At all events, seems you should redfine the < operator. Provide more info...

-- ====== Arman

[charian0920]

What i mean by age is the time that an item has lived in the queue. i only have the following for now ... 1. template class for my queue: template class ThreadSafePriorityQueue : public CComAutoCriticalSection { private: priority_queue > m_q; int m_intMaxSize; public: ThreadSafePriorityQueue() { m_intMaxSize = 10000; } ThreadSafePriorityQueue(int intMaxSize) { m_intMaxSize = intMaxSize; } ~ThreadSafePriorityQueue() { } bool push( const T& x ) { bool rtn = true; Lock(); if(m_q.size() > m_intMaxSize) { rtn = false; } else { m_q.push( x ); } Unlock(); return rtn; } bool pop( T& x ) { bool rtn = false; Lock(); if( !m_q.empty() ) { rtn = true; x = m_q.top(); m_q.pop(); } Unlock(); return rtn; } bool empty() { Lock(); bool rtn = m_q.empty(); Unlock(); return rtn; } T front() { Lock(); T rtn = m_q.top(); Unlock(); return rtn; } }; 2. Then I have this structure that i pushed to the queue typedef struct _StructPriorityRequest { int intPriority; StructRequest structMessage; bool operator < (const _StructPriorityRequest &structT2) const { return intPriority > structT2.intPriority; } } StructPriorityRequest; How should i modify my codes so i could consider the age of the item in the queue? Please help me ....

[Arman S]

StructPriorityRequest should have another field that shows the insertion time; integer value timeStart. Which will be initialized in push like so; bool push( const T& x ) { bool rtn = true; Lock(); if(m_q.size() > m_intMaxSize) { rtn = false; } else { x.timeStart = time(NULL); // HERE m_q.push( x ); } Unlock(); return rtn; } Then modify the < operator of StructPriorityRequest like so; bool operator < (const _StructPriorityRequest &structT2) const { int myAge = time(NULL) - timeStart; int herAge = time(NULL) - structT2.timeStart; return intPriority > structT2.intPriority && /*ALSO CONSIDER myAge and herAge */; } IMPORTANT: As far a know, std::priority_queue does the element comparision inside push method not pop. But the method I've described works if the queue does comarision inside pop not push. So make sure if so, you have to change the container std::priority_queue. Otherwise you will have no way to calculate ages.

-- ===== Arman

[charian0920]

First of all, I would like to thank you for your responses ... After reading your answer, I just found out that I'm still on the right track ... Thank goodness :) I just did the same concept after a lot of readings and research ... The only difference is that i don't sort (or call tha comparison) when the pop method is called. What I did was I created a worker thread that will call the sort(or call tha comparison) after a certain time had elapsed. In effect, I'll be re-sorting my queue on given a period of time. I'm not sure if this is the efficient way though ... Care to share your thoughts?? ;)

[Arman S]

First of all, I would like to thank you for your responses ... You are welcome. :) Look. You've chosen a complicated way. Actually the problem can be solved without multithreading. Do not use multithreading unless it is reasonably resired. Do not be surprised if a strange synchronization issue gets put ahead. Also do not think you are done unless you are sure all the synchronization issues are considered [at least critical sections should be used to protect the queue from concurrent accesses]. What I'd do is create a custom priority queue [e.i. my own queue] and organize the pop method in a way that it finds the element with the highest priority and removes it. Even no sorting is required; only do find the 'max' element (the highest priority element) and remove/return it.

-- ===== Arman