Priority Queue Question

If I am implementing a priority queue, does every object in the queue need an individual priority or can I set I multiple things to the same priority in which case it defaults to FIFO? For example if I want to push instructions to a queue, can I have a series of instructions which operate at say priorty 1 and are executed in a FIFO manner but at some point push an instruction with priority 10 and it will automatically be the next thing to be popped? This would be in case I wanted to stop my instructions or do some subset of instructions before I continue with the regular priority 1 instructions.
thanks

>can I set I multiple things to the same priority in which case it defaults to FIFO?
Absolutely! But keep in mind that there are many different ways to create a priority queue, and building this functionality directly into the data structure may not be practical for some of them. Fortunately, you can fake it pretty easily.

So the priority level used by the queue is based on some comparitive value inside the object you are filling the queue with? So if I wanted to fill a queue with strings (which I am using as instructions) I would be better off making a new class with a string and an integer member called something like priority_level and setting the queue comparator to that? Then I could just make a new instruction object, set its string and priority and push it on the queue. I plan on just using the STL priority queue if I can get it away with it.

Example of the object I am talking about:

Code:

class Instruction{
   public:
      set_ins(std::string s)    {ins_str = s;}
      get_ins()                       {return ins_str;}
     
      set_priority(int p)          {priority_level = p;}
      get_priority()                 {return priority level;}

   private:
      std::string ins_str;
      int priority_level;
};

I'm not sure if it is even really necessary to keep the str and int private but thats how I was taught by my prof, to always use accessor methods. Will this matter at all for the priority queue? Would its implementation be easier if I just made them public?

thanks again

>So if I wanted to fill a queue with strings (which I am using as instructions) I
>would be better off making a new class with a string and an integer member
>called something like priority_level and setting the queue comparator to that?
That's one way to do it, yes.

>I plan on just using the STL priority queue if I can get it away with it.
Off the top of my head, I can't recall the rules for how duplicates are handled with std::priority_queue. It's been a while since I've done an implementation. I say that because I have a nagging feeling that it's not required to give you FIFO behavior. But I would have to check the standard to make sure, and I don't have it handy right now.

>Would its implementation be easier if I just made them public?
Well, presently you could make them public and the effect would be the same. Accessors that don't offer any protection are no better than public access.

>> Well, presently you could make them public and the effect would be the same. Accessors that don't offer any protection are no better than public access.

They may not be better presently, but they are certainly better equipped to handle potential future changes to the implementation. For example, what if you want to change how you store the priority in order to handle two instructions with the same priority level? Exposing the priority level would mean lots of code changes, whereas using the accessor methods now would mean only changing the class implementation.

Out of curiosity - what do you mean about accessors and protection? I am not sure if this is anything I have covered in class and I was wondering if you could give an example.

I was looking through the sgi STL documentation http://www.sgi.com/tech/stl/priority_queue.html but could not figure out how to tell if it defaults to FIFO. If it doesn't, how would you implement such behavior? I would think by using a vector and push_back pop_front possibly but I dont know if that is the right track.
thanks

>> Out of curiosity - what do you mean about accessors and protection?
It refers to your question about the private member variables. The get and set methods are accessor methods because they allow access to the private variables. Generally you want to protect internal implementation details (like the fact that you are currently storing a priority as an int) from outside code, so that if you change the implementation you don't have to change the code that calls the class' interface.

>> I could not figure out how to tell if it defaults to FIFO.
According to Josuttis' C++ Standard Library, the order of elements with the same priority is undefined, so it is best to assume that it does not default to FIFO.

>> how would you implement such behavior?
To handle the situation, I might add the order of insertion to the priority sorting criterion. For example, an id is assigned to each element added to the queue and then incremented for the next one. If two priorities are the same, then check their id. It wouldn't be just that simple and it would depend on other factors specific to your situation, but it could work.

There are other options as well, of course, including simulating the priority_queue yourself as you suggested.

Hmmm this sounds like an interesting project... what may I ask, is this priority queue going to be used in/for ?

