Tech Sujhav

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

Mohan, 65, M, 1
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 3^rd 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.

Solution: Implementation of priority queue using std::multiset

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 <iostream>
#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.

So feel free to put Questions

Tech Sujhav

Pages

Priority Queue with FIFO