std::priority_queue is one of the commonly used container but with limitation that it does not follow the FIFO once multiple- elements of same priority are pushed into the queue. Because of its underline algorithm HEAP with random access container, Therefore sometime notified as std::priority_queue is not FIFO (First In First Out)
Solution::
One solution that we are going to discuss it here today is implementation for priority queue with the help of std::multiset<DATA>. Because std::multiset stores the data in sorted order to KEY, and this KEY shall act priority indicator.
Let's first check the problem with std:: priority_queue
#include <iostream> #include <string>#include <queue> #include <map> using namespace std; class Person { int m_age, m_priority; char m_gender; string m_name; public: Person(string a_name,int a_age,char a_gender) { m_name=a_name; m_gender=a_gender; m_age=a_age; if(m_age >= 60) m_priority=1; else m_priority=2; } //to sort on priority bool operator<( const Person& a_pObj ) const { return (m_priority > a_pObj.m_priority); } void ProcessTicket() { cout<<m_name<<", "<<m_age<<", "<<m_gender<<", "<<m_priority <<endl; } }; int main() { std::priority_queue<Person> l_ticketQueue; //1st Person put on Queue l_ticketQueue.push(Person("Mohan",65,'M')); //2nd Person put on Queue l_ticketQueue.push(Person("RAM",44,'M')); //3rd Person put on Queue l_ticketQueue.push(Person("Ramesh",40,'M')); //4th Person put on Queue l_ticketQueue.push(Person("Mohini",36,'F')); while(!l_ticketQueue.empty()) { Person l_personInFront= l_ticketQueue.top(); l_personInFront.ProcessTicket(); l_ticketQueue.pop(); } } |
|
Output |
Explanation |
Ramesh, 40, M, 2 Ram, 44, M, 2 Mohini, 36, F, 2 |
From the output is very much clear that priority_queue doesn’t follow
FIFO. Because Ramesh was 3rd
in the queue but it came before Ram and both having same priority i.e. (2). This happened because std::priority_queue uses HASH to store data. |
Here we have written a generic thread safe priorityQueue class that can be altered as per your requirement. Hope it shall help you. Please do suggest if you have better way to implement below priorityQueue class.
#include <set> #include <mutex> #include <condition_variable> #include <thread> //Generic thread-safe Priority Queue Class {Read-to-use} //With functions to put ITEM in queue and get ITEM from Queue template<class DATA> class priorityQueue { std::multiset<DATA> m_queue; std::mutex m_lock; std::condition_variable m_cv; public: void putData(DATA a_data) { try { { std::lock_guard<std::mutex> l_lockTaken(m_lock); m_queue.emplace(a_data); } m_cv.notify_all(); } catch(std::exception& e) { std::cout<<"putData::Exception :: "<<e.what()<<std::endl; throw; } catch(...) { std::cout<<"putData::Exception Caught "<<std::endl; throw; } } DATA getData() { try { DATA l_Value; { std::unique_lock<std::mutex> l_lockTaken(m_lock); while(m_queue.empty()) m_cv.wait(l_lockTaken); { auto l_itr=m_queue.begin(); l_Value=*l_itr; m_queue.erase(l_itr); } } return l_Value; } catch(std::exception& e) { std::cout<<"getData ::Exception :: "<<e.what()<<std::endl; throw; } catch(...) { std::cout<<"getData :: Exception Caught "<<std::endl; throw; } } }; //Class Person using namespace std; class Person { int m_age, m_priority; char m_gender; string m_name; public: Person(){} Person(string a_name,int a_age,char a_gender) { m_name=a_name; m_gender=a_gender; m_age=a_age; if(m_age >= 60) m_priority=1; else m_priority=2; } //to sort on priority bool operator<( const Person& a_pObj ) const { return (m_priority < a_pObj.m_priority); } void ProcessTicket() { cout<<m_name<<", "<<m_age<<", "<<m_gender<<", "<<m_priority <<endl; } }; int main() { priorityQueue<Person> l_ticketQueue; //1st Person put on Queue l_ticketQueue.putData(Person("Mohan",65,'M')); //2nd Person put on Queue l_ticketQueue.putData(Person("RAM",44,'M')); //3rd Person put on Queue l_ticketQueue.putData(Person("Ramesh",40,'M')); //4th Person put on Queue l_ticketQueue.putData(Person("Mohini",36,'F')); while(1) { Person l_personInFront= l_ticketQueue.getData(); l_personInFront.ProcessTicket(); } return 0; } |
|
Output |
Explanation |
Mohan, 65, M, 1 RAM, 44, M, 2 Ramesh, 40, M, 2 Mohini, 36, F, 2 |
Here we can see from output that queue follows FIFO once same
priority(KEY) entries are found. Therefore RAM, RAMESH and MOHINI are in the
same order of their insertion. |
Your Comments /Suggestions & Questions are always welcome.
We would like to help you with best of our knowledge.