An introduction to the STL : Priority Queues

(Reader Level : Beginner)
(Knowledge assumptions : classes, std::vector, std::string, queues)
Hello all! This time we're going to look at another STL container - the Priority Queue. You probably know what a queue is but just in case you don't or your memory could use some jogging, here goes... A queue is a First In First Out data structure. It means that the first element you put into the queue is the first one to leave the queue. Think of it as one of those long queues at the supermarket. The sooner you enter the queue, the sooner you can leave. So what is a priority queue? A priority queue is a queue where elements are entered based on their priority. If the wife of the supermarket's Manager had to do some shopping, she might not have to wait in line(hypothetically speaking ;)). She could immediately walk to the front of the queue and check out her purchases. If the Manager's daughter were also present, then she would stand behind the wife because she doesn't get as much importance as the mother but is still more important than the rest of the frustrated patrons. I know, I know. Silly example but hopefully you get the idea. In order to illustrate the beauty of a priority queue let me describe a rather contrived problem. This question was presented to me for a programming competition held at my college university.

The Problem: Write a C++ program to accept a list of words from the user. The user must also enter a weight associated with each word. Finally, display the words in decreasing order of their weights.

Solution Attempt #1 : Using a vector:
The user having to enter words and associated weights is pretty basic stuff. So, I'm not going to write any of that code in order to keep this blog post as short as possible. Here's one possible way to do it with vectors.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

//This class encapsulates a word that can be prioritized based on a number.
class PrioritizedWord
{
private:
 std::string m_word;
 int m_priority;

public:
 explicit PrioritizedWord()
 {}

 explicit PrioritizedWord(const std::string& word, const int priority = 0) : m_word(word), m_priority(priority)
 {}
           
 //Compares two words. This overloaded operator prioritizes words according to their weight.
 const bool operator <(const PrioritizedWord& pW) const
 {
     return (m_priority < pW.m_priority);
 }

 //Overloaded "put to" operator for streaming output.
 friend std::ostream& operator <<(std::ostream& out, const PrioritizedWord& pW)
 {
     out<<pW.m_word;
     return out;
 }
};

int main()
{
std::vector<PrioritizedWord>    vWords;

vWords.push_back(PrioritizedWord("Angelo", 23));
vWords.push_back(PrioritizedWord("This", -1));
vWords.push_back(PrioritizedWord("Here", 51));
vWords.push_back(PrioritizedWord("Was", -1));

std::sort(vWords.begin(), vWords.end());

for(std::vector<PrioritizedWord>::size_type i = 0; i < vWords.size(); ++i)
{
 std::cout<<vWords[i];
}

return 0;
}

We are sorting the vector contents using a function named sort that is available in the pre-compiled header <algorithm>. The working of the sort function is beyond the scope of this post but I'll provide a link at the end. Also, note the use of the overloaded less-than operator. We need to overload this operator because the sort() function will compare two PrioritizedWord's using it. Don't forget the const at the end of the operator definition. sort() expects that our overloaded operator routine will not alter any class member variables. If you forget to be const-correct in this case, the compiler will bite your head off!

Solution Attempt #2 : Using a priority queue:
We'll use the same class PrioritizedWord from above. That way my lazy self won't have to do much typing. :D

#include <iostream>
#include <string>
#include <queue>  //Instead of vectors, we now use a queue.

//PrioritizedWord Class definition goes here.

int main()
{
std::priority_queue<PrioritizedWord>    wordQueue;

wordQueue.push(PrioritizedWord("Angelo", 23));
wordQueue.push(PrioritizedWord("Here", 51));
wordQueue.push(PrioritizedWord("Was", -1));

//Peek and pop until the priority queue is empty.
while(!wordQueue.empty())
{
  std::cout<<wordQueue.top()<<" ";
  wordQueue.pop();
}

return 0;
}

Note that this time we didn't have to sort anything because the words were pushed into the queue based on their priority. This means that at the end of our input, the words in the priority queue are already sorted based on their weights. Pretty neat, huh? I'd say that in this case a priority queue leads to more elegant code when compared to using a vector. The stuff that I said earlier about being const-correct with regard to the overloaded less-than operator applies here too. The push() function is the one who actually prioritizes the words. Here are some good links to read up on.

SGI Documentation on Priority Queues
Member functions of STL Priority Queue
SGI Documentation on sort algorithm
Enjoy!