How to implement a priority queue header in C++ using STL?

Posted on 2006-04-29
Last Modified: 2009-12-16
Here is my vpqueue.h that i need to implement for my project. I think i have most of it but I am stuck on what i am missing since the program goes and only writes the same itme out to the screen and i know i must be missing something in the header file that is messing the program up.

// here was the programming exercise i was tasked with///
#include <vector>
#include "d_except.h"

using namespace std;

class vpriority_queue
                  // default constructor. create an empty priority queue
            int size() const;
                  // return the size of the priority queue
            bool empty() const;
                  // is the priority queue empty?

            void push(const T& item);
                  // insert item into the priority queue
                  // Postcondition: the priority queue has one more  element
            void pop();
                  // remove the highest priority (maximum) item from the priority queue.
                  // Precondition: the priority queue is not empty.
                  // if it is empty, the function throws the underflowError exception

            T& top();
                  // return the highest priority (maximum) item in the priority queue
                  // Precondition: the priority queue is not empty.
                  // if it is empty , the function throws the underflowError excpetion

            const T& top() const;
                  // constant version

            vector<T> pqVector;
                  // pqVector holds the priority queue elements
                                                // vector that implements the priority queue

            int findMaxIndex() const;
            // find the index of the maximum value in pqVector
            int maxIndex;
                                // index of the maximum value
            bool recomputeMaxIndex;
                                // do we need to compute the inmdex of the maximum element?

//Now this is where i tried to implement all the parts of the header file//

// constructor. create empty priority queue


// return the size of the priority queue
template <typename T>
int vpriority_queue<T>::size() const
   return pqVector.size();

// return true if the priority queue is empty and false
// otherwise
template <typename T>
bool vpriority_queue<T>::empty() const
   return pqVector.empty();

// insert a new item in the priority queue
template <typename T>
void vpriority_queue<T>::push(const T& item)
      // insert the item at the end of the vector

      recomputeMaxIndex = true;

// remove the element of highest priority,
template <typename T>
void vpriority_queue<T,Compare>::pop()
      // check for an empty priority queue
      if (pqVector.empty())
            throw underflowError("vpriority_queue pop(): empty list");

      // delele element from back of pqVector

template <typename T>
T& vpriority_queue<T>::top()
   // check for empty
   if (pqVector.empty())
            throw underflowError("vpriority_queue top(): empty list");

      // return
      return pqVector[maxIndex];

template <typename T>
const T& vpriority_queue<T>::top() const
   // check for an empty heap
   if (pqVector.empty())
            throw underflowError("vpriority_queue top(): empty list");

      // return
      return pqVector[maxIndex];

// not sure what i need to implement  for this function
int findMaxIndex() const


-----Not sure what else i am missing in the implementation of the header file
if needed i can supply the test program or anything else that is needed that can help me figure out what i am missing to get this project working--------------

To me this is difficult since i am new to STL and not sure what i am missing in this header file. I sure hope someone can tell me what i need to add to get this header file implemented correctly so my program starts to work. The prgram is due tomorrow and i am really stuck on what i am missing. Thanks all.
Question by:carbuff1976
    1 Comment
    LVL 2

    Accepted Solution

    sorry if this comment comes late but i believe knowledge never comes too late
    but i think you lack the understanding of a priority queue...
    the thing is as a template class, you will be unable to provide the class with the findMaxIndex function as you do now know which instance in the template class will be of the highest priority.

    moreover, your implementation of pop is wrong, u just pop the back element, ie the last element and not the highest priority element

    Featured Post

    Find Ransomware Secrets With All-Source Analysis

    Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

    Join & Write a Comment

    Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
    Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
    The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
    The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

    728 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now