Thread: Priority Queue Question

  1. #16
    Registered User
    Join Date
    May 2006
    Posts
    89
    Would the compare function be a part of the class that is being compared? If so, could I just write my own comparison function for my Instruction class and use it in the STL priority queue? How would the declaration for this function look in my header file? Would it be similar to an operator? Sorry if these questions seem obvious but I haven't been in a regular programming class in 2 quarters and all my old notes on this kind of thing are 4 hours away and I have no prof to ask. I tried figuring it out looking at the STL documentation but I just got more confused I think haha.
    thanks

  2. #17
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    There are several ways to do it. One is to write an operator< for your class, which can be done as a member function or as a non-member (possibly friend) function. If you do this, then you don't have to pass anything to the priority_queue to tell it how to sort, it uses the less than function automatically. Another is to write a non-member (possibly friend) function like what I mentioned that takes two const references and returns a bool. A third way is to write an empty class and add an operator() function that takes two const references to your class and returns a bool.

    Any of the three should work in this situation, each have minor advantages and disadvantages, but I don't see any of them being much better than the others. Perhaps the operator< for your class would be easiest. Just look up operator overloading or operator< to get good examples of that.

  3. #18
    Registered User
    Join Date
    May 2006
    Posts
    89
    Okay, yea I have some old code with overloaded operators in it so i will take a look at that and see where I get.
    thanks!
    Last edited by ac251404; 08-15-2006 at 02:35 PM.

  4. #19
    Registered User
    Join Date
    May 2006
    Posts
    89
    Okay I ran into some trouble, but it doesnt seem to bad. It's just that the compiler is saying InstructionQueue has not been declared in my Main. Here is the code:

    Main
    Code:
    #include <cstdlib>
    #include <iostream>
    
    #include "InstructionQueue.h"
    
    using namespace std;
    
    int main(int argc, char *argv[])
    {
        InstructionQueue iq;
        
        Instruction i1("1", 1);
        
        system("PAUSE");
        return EXIT_SUCCESS;
    }
    Instruction.h
    Code:
    class Instruction{
          public:
                 Instruction();
                 Instruction(std::string s, int p);
                 
                 std::string ins_str;
                 int priority_level;
                 int p_id;
                 
                 friend bool operator < (const Instruction& i1, const Instruction& i2);
    };
    Instruction.cpp
    Code:
    #include "Instruction.h"
    
    Instruction::Instruction():ins_str(""),priority_level(1),p_id(0){ }
    
    Instruction::Instruction(std::string s, int p):ins_str(s),priority_level(p),p_id(0) { }
    
    
    bool operator < (const Instruction& i1, const Instruction& i2){
            if(i1.priority_level != i2.priority_level)
              return (i1.priority_level < i2.priority_level);
            else 
              return(i1.p_id < i2.p_id); 
    }
    InstructionQueue.h
    Code:
    #include "Instruction.h"
    #include <queue>
    
    #ifndef INSTRUCTION_H
    #define INSTRUCTION_H
    
    class InstructionQueue{
          public:
                 InstructionQueue();
                 
                 void push(Instruction i);
                 void pop(){q.pop();}
                 bool empty(){return q.empty();}
                 Instruction top(){return q.top();}
          
          private: 
                 priority_queue< deque<Instruction> > q;
                 int id;
    }
    #endif
    InstructionQueue.cpp
    Code:
    #include "InstructionQueue.h"
    
    InstructionQueue::InstructionQueue():id(0){ }
    
    void InstructionQueue::push(Instruction i){
         i.p_id = id++;
         q.push(i);
    }
    And here is the exact error from Dev C++:

    Code:
     C:\Dev-Cpp\main.cpp In function `int main(int, char**)': 
    10 C:\Dev-Cpp\main.cpp `InstructionQueue' undeclared (first use this function)
    Last edited by ac251404; 08-15-2006 at 02:55 PM.

  5. #20
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    One danger of the global id is the potential for it to overflow if you will have lots of objects in the queue, or if the queue will be running for a long time. If you don't expect your program to run long enough to overflow the size of whatever datatype you use, then that would be fine. I would use a static member of whatever class handles the pushing.

    You don't actually have to create your own instruction queue class if the priority_queue is already encapsulated in a class and the adding of objects happens all in one place (which is how it probably should be anyway).

    If you want this program to run indefinitely or you expect the number of instructions to be huge, then maybe you shouldn't use a priority_queue after all.



    Now that I think about it, there might be a better way. How many different priorities do you expect to have? Will it be like a low, medium, high type thing, or will there be thousands of different priorities and only a few duplicates?

  6. #21
    Registered User
    Join Date
    May 2006
    Posts
    89
    I was thinking 3 priorities tops right now. 1 for general instructions, 2 for navigation thru menus (if for example a warning screen of some kind appears navigate out of it then continue with lvl 1 instructions), 3 for extremely urgent things which would basically be a stop instruction which would halt all communication. So yes a low/med/high type thing. I would say at the very most there would be 20k initial instructions, probably closer to 5-10k. I dont plan on running into to many error screens or anything but anytime that happens it adds about 5 instructions which doesnt make to much of a difference. So yea I would say 20k max just to be safe.

    edit: Also the priority_queue is not part of any other class which is why I made the InstructionQueue class. I then use a global InstructionQueue for doing everything with.
    Last edited by ac251404; 08-15-2006 at 03:42 PM.

  7. #22
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    In this case, I think it is a much better idea to just have a separate FIFO queue for each priority. If you want to make the code flexible, you can use a vector of queues with the priority as the index (adjusting for the zero-based indices of vector). Or you can hard code a queue for each possible priority. Either way, you'll have a much easier implementation and it might be more efficient as well. You could do this inside your instruction queue class and still provide the same interface. To pop the next instruction, you would obviously start at the queue with the highest priority and move the the next one only if it was empty.

    The idea of a priority_queue that defaults to FIFO for equal priorities makes sense only if the number of priorities is high, otherwise it is a waste of the benefits of the priority queue over a regular queue.

  8. #23
    Registered User
    Join Date
    May 2006
    Posts
    89
    Okay, that does sound a lot more effecient for this. I am going to give it a shot. Any idea though about that error posted above? I think it might be some syntax I am missing but I can't find it and I think it will occur even after I make the changes you suggested.
    thanks

  9. #24
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Sorry, I don't remember seeing that post. Perhaps the missing semi-colon at the end of the InstructionQueue class declaration is what's causing the problem.

  10. #25
    Registered User
    Join Date
    May 2006
    Posts
    89
    Okay well here is the final code I came up with. I have one last concern regarding it: in my top() method (last code segment) you can see that I use it->front() instead of it->top(). This seems to work in testing and I guess it should but I thought it was odd that the compiler did not think the top() member existed. I am sure it is the way I have the iterator declared and I'd like to fix it if it is wrong but as of now it works in testing.

    Instruction.h
    Code:
    class Instruction{
          public:
                 Instruction();
                 Instruction(std::string s, int p);
                 
                 std::string ins_str;
                 int priority_level;
                 
                 friend bool operator < (const Instruction& i1, const Instruction& i2);
    };
    Instruction.cpp
    Code:
    Instruction::Instruction():ins_str(""),priority_level(0){ }
    
    Instruction::Instruction(std::string s, int p):ins_str(s),priority_level(p){ }
    
    
    bool operator < (const Instruction& i1, const Instruction& i2){
              return (i1.priority_level < i2.priority_level);
    }
    InstructionQueue.h
    Code:
    class InstructionQueue{
          public:
                 InstructionQueue();
                 
                 void push(Instruction i);
                 void pop();
                 bool empty();
                 Instruction top();
          
          private: 
                 std::vector< std::queue<Instruction> > q_vect; 
    };
    InstructionQueue.cpp
    Code:
    InstructionQueue::InstructionQueue(){}
    
    void InstructionQueue::push(Instruction i){ 
         int index = i.priority_level;    
         if(index >= q_vect.size())
              q_vect.resize(index+1);
         q_vect[index].push(i);
    }
    
    void InstructionQueue::pop(){
         std::vector< std::queue<Instruction> >::reverse_iterator it;
         
         for(it = q_vect.rbegin(); it != q_vect.rend(); ++it){
                if(!it->empty()){
                      it->pop();
                      break;
                }
         }   
         return;
    }
    
    bool InstructionQueue::empty(){
         std::vector< std::queue<Instruction> >::iterator it;
         for(it = q_vect.begin(); it != q_vect.end(); ++it){
                if(!it->empty())
                      return false;
         }  
         return true;
    }
    
    Instruction InstructionQueue::top(){
         std::vector< std::queue<Instruction> >::reverse_iterator it;     
         for(it = q_vect.rbegin(); it != q_vect.rend(); ++it){
                if(!it->empty()){
                      return it->front();
                }
         }
         Instruction itmp;
         return itmp;
    }

  11. #26
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Looks good.

    >> I use it->front() instead of it->top().
    That's correct. The interface of queue uses the term front instead of top. I don't know the exact reasons, but I imagine it is to match the common terminology used with a queue.

  12. #27
    Registered User
    Join Date
    May 2006
    Posts
    89
    Haha I knew that, my brain must have just been fried when I was messing with that last night. Got everything working great in my app. Thanks for all your help.
    -ac

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple Queue Question
    By RobJ in forum C++ Programming
    Replies: 5
    Last Post: 05-27-2007, 09:28 AM
  2. linker error
    By tasha302 in forum C++ Programming
    Replies: 3
    Last Post: 12-14-2006, 12:00 AM
  3. ADT queue
    By ^xor in forum C Programming
    Replies: 4
    Last Post: 06-15-2005, 05:43 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM