Priority Queue
Home Up

 

Same level pages:
Vector
Deque
List
Set
Multiset
Map
Multimap
String
Bitset
Stack
Queue
Priority Queue

Parent level pages:
Containers
Classes
Iterators
Algorithms

The priority_queue<T, Seq, Compare> template class is an adaptor that stores data in a  sequence Seq (a vector<T> by default> to provide a restricted subset of container functionality that does not allow iteration. It is assignable and default constructible. T must be assignable. Seq must be a random access container whose value type is T. The Compare class must represent a binary predicate that induces a strict weak ordering on T. Normally, the default Compare class simply uses the member function with the signature bool operator<(const& T) const or the non-member function with the signature bool operator<(const & T, const &T).

The STL priority_queue template is found in <queue> and is normally implemented as a heap. A simplified declaration of the queue template would look something like:

template<class T>
class priority_queue
{
public:
    priority_queue();
    bool empty() const;
    unsigned size() const;
    T& top();
    const T& top() const;
    void push(T& x);
    void pop();
};

The full declaration of a priority queue looks something like:

template<class T,
    class Cont = vector<T>,
    class Pred = less<Cont::value_type> >
class priority_queue
{
public:
    typedef Cont::allocator_type allocator_type;
    typedef Cont::value_type value_type;
    typedef Cont::size_type size_type;
    explicit priority_queue(const Pred& pr = Pred(),
        const allocator_type& al = allocator_type());
    priority_queue(const value_type *first, const value_type *last,
        const Pred& pr = Pred(), const allocator_type& al = allocator_type());
    bool empty() const;
    size_type size() const;
    allocator_type get_allocator() const;
    value_type& top();
    const value_type& top() const;
    void push(const value_type& x);
    void pop();
protected:
    Cont c;
    Pred comp;
};
 

 

ŠPaul Buis & Ball State University Author: Paul Buis (peb@bsu.edu) Last Modified:10/26/00 03:31 PM

NOTICE: The information presented on this page represents the personal views, ideas, and opinions of the author. This is not an official Ball State University web page. Links contained at this web site to other organizations, are presented as a service and neither constitute nor imply university endorsement or warranty.