stl_queue.h

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

   *  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 lexographically 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::lexographical_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;
    __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
    __glibcpp_class_requires(_Sequence, _SequenceConcept)
    __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept)
    __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
    __glibcpp_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) 
    { 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)
      { 
        c.insert(c.end(), __first, __last);
        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 { 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); 
          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() 
    {
      try 
        {
          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 /* __GLIBCPP_INTERNAL_QUEUE_H */