stl_queue.h

Go to the documentation of this file.
00001 // Queue implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996,1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /** @file stl_queue.h
00057  *  This is an internal header file, included by other library headers.
00058  *  You should not attempt to use it directly.
00059  */
00060 
00061 #ifndef __GLIBCPP_INTERNAL_QUEUE_H
00062 #define __GLIBCPP_INTERNAL_QUEUE_H
00063 
00064 #include <bits/concept_check.h>
00065 
00066 namespace std
00067 {
00068   // Forward declarations of operators < and ==, needed for friend declaration.
00069   
00070   template <typename _Tp, typename _Sequence = deque<_Tp> >
00071   class queue;
00072   
00073   template <typename _Tp, typename _Seq>
00074   inline bool operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
00075   
00076   template <typename _Tp, typename _Seq>
00077   inline bool operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
00078   
00079   
00080   /**
00081    *  @brief  A standard container giving FIFO behavior.
00082    *
00083    *  @ingroup Containers
00084    *  @ingroup Sequences
00085    *
00086    *  Meets many of the requirements of a
00087    *  <a href="tables.html#65">container</a>,
00088    *  but does not define anything to do with iterators.  Very few of the
00089    *  other standard container interfaces are defined.
00090    *
00091    *  This is not a true container, but an @e adaptor.  It holds another
00092    *  container, and provides a wrapper interface to that container.  The
00093    *  wrapper is what enforces strict first-in-first-out %queue behavior.
00094    *
00095    *  The second template parameter defines the type of the underlying
00096    *  sequence/container.  It defaults to std::deque, but it can be any type
00097    *  that supports @c front, @c back, @c push_back, and @c pop_front,
00098    *  such as std::list or an appropriate user-defined type.
00099    *
00100    *  Members not found in "normal" containers are @c container_type,
00101    *  which is a typedef for the second Sequence parameter, and @c push and
00102    *  @c pop, which are standard %queue/FIFO operations.
00103   */
00104   template <typename _Tp, typename _Sequence>
00105     class queue
00106   {
00107     // concept requirements
00108     typedef typename _Sequence::value_type _Sequence_value_type;
00109     __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00110     __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00111     __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept)
00112     __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00113   
00114     template <typename _Tp1, typename _Seq1>
00115     friend bool operator== (const queue<_Tp1, _Seq1>&,
00116                             const queue<_Tp1, _Seq1>&);
00117     template <typename _Tp1, typename _Seq1>
00118     friend bool operator< (const queue<_Tp1, _Seq1>&,
00119                            const queue<_Tp1, _Seq1>&);
00120   
00121   public:
00122     typedef typename _Sequence::value_type                value_type;
00123     typedef typename _Sequence::reference                 reference;
00124     typedef typename _Sequence::const_reference           const_reference;
00125     typedef typename _Sequence::size_type                 size_type;
00126     typedef          _Sequence                            container_type;
00127   
00128   protected:
00129     /**
00130      *  'c' is the underlying container.  Maintainers wondering why this isn't
00131      *  uglified as per style guidelines should note that this name is
00132      *  specified in the standard, [23.2.3.1].  (Why?  Presumably for the same
00133      *  reason that it's protected instead of private:  to allow derivation.
00134      *  But none of the other containers allow for derivation.  Odd.)
00135     */
00136     _Sequence c;
00137   
00138   public:
00139     /**
00140      *  @brief  Default constructor creates no elements.
00141     */
00142     explicit
00143     queue(const _Sequence& __c = _Sequence())
00144     : c(__c) {}
00145   
00146     /**
00147      *  Returns true if the %queue is empty.
00148     */
00149     bool
00150     empty() const { return c.empty(); }
00151   
00152     /**  Returns the number of elements in the %queue.  */
00153     size_type
00154     size() const { return c.size(); }
00155   
00156     /**
00157      *  Returns a read/write reference to the data at the first element of the
00158      *  %queue.
00159     */
00160     reference
00161     front() { return c.front(); }
00162   
00163     /**
00164      *  Returns a read-only (constant) reference to the data at the first
00165      *  element of the %queue.
00166     */
00167     const_reference
00168     front() const { return c.front(); }
00169   
00170     /**
00171      *  Returns a read/write reference to the data at the last element of the
00172      *  %queue.
00173     */
00174     reference
00175     back() { return c.back(); }
00176   
00177     /**
00178      *  Returns a read-only (constant) reference to the data at the last
00179      *  element of the %queue.
00180     */
00181     const_reference
00182     back() const { return c.back(); }
00183   
00184     /**
00185      *  @brief  Add data to the end of the %queue.
00186      *  @param  x  Data to be added.
00187      *
00188      *  This is a typical %queue operation.  The function creates an element at
00189      *  the end of the %queue and assigns the given data to it.
00190      *  The time complexity of the operation depends on the underlying
00191      *  sequence.
00192     */
00193     void
00194     push(const value_type& __x) { c.push_back(__x); }
00195   
00196     /**
00197      *  @brief  Removes first element.
00198      *
00199      *  This is a typical %queue operation.  It shrinks the %queue by one.
00200      *  The time complexity of the operation depends on the underlying
00201      *  sequence.
00202      *
00203      *  Note that no data is returned, and if the first element's data is
00204      *  needed, it should be retrieved before pop() is called.
00205     */
00206     void
00207     pop() { c.pop_front(); }
00208   };
00209   
00210   
00211   /**
00212    *  @brief  Queue equality comparison.
00213    *  @param  x  A %queue.
00214    *  @param  y  A %queue of the same type as @a x.
00215    *  @return  True iff the size and elements of the queues are equal.
00216    *
00217    *  This is an equivalence relation.  Complexity and semantics depend on the
00218    *  underlying sequence type, but the expected rules are:  this relation is
00219    *  linear in the size of the sequences, and queues are considered equivalent
00220    *  if their sequences compare equal.
00221   */
00222   template <typename _Tp, typename _Sequence>
00223     inline bool 
00224     operator==(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00225     { return __x.c == __y.c; }
00226   
00227   /**
00228    *  @brief  Queue ordering relation.
00229    *  @param  x  A %queue.
00230    *  @param  y  A %queue of the same type as @a x.
00231    *  @return  True iff @a x is lexographically less than @a y.
00232    *
00233    *  This is an total ordering relation.  Complexity and semantics depend on
00234    *  the underlying sequence type, but the expected rules are:  this relation
00235    *  is linear in the size of the sequences, the elements must be comparable
00236    *  with @c <, and std::lexographical_compare() is usually used to make the
00237    *  determination.
00238   */
00239   template <typename _Tp, typename _Sequence>
00240     inline bool
00241     operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00242     { return __x.c < __y.c; }
00243   
00244   /// Based on operator==
00245   template <typename _Tp, typename _Sequence>
00246     inline bool
00247     operator!=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00248     { return !(__x == __y); }
00249   
00250   /// Based on operator<
00251   template <typename _Tp, typename _Sequence>
00252     inline bool 
00253     operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00254     { return __y < __x; }
00255   
00256   /// Based on operator<
00257   template <typename _Tp, typename _Sequence>
00258     inline bool 
00259     operator<=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00260     { return !(__y < __x); }
00261   
00262   /// Based on operator<
00263   template <typename _Tp, typename _Sequence>
00264     inline bool 
00265     operator>=(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00266     { return !(__x < __y); }
00267   
00268   
00269   /**
00270    *  @brief  A standard container automatically sorting its contents.
00271    *
00272    *  @ingroup Containers
00273    *  @ingroup Sequences
00274    *
00275    *  This is not a true container, but an @e adaptor.  It holds another
00276    *  container, and provides a wrapper interface to that container.  The
00277    *  wrapper is what enforces sorting and first-in-first-out %queue behavior.
00278    *  Very few of the standard container/sequence interface requirements are
00279    *  met (e.g., iterators).
00280    *
00281    *  The second template parameter defines the type of the underlying
00282    *  sequence/container.  It defaults to std::vector, but it can be any type
00283    *  that supports @c front(), @c push_back, @c pop_back, and random-access
00284    *  iterators, such as std::deque or an appropriate user-defined type.
00285    *
00286    *  The third template parameter supplies the means of making priority
00287    *  comparisons.  It defaults to @c less<value_type> but can be anything
00288    *  defining a strict weak ordering.
00289    *
00290    *  Members not found in "normal" containers are @c container_type,
00291    *  which is a typedef for the second Sequence parameter, and @c push,
00292    *  @c pop, and @c top, which are standard %queue/FIFO operations.
00293    *
00294    *  @note  No equality/comparison operators are provided for %priority_queue.
00295    *
00296    *  @note  Sorting of the elements takes place as they are added to, and
00297    *         removed from, the %priority_queue using the %priority_queue's
00298    *         member functions.  If you access the elements by other means, and
00299    *         change their data such that the sorting order would be different,
00300    *         the %priority_queue will not re-sort the elements for you.  (How
00301    *         could it know to do so?)
00302   */
00303   template <typename _Tp, typename _Sequence = vector<_Tp>,
00304             typename _Compare  = less<typename _Sequence::value_type> >
00305     class priority_queue
00306   {
00307     // concept requirements
00308     typedef typename _Sequence::value_type _Sequence_value_type;
00309     __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00310     __glibcpp_class_requires(_Sequence, _SequenceConcept)
00311     __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept)
00312     __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00313     __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept)
00314   
00315   public:
00316     typedef typename _Sequence::value_type                value_type;
00317     typedef typename _Sequence::reference                 reference;
00318     typedef typename _Sequence::const_reference           const_reference;
00319     typedef typename _Sequence::size_type                 size_type;
00320     typedef          _Sequence                            container_type;
00321   
00322   protected:
00323     //  See queue::c for notes on these names.
00324     _Sequence  c;
00325     _Compare   comp;
00326   
00327   public:
00328     /**
00329      *  @brief  Default constructor creates no elements.
00330     */
00331     explicit
00332     priority_queue(const _Compare& __x = _Compare(),
00333                    const _Sequence& __s = _Sequence()) 
00334     : c(__s), comp(__x) 
00335     { make_heap(c.begin(), c.end(), comp); }
00336   
00337     /**
00338      *  @brief  Builds a %queue from a range.
00339      *  @param  first  An input iterator.
00340      *  @param  last  An input iterator.
00341      *  @param  x  A comparison functor describing a strict weak ordering.
00342      *  @param  s  An initial sequence with which to start.
00343      * 
00344      *  Begins by copying @a s, inserting a copy of the elements from
00345      *  @a [first,last) into the copy of @a s, then ordering the copy
00346      *  according to @a x.
00347      *
00348      *  For more information on function objects, see the documentation on
00349      *  @link s20_3_1_base functor base classes@endlink.
00350     */
00351     template <typename _InputIterator>
00352       priority_queue(_InputIterator __first, _InputIterator __last,
00353                      const _Compare& __x = _Compare(),
00354                      const _Sequence& __s = _Sequence())
00355       : c(__s), comp(__x)
00356       { 
00357         c.insert(c.end(), __first, __last);
00358         make_heap(c.begin(), c.end(), comp);
00359       }
00360   
00361     /**
00362      *  Returns true if the %queue is empty.
00363     */
00364     bool
00365     empty() const { return c.empty(); }
00366   
00367     /**  Returns the number of elements in the %queue.  */
00368     size_type
00369     size() const { return c.size(); }
00370   
00371     /**
00372      *  Returns a read-only (constant) reference to the data at the first
00373      *  element of the %queue.
00374     */
00375     const_reference
00376     top() const { return c.front(); }
00377   
00378     /**
00379      *  @brief  Add data to the %queue.
00380      *  @param  x  Data to be added.
00381      *
00382      *  This is a typical %queue operation.
00383      *  The time complexity of the operation depends on the underlying
00384      *  sequence.
00385     */
00386     void 
00387     push(const value_type& __x) 
00388     {
00389       try 
00390         {
00391           c.push_back(__x); 
00392           push_heap(c.begin(), c.end(), comp);
00393         }
00394       catch(...)
00395         {
00396           c.clear();
00397           __throw_exception_again; 
00398         }
00399     }
00400   
00401     /**
00402      *  @brief  Removes first element.
00403      *
00404      *  This is a typical %queue operation.  It shrinks the %queue by one.
00405      *  The time complexity of the operation depends on the underlying
00406      *  sequence.
00407      *
00408      *  Note that no data is returned, and if the first element's data is
00409      *  needed, it should be retrieved before pop() is called.
00410     */
00411     void 
00412     pop() 
00413     {
00414       try 
00415         {
00416           pop_heap(c.begin(), c.end(), comp);
00417           c.pop_back();
00418         }
00419       catch(...)
00420         {
00421           c.clear();
00422           __throw_exception_again; 
00423         }
00424     }
00425   };
00426   
00427   // No equality/comparison operators are provided for priority_queue.
00428 } // namespace std
00429 
00430 #endif /* __GLIBCPP_INTERNAL_QUEUE_H */

Generated on Thu Feb 10 23:22:59 2005 for libstdc++-v3 Source by  doxygen 1.4.0