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.

Quote:

---

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.

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

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.

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!

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)

---

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?

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.

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.

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

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.

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;
}

---

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.

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