What I am doing is sending commands to a telnet session using batch instructions. I take a file and parse it into Product objects. The Product object then generates a Queue of instructions which are a mix of text and escape chars used to either add or delete the product on the server. Each Product queue is then added to an overall instruction queue. Once the instruction queue is built I use a timer control on my form to pop off instructions and send them over the server and then read back from the server. The timer is really nice because I can easily set the delay and it operates on its own thread. The only problem is sometimes warnings occur over the telnet session and when I catch them, currently I have to write directly to the pipe to get past them. I would like to use higher priority instructions to push onto the queue so that I can a) eliminate direct pipe access from my main program. b) have all telnet instructions coming from one piece of code which will be easier to debug and just overall cleaner.

Originally Posted by Daved

>> Out of curiosity - what do you mean about accessors and protection?
>> I could not figure out how to tell if it defaults to FIFO.
According to Josuttis' C++ Standard Library, the order of elements with the same priority is undefined, so it is best to assume that it does not default to FIFO.

Exactly, that's just how a heap works. An item can and sometimes will come out after another item of the same priority.

Okay here is a quick implemenation I wrote up using a vector. It would have been nicer if vector had push_front/pop_front but for some reason they only have push/pop_back. My only concern is in my pop() method. I'm not sure if erase resizes the vector or not. Let me know what you think or if you see any glaring problems. thanks

InsQueue.h

Code:

#include <vector>
#include <string>

class Instruction{
      public:
             std::string ins_str;
             int priority_level;
};


class InsQueue{
      public:
             void push(Instruction i);
             void pop();
             Instruction top();
             bool empty();
             
      private:
              std::vector<Instruction> ins_vect;
};

InsQueue.cpp

Code:

#include "InsQueue.h"

void InsQueue::push(Instruction i){
     for(std::vector<Instruction>::iterator it = ins_vect.begin(); it != ins_vect.end(); ++it){
          if(i.priority_level > it->priority_level){
               ins_vect.insert(it, i);
               return;
          }
     }
     ins_vect.push_back(i);
}

void InsQueue::pop(){
     if(!ins_vect.empty())
          ins_vect.erase(ins_vect.begin());
}

Instruction InsQueue::top(){
     return ins_vect.front();
}

bool InsQueue::empty(){
     return ins_vect.empty();
}

>It would have been nicer if vector had push_front/pop_front but for some reason they only have push/pop_back.
Because push_front and pop_front are potentially expensive operations for a vector. However, you can define the underlying container for a priority_queue adapter. Change it to a deque and you'll have push_front and pop_front.

>I'm not sure if erase resizes the vector or not.
It logically resizes the vector, but memory is not shrinkwrapped. Basically, size() will return the new size but capacity() will remain the same.

so as i keep adding instructions to the back of the vector and erasing them from the front its not getting any smaller? I could be dealing with up to say 10,000 instructions maybe 20k. Is this gonna be a huge issue for me? I don't really think it will matter that much because the entire Queue is filled with instructions before I start using it. Only occassionally throughout the program will I be adding in 3-5 higher priority instructions... So as long as the memory is freed when the program is done I should be okay right?

Using the STL priority queue can I define the comparator as a function? This way if it just used a function I could then compare the actual priority level and if they are the same then compare the ID (if I were to give individual ID's to each instruction, incrementing by one each time a new instruction is added). Otherwise I'm not sure how I would tell it to compare first one thing and then another if the original comparison turns out to be equal.

I understand that push_front/pop_front could be costly as all the elements would need to shift forward but wouldnt it make sense to at least give it the extra functionality and let the programmer decide whether or not it is worth using?

>> Using the STL priority queue can I define the comparator as a function?
Yes. The function should return a bool and take two const references to your class. It should return true if and only if the first parameter is less than the second. That means it should return false if they are equal (which shouldn't actually happen with your ID thing).

>> wouldnt it make sense to at least give it the extra functionality and let the programmer decide whether or not it is worth using?
The tact the standard library creators took was to not provide needlessly expensive operations. While the programmer could decide him or herself, there are enough alternatives to make a situation in which you should actually use those function extremely rare. Leaving them in would be confusing to those programmers who don't know any better and who would just use them because they are available. In addition, push_front doesn't make that much sense as part of a vector class, but it does make sense as part of a double-ended queue class.

If I were implementing the InsQueue, I would not use vector. A deque would be much more appropriate, which is why it is the default container used internally for priority_queue. A list is another option, since you are inserting into the middle a lot.