stl_queue.h File Reference

#include <bits/concept_check.h>
#include <debug/debug.h>

Go to the source code of this file.

Functions
namespace std	_GLIBCXX_VISIBILITY (default)

Detailed Description

This is an internal header file, included by other library headers. Do not attempt to use it directly. {queue}

Function Documentation

namespace std _GLIBCXX_VISIBILITY

(

default

)

A standard container giving FIFO behavior.

Template Parameters

_Tp	Type of element.
_Sequence	Type of underlying sequence, defaults to deque<_Tp>.

Meets many of the requirements of a container, but does not define anything to do with iterators. Very few of the other standard container interfaces are defined.

This is not a true container, but an adaptor. It holds another container, and provides a wrapper interface to that container. The wrapper is what enforces strict first-in-first-out queue behavior.

The second template parameter defines the type of the underlying sequence/container. It defaults to std::deque, but it can be any type that supports front, back, push_back, and pop_front, such as std::list or an appropriate user-defined type.

Members not found in normal containers are container_type, which is a typedef for the second Sequence parameter, and push and pop, which are standard queue/FIFO operations.

'c' is the underlying container. Maintainers wondering why this isn't uglified as per style guidelines should note that this name is specified in the standard, [23.2.3.1]. (Why? Presumably for the same reason that it's protected instead of private: to allow derivation. But none of the other containers allow for derivation. Odd.)

Default constructor creates no elements.

Returns true if the queue is empty.

Returns the number of elements in the queue.

Returns a read/write reference to the data at the first element of the queue.

Returns a read-only (constant) reference to the data at the first element of the queue.

Returns a read/write reference to the data at the last element of the queue.

Returns a read-only (constant) reference to the data at the last element of the queue.

Add data to the end of the queue.

Parameters

__x	Data to be added.

This is a typical queue operation. The function creates an element at the end of the queue and assigns the given data to it. The time complexity of the operation depends on the underlying sequence.

Removes first element.

This is a typical queue operation. It shrinks the queue by one. The time complexity of the operation depends on the underlying sequence.

Note that no data is returned, and if the first element's data is needed, it should be retrieved before pop() is called.

Queue equality comparison.

Parameters

__x	A queue.
__y	A queue of the same type as __x.

Returns

True iff the size and elements of the queues are equal.

This is an equivalence relation. Complexity and semantics depend on the underlying sequence type, but the expected rules are: this relation is linear in the size of the sequences, and queues are considered equivalent if their sequences compare equal.

Queue ordering relation.

Parameters

__x	A queue.
__y	A queue of the same type as x.

Returns

True iff __x is lexicographically less than __y.

This is an total ordering relation. Complexity and semantics depend on the underlying sequence type, but the expected rules are: this relation is linear in the size of the sequences, the elements must be comparable with <, and std::lexicographical_compare() is usually used to make the determination.

Based on operator==

Based on operator<

Based on operator<

Based on operator<

A standard container automatically sorting its contents.

Template Parameters

_Tp	Type of element.
_Sequence	Type of underlying sequence, defaults to vector<_Tp>.
_Compare	Comparison function object type, defaults to less<_Sequence::value_type>.

This is not a true container, but an adaptor. It holds another container, and provides a wrapper interface to that container. The wrapper is what enforces priority-based sorting and queue behavior. Very few of the standard container/sequence interface requirements are met (e.g., iterators).

The second template parameter defines the type of the underlying sequence/container. It defaults to std::vector, but it can be any type that supports front(), push_back, pop_back, and random-access iterators, such as std::deque or an appropriate user-defined type.

The third template parameter supplies the means of making priority comparisons. It defaults to less<value_type> but can be anything defining a strict weak ordering.

Members not found in normal containers are container_type, which is a typedef for the second Sequence parameter, and push, pop, and top, which are standard queue operations.

Note

No equality/comparison operators are provided for priority_queue.

Sorting of the elements takes place as they are added to, and removed from, the priority_queue using the priority_queue's member functions. If you access the elements by other means, and change their data such that the sorting order would be different, the priority_queue will not re-sort the elements for you. (How could it know to do so?)

