13.40 <queue>

The <queue> header declares the queue and priority_queue container adapters. These class templates are not containers in their own rights, but they adapt containers to present the behavior of a queue or priority queue.

A queue is a sequence of items that supports insertion at one end and removal from the other end. Because the first item inserted into a queue is the first item removed, a queue is sometimes called a FIFO (first-in, first-out) container.

Instead of preserving FIFO order, a priority queue maintains heap order, which ensures that the largest item is always first. In strict C++ terms, the first item in a priority queue is not less than any other item in the queue. This is called the "largest" item, but you can also think of it as the most important item or the one with the highest priority.

See Chapter 10 for information about containers.

template <typename T, typename Container>
bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);

The == operator compares two queues for equality by comparing the adapted containers (e.g., the return value is x.c == y.c).

template <typename T, typename Container>
bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);

The != operator compares two queues for inequality by comparing the adapted containers (e.g., the return value is x.c != y.c).

template <typename T, typename Container>
bool operator<(const queue<T, Container>& x, const queue<T, Container>& y);

The < operator compares two queues by comparing the adapted containers (e.g., the return value is x.c < y.c).

template <typename T, typename Container>
bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);

The <= operator compares two queues by comparing the adapted containers (e.g., the return value is x.c <= y.c).

template <typename T, typename Container>
bool operator>(const queue<T, Container>& x, const queue<T, Container>& y);

The > operator compares two queues by comparing the adapted containers (e.g., the return value is x.c >= y.c).

template <typename T, typename Container>
bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);

The >= operator compares two queues by comparing the adapted containers (e.g., the return value is x.c >= y.c).

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.

See Also

make_heap, pop_heap, and push_heap in <algorithm>, list in <list>, vector in <vector>

template <class T, class Container = deque<T> >
class queue {
public:
  typedef typename Container::value_type value_type;
  typedef typename Container::size_type size_type;
  typedef Container container_type;
   
  explicit queue(const Container& = Container(  ));
  bool empty(  ) const { return c.empty(  ); }
  size_type size(  ) const { return c.size(  ); }
  value_type& front(  ) { return c.front(  ); }
  const value_type& front(  ) const { return c.front(  ); }
  value_type& back(  ) { return c.back(  ); }
  const value_type& back(  ) const { return c.back(  ); }
  void push(const value_type& x) { c.push_back(x); }
  void pop(  ) { c.pop_front(  ); }
protected:
  Container c;
};

The queue class template is an adapter for any sequence container that supports the front( ), back( ), push_back( ), and pop_front( ) members. See the list and deque class templates for the standard containers that are suitable. (The default is deque.)

Because 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 queue adapter is useful only for simple needs.

Most of the members of queue are straightforward mappings from a simple queue protocol to the underlying container protocol. The members are:

explicit queue(const Container& cont = Container( ))

Takes an existing container cont and copies its contents into the queue. With no argument, the constructor creates a new, empty container for the queue.

value_type& back( )

const value_type& back( ) const

Returns the last item in the queue, that is, the item that was added most recently to the queue.

bool empty( ) const

Returns true if the queue is empty.

value_type& front( )

const value_type& front( ) const

Returns the first item in the queue.

void pop( )

Erases the first item from the queue.

void push(const value_type& x)

Inserts x at the end of the queue.

size_type size( ) const

Returns the number of items in the queue.

See Also

deque in <deque>, list in <list>, stack in <stack>