priority_queue class template — Priority queue container adapter
template <typename T, typename Container = vector<T>, typename Compare = less<typename Container::value_type> > class priority_queue { public: typedef typename Container::value_type value_type; typedef typename Container::size_type size_type; typedef Container container_type; explicit priority_queue(const Compare& x = Compare( ), const Container& = Container( )); template <class InputIterator> priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare( ), const Container& = Container( )); bool empty( ) const { return c.empty( ); } size_type size( ) const { return c.size( ); } const value_type& top( ) const { return c.front( ); } void push(const value_type& x); void pop( ); protected: Container c; Compare comp; };
The priority_queue
class
template is an adapter for any sequence container that supports
random access, such as deque
and
vector
. (The default is vector
.) The priority queue keeps its
elements in heap order, so it requires a comparator (the Compare
template parameter).
Because priority_queue
is
not itself a standard container, it cannot be used with the standard
algorithms. (In particular, note the lack of begin
and end
member functions.) Thus, the priority_queue
adapter is useful only for
simple needs.
Unlike queue
, priority_queue
has no comparison
operators.
Most of the members of priority_queue
are straightforward
mappings from a simple queue protocol to the underlying container
protocol. The members are:
explicit
priority_queue
(const
Compare&
cmp
=
Compare( ),
const Container& cont = Container( ))
Copies cont
to the
data member c
, copies
cmp
to comp
, and then calls make_heap(c.begin( )
, c.end( )
, comp)
to initialize the priority
queue.
template <class
InputIter>
, priority_queue
(InputIter first
, InputIter last, const
Compare&
cmp
=
Compare( ),
const
Container& cont
=
Container(
))
Copies cont
to the
data member c
, copies
cmp
to comp
, and then adds the elements
[first
, last
) to the container by calling
c.insert(c.end( )
, first
, last)
. Finally, this method
initializes the priority queue by calling make_heap(c.begin( )
, c.end( )
, comp)
.
bool
empty
( )
const
Returns true
if the
priority queue is empty.
void
pop
( )
Erases the largest (last) item from the priority queue
by calling pop_heap
and
then erasing the last element in the container.
void
push
(const value_type&
x)
Inserts x
in the
container and then calls push_heap
to restore priority queue
order.
size_type
size
( )
const
Returns the number of items in the priority queue.
const
value_type&
top
( )
const
Returns the largest (last) item in the priority queue.