Default constructor creates no elements.

Builds a queue from a range.

Parameters

__first	An input iterator.
__last	An input iterator.
__x	A comparison functor describing a strict weak ordering.
__s	An initial sequence with which to start.

Begins by copying __s, inserting a copy of the elements from [first,last) into the copy of __s, then ordering the copy according to __x.

For more information on function objects, see the documentation on functor base classes.

Returns true if the queue is empty.

Returns the number of elements in the queue.

Returns a read-only (constant) reference to the data at the first element of the queue.

Add data to the queue.

Parameters

__x	Data to be added.

This is a typical queue operation. The time complexity of the operation depends on the underlying sequence.

Removes first element.

This is a typical queue operation. It shrinks the queue by one. The time complexity of the operation depends on the underlying sequence.

Note that no data is returned, and if the first element's data is needed, it should be retrieved before pop() is called.

{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  template<typename _Tp, typename _Sequence = deque<_Tp> >
    class queue
    {
      // concept requirements
      typedef typename _Sequence::value_type _Sequence_value_type;
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
      __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)

      template<typename _Tp1, typename _Seq1>
        friend bool
        operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);

      template<typename _Tp1, typename _Seq1>
        friend bool
        operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);

    public:
      typedef typename _Sequence::value_type                value_type;
      typedef typename _Sequence::reference                 reference;
      typedef typename _Sequence::const_reference           const_reference;
      typedef typename _Sequence::size_type                 size_type;
      typedef          _Sequence                            container_type;

    protected:
      _Sequence c;

    public:
#if __cplusplus < 201103L
      explicit
      queue(const _Sequence& __c = _Sequence())
      : c(__c) { }
#else
      explicit
      queue(const _Sequence& __c)
      : c(__c) { }

      explicit
      queue(_Sequence&& __c = _Sequence())
      : c(std::move(__c)) { }
#endif

      bool
      empty() const
      { return c.empty(); }

      size_type
      size() const
      { return c.size(); }

      reference
      front()
      {
    __glibcxx_requires_nonempty();
    return c.front();
      }

      const_reference
      front() const
      {
    __glibcxx_requires_nonempty();
    return c.front();
      }

      reference
      back()
      {
    __glibcxx_requires_nonempty();
    return c.back();
      }

      const_reference
      back() const
      {
    __glibcxx_requires_nonempty();
    return c.back();
      }

      void
      push(const value_type& __x)
      { c.push_back(__x); }

#if __cplusplus >= 201103L
      void
      push(value_type&& __x)
      { c.push_back(std::move(__x)); }

      template<typename... _Args>
        void
        emplace(_Args&&... __args)
    { c.emplace_back(std::forward<_Args>(__args)...); }
#endif

      void
      pop()
      {
    __glibcxx_requires_nonempty();
    c.pop_front();
      }

#if __cplusplus >= 201103L
      void
      swap(queue& __q)
      noexcept(noexcept(swap(c, __q.c)))
      {
    using std::swap;
    swap(c, __q.c);
      }
#endif
    };

  template<typename _Tp, typename _Seq>
    inline bool
    operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
    { return __x.c == __y.c; }

  template<typename _Tp, typename _Seq>
    inline bool
    operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
    { return __x.c < __y.c; }

  template<typename _Tp, typename _Seq>
    inline bool
    operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
    { return !(__x == __y); }

  template<typename _Tp, typename _Seq>
    inline bool
    operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
    { return __y < __x; }

  template<typename _Tp, typename _Seq>
    inline bool
    operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
    { return !(__y < __x); }

  template<typename _Tp, typename _Seq>
    inline bool
    operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
    { return !(__x < __y); }

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Seq>
    inline void
    swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
    noexcept(noexcept(__x.swap(__y)))
    { __x.swap(__y); }

  template<typename _Tp, typename _Seq, typename _Alloc>
    struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
    : public uses_allocator<_Seq, _Alloc>::type { };
