stl_queue.h

mingw32.rar

   *  @brief  Queue equality comparison.
   *  @param  x  A %queue.
   *  @param  y  A %queue of the same type as @a x.
   *  @return  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.
  */
  template<typename _Tp, typename _Sequence>
    inline bool
    operator==(const queue<_Tp,_Sequence>& __x,
	       const queue<_Tp,_Sequence>& __y)
    { return __x.c == __y.c; }

  /**
   *  @brief  Queue ordering relation.
   *  @param  x  A %queue.
   *  @param  y  A %queue of the same type as @a x.
   *  @return  True iff @a x is lexicographically less than @a 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 @c <, and
   *  std::lexicographical_compare() is usually used to make the
   *  determination.
  */
  template<typename _Tp, typename _Sequence>
    inline bool
    operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
    { return __x.c < __y.c; }

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

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

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

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

  /**
   *  @brief  A standard container automatically sorting its contents.
   *
   *  @ingroup Containers
   *  @ingroup Sequences
   *
   *  This is not a true container, but an @e adaptor.  It holds
   *  another container, and provides a wrapper interface to that
   *  container.  The wrapper is what enforces sorting and
   *  first-in-first-out %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 @c front(), @c push_back, @c 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 @c less<value_type> but
   *  can be anything defining a strict weak ordering.
   *
   *  Members not found in "normal" containers are @c container_type,
   *  which is a typedef for the second Sequence parameter, and @c
   *  push, @c pop, and @c top, which are standard %queue/FIFO
   *  operations.
   *
   *  @note No equality/comparison operators are provided for
   *  %priority_queue.
   *
   *  @note 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?)
  */
  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:
      /**
       *  @brief  Default constructor creates no elements.
       */
      explicit
      priority_queue(const _Compare& __x = _Compare(),
		     const _Sequence& __s = _Sequence())
      : c(__s), comp(__x)
      { std::make_heap(c.begin(), c.end(), comp); }

      /**
       *  @brief  Builds a %queue from a range.
       *  @param  first  An input iterator.
       *  @param  last  An input iterator.
       *  @param  x  A comparison functor describing a strict weak ordering.
       *  @param  s  An initial sequence with which to start.
       *
       *  Begins by copying @a s, inserting a copy of the elements
       *  from @a [first,last) into the copy of @a s, then ordering
       *  the copy according to @a x.
       *
       *  For more information on function objects, see the
       *  documentation on @link s20_3_1_base functor base
       *  classes@endlink.
       */
      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);
	}

      /**
       *  Returns true if the %queue is empty.
       */
      bool
      empty() const { return c.empty(); }

      /**  Returns the number of elements in the %queue.  */
      size_type
      size() const { return c.size(); }

      /**
       *  Returns a read-only (constant) reference to the data at the first
       *  element of the %queue.
       */
      const_reference
      top() const
      {
	__glibcxx_requires_nonempty();
	return c.front();
      }

      /**
       *  @brief  Add data to the %queue.
       *  @param  x  Data to be added.
       *
       *  This is a typical %queue operation.
       *  The time complexity of the operation depends on the underlying
       *  sequence.
       */
      void
      push(const value_type& __x)
      {
	try
        {
          c.push_back(__x);
          std::push_heap(c.begin(), c.end(), comp);
        }
	catch(...)
        {
          c.clear();
          __throw_exception_again;
        }
      }

      /**
       *  @brief  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.
       */
      void
      pop()
      {
	__glibcxx_requires_nonempty();
	try
        {
          std::pop_heap(c.begin(), c.end(), comp);
          c.pop_back();
        }
	catch(...)
        {
          c.clear();
          __throw_exception_again;
        }
      }
    };

  // No equality/comparison operators are provided for priority_queue.
} // namespace std

#endif /* _QUEUE_H */