<queue>
Include the STL
standard header <queue>
to define the template classes priority_queue
and
queue
, and several supporting templates.
namespace std { template<class Ty, class Container> class queue; template<class Ty, class Container, class Pr> class priority_queue; // TEMPLATE FUNCTIONS template<class Ty, class Container> bool operator==(const queue<Ty, Container>& left, const queue<Ty, Container>&); template<class Ty, class Container> bool operator!=(const queue<Ty, Container>& left, const queue<Ty, Container>&); template<class Ty, class Container> bool operator<(const queue<Ty, Container>& left, const queue<Ty, Container>&); template<class Ty, class Container> bool operator>(const queue<Ty, Container>& left, const queue<Ty, Container>&); template<class Ty, class Container> bool operator<=(const queue<Ty, Container>& left, const queue<Ty, Container>&); template<class Ty, class Container> bool operator>=(const queue<Ty, Container>& left, const queue<Ty, Container>&); };
operator!=
template<class Ty, class Container> bool operator!=(const queue <Ty, Container>& left, const queue <Ty, Container>& right);
The template function returns !(left == right)
.
operator==
template<class Ty, class Container> bool operator==(const queue <Ty, Container>& left, const queue <Ty, Container>& right);
The template function overloads operator==
to compare
two objects of template class
queue
. The function returns
left.c == right.c
.
operator<
template<class Ty, class Container> bool operator<(const queue <Ty, Container>& left, const queue <Ty, Container>& right);
The template function overloads operator<
to compare
two objects of template class
queue
. The function returns
left.c < right.c
.
operator<=
template<class Ty, class Container> bool operator<=(const queue <Ty, Container>& left, const queue <Ty, Container>& right);
The template function returns !(right < left)
.
operator>
template<class Ty, class Container> bool operator>(const queue <Ty, Container>& left, const queue <Ty, Container>& right);
The template function returns right < left
.
operator>=
template<class Ty, class Container> bool operator>=(const queue <Ty, Container>& left, const queue <Ty, Container>& right);
The template function returns !(left < right)
.
priority_queue
template<class Ty, class Container = vector<Ty>, class Pr = less<typename Container::value_type> > class priority_queue { public: typedef Container container_type; typedef typename Container::value_type value_type; typedef typename Container::size_type size_type; priority_queue(); explicit priority_queue(const Pr& pred); priority_queue(const Pr& pred, const container_type& cont); priority_queue(const priority_queue& right); template<class InIt> priority_queue(InIt first, InIt last); template<class InIt> priority_queue(InIt first, InIt last, const Pr& pred); template<class InIt> priority_queue(InIt first, InIt last, const Pr& pred, const container_type& cont); bool empty() const; size_type size() const; const value_type& top() const; void push(const value_type& val); void pop(); protected: Container c; Pr comp; };
The template class describes an object that controls a
varying-length sequence of elements.
The object allocates and frees storage for the sequence it controls
through a protected object named
c
,
of class Container
.
The type Ty
of elements in the controlled sequence must match
value_type
.
The sequence is ordered using a protected object named
comp
.
After each insertion or removal of the top element (at position zero),
for the iterators P0
and Pi
designating elements at positions 0
and I
, comp(*P0, *Pi)
is false.
(For the default template parameter
less<typename Container::value_type>
the top element of the sequence compares largest, or highest priority.)
An object of class Container
must supply
random-access iterators and
several public members defined the same as for
deque
and
vector
(both of which are suitable candidates for class Container
).
The required members are:
typedef Ty value_type; typedef T0 size_type; typedef T1 iterator; Container(); template<class InIt> Container(InIt first, InIt last); template<class InIt> void insert(iterator where, InIt first, InIt last); iterator begin(); iterator end(); bool empty() const; size_type size() const; const value_type& front() const; void push_back(const value_type& val); void pop_back();
Here, T0
and T1
are unspecified types
that meet the stated requirements.
priority_queue::container_type
typedef typename Container::container_type container_type;
The type is a synonym for the template parameter Container
.
priority_queue::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
priority_queue::pop
void pop();
The member function removes the first element of the controlled sequence, which must be non-empty, then reorders it.
priority_queue::priority_queue
priority_queue(); explicit priority_queue(const Pr& pred); priority_queue(const Pr& pred, const container_type& cont); priority_queue(const priority_queue& right); template<class InIt> priority_queue(InIt first, InIt last); template<class InIt> priority_queue(InIt first, InIt last, const Pr& pred); template<class InIt> priority_queue(InIt first, InIt last, const Pr& pred, const container_type& cont);
All constructors with an argument cont
initialize the stored object with
c(cont)
.
The remaining constructors initialize the stored object with
c
, to specify an
empty initial controlled sequence.
The last three constructors then call
c.insert(c.end(), first, last)
.
All constructors also store a function object in
comp
.
The function object comp
is the argument pred
, if present.
For the copy constructor, it is right.comp
.
Otherwise, it is Pr()
.
A non-empty initial controlled sequence is then ordered by calling
make_heap(c.begin(),
c.end(), comp)
.
priority_queue::push
void push(const Ty& val);
The member function inserts an element with value val
at the end of the controlled sequence, then reorders it.
priority_queue::size
size_type size() const;
The member function returns the length of the controlled sequence.
priority_queue::size_type
typedef typename Container::size_type size_type;
The type is a synonym for Container::size_type
.
priority_queue::top
const value_type& top() const;
The member function returns a reference to the first (highest priority) element of the controlled sequence, which must be non-empty.
priority_queue::value_type
typedef typename Container::value_type value_type;
The type is a synonym for Container::value_type
.
queue
template<class Ty, class Container = deque<Ty> > class queue { public: typedef Container container_type; typedef typename Container::value_type value_type; typedef typename Container::size_type size_type; queue(); explicit queue(const container_type& cont); bool empty() const; size_type size() const; value_type& back(); const value_type& back() const; value_type& front(); const value_type& front() const; void push(const value_type& val); void pop(); protected: Container c; };
The template class describes an object that controls a
varying-length sequence of elements.
The object allocates and frees storage for the sequence it controls
through a protected object named
c
,
of class Container
.
The type Ty
of elements in the controlled sequence must match
value_type
.
An object of class Container
must supply
several public members defined the same as for
deque
and
list
(both of which are suitable candidates for class Container
).
The required members are:
typedef Ty value_type; typedef T0 size_type; Container(); bool empty() const; size_type size() const; value_type& front(); const value_type& front() const; value_type& back(); const value_type& back() const; void push_back(const value_type& val); void pop_front(); bool operator==(const Container& cont) const; bool operator!=(const Container& cont) const; bool operator<(const Container& cont) const; bool operator>(const Container& cont) const; bool operator<=(const Container& cont) const; bool operator>=(const Container& cont) const;
Here, T0
is an unspecified type
that meets the stated requirements.
queue::back
value_type& back(); const value_type& back() const;
The member function returns a reference to the last element of the controlled sequence, which must be non-empty.
queue::container_type
typedef Container container_type;
The type is a synonym for the template parameter Container
.
queue::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
queue::front
value_type& front(); const value_type& front() const;
The member function returns a reference to the first element of the controlled sequence, which must be non-empty.
queue::pop
void pop();
The member function removes the first element of the controlled sequence, which must be non-empty.
queue::push
void push(const Ty& val);
The member function inserts an element with value val
at the end of the controlled sequence.
queue::queue
queue(); explicit queue(const container_type& cont);
The first constructor initializes the stored object with
c()
, to specify an
empty initial controlled sequence.
The second constructor initializes the stored object with
c(cont)
, to specify an
initial controlled sequence that is a copy of the sequence controlled
by cont
.
queue::size
size_type size() const;
The member function returns the length of the controlled sequence.
queue::size_type
typedef typename Container::size_type size_type;
The type is a synonym for Container::size_type
.
queue::value_type
typedef typename Container::value_type value_type;
The type is a synonym for Container::value_type
.
See also the Table of Contents and the Index.
Copyright © 1994-2002 by P.J. Plauger. Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights reserved.