#endif

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {
      // concept requirements
      typedef typename _Sequence::value_type _Sequence_value_type;
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires(_Sequence, _SequenceConcept)
      __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
      __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
                _BinaryFunctionConcept)

    public:
      typedef typename _Sequence::value_type                value_type;
      typedef typename _Sequence::reference                 reference;
      typedef typename _Sequence::const_reference           const_reference;
      typedef typename _Sequence::size_type                 size_type;
      typedef          _Sequence                            container_type;

    protected:
      //  See queue::c for notes on these names.
      _Sequence  c;
      _Compare   comp;

    public:
#if __cplusplus < 201103L
      explicit
      priority_queue(const _Compare& __x = _Compare(),
             const _Sequence& __s = _Sequence())
      : c(__s), comp(__x)
      { std::make_heap(c.begin(), c.end(), comp); }
#else
      explicit
      priority_queue(const _Compare& __x,
             const _Sequence& __s)
      : c(__s), comp(__x)
      { std::make_heap(c.begin(), c.end(), comp); }

      explicit
      priority_queue(const _Compare& __x = _Compare(),
             _Sequence&& __s = _Sequence())
      : c(std::move(__s)), comp(__x)
      { std::make_heap(c.begin(), c.end(), comp); }
#endif

#if __cplusplus < 201103L
      template<typename _InputIterator>
        priority_queue(_InputIterator __first, _InputIterator __last,
               const _Compare& __x = _Compare(),
               const _Sequence& __s = _Sequence())
    : c(__s), comp(__x)
        {
      __glibcxx_requires_valid_range(__first, __last);
      c.insert(c.end(), __first, __last);
      std::make_heap(c.begin(), c.end(), comp);
    }
#else
      template<typename _InputIterator>
        priority_queue(_InputIterator __first, _InputIterator __last,
               const _Compare& __x,
               const _Sequence& __s)
    : c(__s), comp(__x)
        {
      __glibcxx_requires_valid_range(__first, __last);
      c.insert(c.end(), __first, __last);
      std::make_heap(c.begin(), c.end(), comp);
    }

      template<typename _InputIterator>
        priority_queue(_InputIterator __first, _InputIterator __last,
               const _Compare& __x = _Compare(),
               _Sequence&& __s = _Sequence())
    : c(std::move(__s)), comp(__x)
        {
      __glibcxx_requires_valid_range(__first, __last);
      c.insert(c.end(), __first, __last);
      std::make_heap(c.begin(), c.end(), comp);
    }
#endif

      bool
      empty() const
      { return c.empty(); }

      size_type
      size() const
      { return c.size(); }

      const_reference
      top() const
      {
    __glibcxx_requires_nonempty();
    return c.front();
      }

      void
      push(const value_type& __x)
      {
    c.push_back(__x);
    std::push_heap(c.begin(), c.end(), comp);
      }

#if __cplusplus >= 201103L
      void
      push(value_type&& __x)
      {
    c.push_back(std::move(__x));
    std::push_heap(c.begin(), c.end(), comp);
      }

      template<typename... _Args>
        void
        emplace(_Args&&... __args)
    {
      c.emplace_back(std::forward<_Args>(__args)...);
      std::push_heap(c.begin(), c.end(), comp);
    }
#endif

      void
      pop()
      {
    __glibcxx_requires_nonempty();
    std::pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
      }

#if __cplusplus >= 201103L
      void
      swap(priority_queue& __pq)
      noexcept(noexcept(swap(c, __pq.c)) && noexcept(swap(comp, __pq.comp)))
      {
    using std::swap;
    swap(c, __pq.c);
    swap(comp, __pq.comp);
      }
#endif
    };

  // No equality/comparison operators are provided for priority_queue.

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Sequence, typename _Compare>
    inline void
    swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
     priority_queue<_Tp, _Sequence, _Compare>& __y)
    noexcept(noexcept(__x.swap(__y)))
    { __x.swap(__y); }

  template<typename _Tp, typename _Sequence, typename _Compare,
       typename _Alloc>
    struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
    : public uses_allocator<_Sequence, _Alloc>::type { };
#endif

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace