The STL priority_queue is a container adaptor. That is, it
is not a "first-class" container, but instead simply "adapts" one of
the sequential first-class containers (by default, the vector)
for its own purposes. So, the vector interface is restricted
(i.e., much of it is hidden) so that the required access-via-highest-priority
priority-queue-like behavior is provided.
Default Constructor
- priority_queue<T> pq;
- Construct an empty priority_queue pq which can hold
values of type T.
Copy Constructor
There is, of course, only one copy constructor, but there are two
syntactic forms that invoke it, and both are shown.
- priority_queue<T> pq(otherPriorityQueue);
- Construct pq as a copy of otherPriorityQueue,
whose component type must be T.
- priority_queue<T> pq = otherPriorityQueue;
- Copy constructor (alternate usage syntax).
Destructor
Any priority_queue will have a container data member (by default, a
deque) which will hold its elements. That data member will have its own
destructor which will automatically be invoked when the priority_queue
goes out of scope.
Assignment operator
- pq1 = pq2
- Assign pq2 to pq1, and return the common value.
The priority_queue on the left of an assignment receives the values
and size of the one on the right.
- pq.top()
- Return a reference (or const_reference) to the
component of pq with the highest priority.
- pq.size()
- Return a value of type size_type giving the number of
values currently in pq.
- pq.empty()
- Return true if pq is empty (contains zero
values); otherwise return false.
- pq.push(val)
- Add val to pq, increasing the size of
pq by one.
- pq.pop()
- Delete the value of pq with the highest priority,
decreasing the size of pq by one.
- Implementation
- Standard C++ does not say how the STL containers and algorithms
must be implemented. It does, however, state certain constraints,
such as complexity constraints, to which each implementation must
adhere. Thus it is much better to base your programs on the STL's
performance guarantees, rather than upon any assumption about how a
particular feature, like the priority_queue class, may be
implemented. The priority_quqeue container adaptor is based by
default on the vector. A deque could also be used, since both the
vector and the deque provide the push_back(),
pop_back() and front() operations that are
necessary to support the priority_queu interface. Of course the list
provides these operations as well, but the additional requirement of
random acces, whcih is necessary for sorting the values (and which is
done by the STL heap algorithms), elminates the list as a possible
underlying container.
All programs have been compiled and run successfully under Microsoft
Visual Studio .NET 2005, unless otherwise noted.
- priority_queue01.cpp
| Windows_executable
| program_output
(text)
- Illustrates a simple priority queue of integers, including a
default constructor, a copy constructor, and the push(), pop(),
top(), empty() and size() member functions of the STL priority_queue
interface.
- priority_queue02.cpp
| Windows_executable
| program_output
(text)
- Illustrates two constructors of the STL priority-queue class, and
the assignment of one priority_queue object to another.
- priority_queue03.cpp
| Windows_executable
| program_output
(text)
- Illustrates how to define a priority_queue object with the
priority determined by a built-in "function object", and also how to
alter the underlying container used by the priority_queue
object.
- priority_queue04.cpp
| Windows_executable
| program_output
(text)
- Illustrates how not to access the components of a
priority queue.
- priority_queue05.cpp
| Windows_executable
| program_output
(text)
- Illustrates a simple priority queue of class objects, in which
the priority has been defined by overloading "operator<".
- priority_queue06.cpp
| Windows_executable
| program_output
(text)
- Illustrates a simple priority queue of class objects, in which
the priority has been defined by overloading "operator>" and using
this in conjuction with the built-in functor template class
"greater<>".
Template specification for the priority_queue class
template<class T,
class Allocator = allocator<T> >
class priority_queue { ... }
Default Constructor
explicit priority_queue(const Container& c = Container());
Copy Constructor
priority_queue(const Container& otherContainer);
Destructor
~priority_queue();
empty
bool empty() const;
pop
void pop();
push
void push(const T& val);
size
size_type size() const;
top
T& top() const;
const T& top() const;