How to use the priority queue STL for objects

Question

class Person   public      int age       I want to store objects of the class Person in a priority queue   priority queue lt  Person  vector lt Person gt        gt    I think I need to define a class for the comparison thing  but I am not sure about it   Also  when we write   priority queue lt  int  vector lt int gt   greater lt int gt   gt     How does the greater work

User · Answer

This piece of code may help     include  lt bits stdc   h gt  using namespace std       class node  public      int age      string name      node int a  string b           age   a          name   b            bool operator lt  const node amp  a  const node amp  b         node temp1 a temp2 b      if a age    b age          return a age  gt  b age      else          return temp1 name append temp2 name   gt  temp2 name append temp1 name            int main        priority queue lt node gt  pq      node b 23  prashantandsoon          node a 22  prashant        node c 22  prashantonly        pq push b       pq push a       pq push c        int size   pq size        for  int i   0  i  lt  size    i                cout lt  lt pq top   age lt  lt     lt  lt pq top   name lt  lt   n           pq pop              Output    22 prashantonly 22 prashant 23 prashantandsoon

User · Answer

A priority queue is an abstract data type that captures the idea of a container whose elements have  priorities  attached to them   An element of highest priority always appears at the front of the queue    If that element  is removed  the next  highest priority  element  advances to the front    The C   standard library defines a class template priority queue  with the following operations   push   Insert an element into the prioity queue   top  Return  without removing it  a highest priority element from the priority queue   pop  Remove a highest priority element from the priority queue   size  Return the number of elements in the priority queue   empty  Return true or false according to whether the priority queue is empty or not   The following code snippet shows how to construct two priority queues  one that can contain integers and another one that can contain character strings    include  lt queue gt   priority queue lt int gt  q1  priority queue lt string gt  q2    The following is an example of priority queue usage    include  lt string gt   include  lt queue gt   include  lt iostream gt   using namespace std      This is to make available the names of things defined in the standard library   int main         piority queue lt string gt  pq     Creates a priority queue pq to store strings  and initializes the queue to be empty       pq push  the quick        pq push  fox        pq push  jumped over        pq push  the lazy dog            The strings are ordered inside the priority queue in lexicographic  dictionary  order          fox    jumped over    the lazy dog    the quick          The lowest priority string is  fox   and the highest priority string is  the quick       while   pq empty             cout  lt  lt  pq top    lt  lt  endl      Print highest priority string        pq pop                          Remmove highest priority string            return 0      The output of this program is   the quick the lazy dog jumped over fox   Since a queue follows a priority discipline  the strings are printed from highest to lowest priority   Sometimes one needs to create a priority queue to contain user defined objects   In this case  the priority queue needs to know the comparison criterion used to determine which objects have the highest priority   This is done by means of a function object belonging to a class that overloads the operator      The overloaded    acts as  lt  for the purpose of determining priorities   For example  suppose we want to create a priority queue to store Time objects   A Time object has three fields  hours  minutes  seconds   struct Time       int h       int m       int s      class CompareTime       public      bool operator   Time amp  t1  Time amp  t2     Returns true if t1 is earlier than t2              if  t1 h  lt  t2 h  return true         if  t1 h    t2 h  amp  amp  t1 m  lt  t2 m  return true         if  t1 h    t2 h  amp  amp  t1 m    t2 m  amp  amp  t1 s  lt  t2 s  return true         return false            A priority queue to store times according the the above comparison criterion would be defined as follows   priority queue lt Time  vector lt Time gt   CompareTime gt  pq   Here is a complete program    include  lt iostream gt   include  lt queue gt   include  lt iomanip gt   using namespace std   struct Time       int h      gt   0     int m     0-59     int s     0-59     class CompareTime   public      bool operator   Time amp  t1  Time amp  t2               if  t1 h  lt  t2 h  return true         if  t1 h    t2 h  amp  amp  t1 m  lt  t2 m  return true         if  t1 h    t2 h  amp  amp  t1 m    t2 m  amp  amp  t1 s  lt  t2 s  return true         return false            int main         priority queue lt Time  vector lt Time gt   CompareTime gt  pq          Array of 4 time objects       Time t 4       3  2  40    3  2  26    5  16  13    5  14  20         for  int i   0  i  lt  4    i         pq push t i         while    pq empty             Time t2   pq top           cout  lt  lt  setw 3   lt  lt  t2 h  lt  lt       lt  lt  setw 3   lt  lt  t2 m  lt  lt       lt  lt         setw 3   lt  lt  t2 s  lt  lt  endl         pq pop               return 0      The program prints the times from latest to earliest   5  16  13 5  14  20 3   2  40 3   2  26   If we wanted earliest times to have the highest priority  we would redefine CompareTime like this   class CompareTime   public      bool operator   Time amp  t1  Time amp  t2     t2 has highest prio than t1 if t2 is earlier than t1              if  t2 h  lt  t1 h  return true         if  t2 h    t1 h  amp  amp  t2 m  lt  t1 m  return true         if  t2 h    t1 h  amp  amp  t2 m    t1 m  amp  amp  t2 s  lt  t1 s  return true         return false

User · Answer

You need to provide a valid strict weak ordering comparison for the type stored in the queue  Person in this case  The default is to use std  less lt T gt   which resolves to something equivalent to operator lt   This relies on it s own stored type having one  So if you were to implement  bool operator lt  const Person amp  lhs  const Person amp  rhs      it should work without any further changes  The implementation could be  bool operator lt  const Person amp  lhs  const Person amp  rhs      return lhs age  lt  rhs age      If the the type does not have a natural  less than  comparison  it would make more sense to provide your own predicate  instead of the default std  less lt Person gt   For example   struct LessThanByAge     bool operator   const Person amp  lhs  const Person amp  rhs  const         return lhs age  lt  rhs age           then instantiate the queue like this   std  priority queue lt Person  std  vector lt Person gt   LessThanByAge gt  pq    Concerning the use of std  greater lt Person gt  as comparator  this would use the equivalent of operator gt  and have the effect of creating a queue with the priority inverted WRT the default case  It would require the presence of an operator gt  that can operate on two Person instances

User · Answer

You would write a comparator class  for example   struct CompareAge       bool operator   Person const  amp  p1  Person const  amp  p2               return  true  if  p1  is ordered before  p2   for example          return p1 age  lt  p2 age             and use that as the comparator argument   priority queue lt Person  vector lt Person gt   CompareAge gt    Using greater gives the opposite ordering to the default less  meaning that the queue will give you the lowest value rather than the highest

User · Answer

We can define user defined comparator   The code below can be helpful for you   Code Snippet     include lt bits stdc   h gt  using namespace std   struct man     string name    int priority       class comparator    public     bool operator   const man amp  a  const man amp  b               return a priority lt b priority           int main        man arr 5      priority queue lt man  vector lt man gt   comparator gt  pq      for int i 0  i lt 3  i              cin gt  gt arr i  name gt  gt arr i  priority       pq push arr i             while   pq empty              cout lt  lt pq top   name lt  lt     lt  lt pq top   priority       pq pop         cout lt  lt endl          return 0      input       batman 2   goku  9   mario 4                                    Output         goku  9   mario 4   batman 2

[c++] How to use the priority queue STL for objects?

Examples related to c++

Examples related to stl