stl_queue.h

Go to the documentation of this file.
00001 // Queue implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  *
00028  * Copyright (c) 1994
00029  * Hewlett-Packard Company
00030  *
00031  * Permission to use, copy, modify, distribute and sell this software
00032  * and its documentation for any purpose is hereby granted without fee,
00033  * provided that the above copyright notice appear in all copies and
00034  * that both that copyright notice and this permission notice appear
00035  * in supporting documentation.  Hewlett-Packard Company makes no
00036  * representations about the suitability of this software for any
00037  * purpose.  It is provided "as is" without express or implied warranty.
00038  *
00039  *
00040  * Copyright (c) 1996,1997
00041  * Silicon Graphics Computer Systems, Inc.
00042  *
00043  * Permission to use, copy, modify, distribute and sell this software
00044  * and its documentation for any purpose is hereby granted without fee,
00045  * provided that the above copyright notice appear in all copies and
00046  * that both that copyright notice and this permission notice appear
00047  * in supporting documentation.  Silicon Graphics makes no
00048  * representations about the suitability of this software for any
00049  * purpose.  It is provided "as is" without express or implied warranty.
00050  */
00051 
00052 /** @file stl_queue.h
00053  *  This is an internal header file, included by other library headers.
00054  *  You should not attempt to use it directly.
00055  */
00056 
00057 #ifndef _STL_QUEUE_H
00058 #define _STL_QUEUE_H 1
00059 
00060 #include <bits/concept_check.h>
00061 #include <debug/debug.h>
00062 
00063 _GLIBCXX_BEGIN_NAMESPACE(std)
00064 
00065   /**
00066    *  @brief  A standard container giving FIFO behavior.
00067    *
00068    *  @ingroup sequences
00069    *
00070    *  Meets many of the requirements of a
00071    *  <a href="tables.html#65">container</a>,
00072    *  but does not define anything to do with iterators.  Very few of the
00073    *  other standard container interfaces are defined.
00074    *
00075    *  This is not a true container, but an @e adaptor.  It holds another
00076    *  container, and provides a wrapper interface to that container.  The
00077    *  wrapper is what enforces strict first-in-first-out %queue behavior.
00078    *
00079    *  The second template parameter defines the type of the underlying
00080    *  sequence/container.  It defaults to std::deque, but it can be any type
00081    *  that supports @c front, @c back, @c push_back, and @c pop_front,
00082    *  such as std::list or an appropriate user-defined type.
00083    *
00084    *  Members not found in "normal" containers are @c container_type,
00085    *  which is a typedef for the second Sequence parameter, and @c push and
00086    *  @c pop, which are standard %queue/FIFO operations.
00087   */
00088   template<typename _Tp, typename _Sequence = deque<_Tp> >
00089     class queue
00090     {
00091       // concept requirements
00092       typedef typename _Sequence::value_type _Sequence_value_type;
00093       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00094       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00095       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
00096       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00097 
00098       template<typename _Tp1, typename _Seq1>
00099         friend bool
00100         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00101 
00102       template<typename _Tp1, typename _Seq1>
00103         friend bool
00104         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00105 
00106     public:
00107       typedef typename _Sequence::value_type                value_type;
00108       typedef typename _Sequence::reference                 reference;
00109       typedef typename _Sequence::const_reference           const_reference;
00110       typedef typename _Sequence::size_type                 size_type;
00111       typedef          _Sequence                            container_type;
00112 
00113     protected:
00114       /**
00115        *  'c' is the underlying container.  Maintainers wondering why
00116        *  this isn't uglified as per style guidelines should note that
00117        *  this name is specified in the standard, [23.2.3.1].  (Why?
00118        *  Presumably for the same reason that it's protected instead
00119        *  of private: to allow derivation.  But none of the other
00120        *  containers allow for derivation.  Odd.)
00121        */
00122       _Sequence c;
00123 
00124     public:
00125       /**
00126        *  @brief  Default constructor creates no elements.
00127        */
00128 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00129       explicit
00130       queue(const _Sequence& __c = _Sequence())
00131       : c(__c) { }
00132 #else
00133       explicit
00134       queue(const _Sequence& __c)
00135       : c(__c) { }
00136 
00137       explicit
00138       queue(_Sequence&& __c = _Sequence())
00139       : c(std::move(__c)) { }
00140 
00141       queue(queue&& __q)
00142       : c(std::move(__q.c)) { }
00143 
00144       queue&
00145       operator=(queue&& __q)
00146       {
00147     c = std::move(__q.c);
00148     return *this;
00149       }
00150 #endif
00151 
00152       /**
00153        *  Returns true if the %queue is empty.
00154        */
00155       bool
00156       empty() const
00157       { return c.empty(); }
00158 
00159       /**  Returns the number of elements in the %queue.  */
00160       size_type
00161       size() const
00162       { return c.size(); }
00163 
00164       /**
00165        *  Returns a read/write reference to the data at the first
00166        *  element of the %queue.
00167        */
00168       reference
00169       front()
00170       {
00171     __glibcxx_requires_nonempty();
00172     return c.front();
00173       }
00174 
00175       /**
00176        *  Returns a read-only (constant) reference to the data at the first
00177        *  element of the %queue.
00178        */
00179       const_reference
00180       front() const
00181       {
00182     __glibcxx_requires_nonempty();
00183     return c.front();
00184       }
00185 
00186       /**
00187        *  Returns a read/write reference to the data at the last
00188        *  element of the %queue.
00189        */
00190       reference
00191       back()
00192       {
00193     __glibcxx_requires_nonempty();
00194     return c.back();
00195       }
00196 
00197       /**
00198        *  Returns a read-only (constant) reference to the data at the last
00199        *  element of the %queue.
00200        */
00201       const_reference
00202       back() const
00203       {
00204     __glibcxx_requires_nonempty();
00205     return c.back();
00206       }
00207 
00208       /**
00209        *  @brief  Add data to the end of the %queue.
00210        *  @param  x  Data to be added.
00211        *
00212        *  This is a typical %queue operation.  The function creates an
00213        *  element at the end of the %queue and assigns the given data
00214        *  to it.  The time complexity of the operation depends on the
00215        *  underlying sequence.
00216        */
00217       void
00218       push(const value_type& __x)
00219       { c.push_back(__x); }
00220 
00221 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00222       void
00223       push(value_type&& __x)
00224       { c.push_back(std::move(__x)); }
00225 
00226       template<typename... _Args>
00227         void
00228         emplace(_Args&&... __args)
00229     { c.emplace_back(std::forward<_Args>(__args)...); }
00230 #endif
00231 
00232       /**
00233        *  @brief  Removes first element.
00234        *
00235        *  This is a typical %queue operation.  It shrinks the %queue by one.
00236        *  The time complexity of the operation depends on the underlying
00237        *  sequence.
00238        *
00239        *  Note that no data is returned, and if the first element's
00240        *  data is needed, it should be retrieved before pop() is
00241        *  called.
00242        */
00243       void
00244       pop()
00245       {
00246     __glibcxx_requires_nonempty();
00247     c.pop_front();
00248       }
00249 
00250 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00251       void
00252       swap(queue&& __q)
00253       { c.swap(__q.c); }
00254 #endif
00255     };
00256 
00257   /**
00258    *  @brief  Queue equality comparison.
00259    *  @param  x  A %queue.
00260    *  @param  y  A %queue of the same type as @a x.
00261    *  @return  True iff the size and elements of the queues are equal.
00262    *
00263    *  This is an equivalence relation.  Complexity and semantics depend on the
00264    *  underlying sequence type, but the expected rules are:  this relation is
00265    *  linear in the size of the sequences, and queues are considered equivalent
00266    *  if their sequences compare equal.
00267   */
00268   template<typename _Tp, typename _Seq>
00269     inline bool
00270     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00271     { return __x.c == __y.c; }
00272 
00273   /**
00274    *  @brief  Queue ordering relation.
00275    *  @param  x  A %queue.
00276    *  @param  y  A %queue of the same type as @a x.
00277    *  @return  True iff @a x is lexicographically less than @a y.
00278    *
00279    *  This is an total ordering relation.  Complexity and semantics
00280    *  depend on the underlying sequence type, but the expected rules
00281    *  are: this relation is linear in the size of the sequences, the
00282    *  elements must be comparable with @c <, and
00283    *  std::lexicographical_compare() is usually used to make the
00284    *  determination.
00285   */
00286   template<typename _Tp, typename _Seq>
00287     inline bool
00288     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00289     { return __x.c < __y.c; }
00290 
00291   /// Based on operator==
00292   template<typename _Tp, typename _Seq>
00293     inline bool
00294     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00295     { return !(__x == __y); }
00296 
00297   /// Based on operator<
00298   template<typename _Tp, typename _Seq>
00299     inline bool
00300     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00301     { return __y < __x; }
00302 
00303   /// Based on operator<
00304   template<typename _Tp, typename _Seq>
00305     inline bool
00306     operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00307     { return !(__y < __x); }
00308 
00309   /// Based on operator<
00310   template<typename _Tp, typename _Seq>
00311     inline bool
00312     operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00313     { return !(__x < __y); }
00314 
00315 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00316   template<typename _Tp, typename _Seq>
00317     inline void
00318     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
00319     { __x.swap(__y); }
00320 
00321   template<typename _Tp, typename _Seq>
00322     inline void
00323     swap(queue<_Tp, _Seq>&& __x, queue<_Tp, _Seq>& __y)
00324     { __x.swap(__y); }
00325 
00326   template<typename _Tp, typename _Seq>
00327     inline void
00328     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>&& __y)
00329     { __x.swap(__y); }
00330 #endif
00331 
00332   /**
00333    *  @brief  A standard container automatically sorting its contents.
00334    *
00335    *  @ingroup sequences
00336    *
00337    *  This is not a true container, but an @e adaptor.  It holds
00338    *  another container, and provides a wrapper interface to that
00339    *  container.  The wrapper is what enforces priority-based sorting 
00340    *  and %queue behavior.  Very few of the standard container/sequence
00341    *  interface requirements are met (e.g., iterators).
00342    *
00343    *  The second template parameter defines the type of the underlying
00344    *  sequence/container.  It defaults to std::vector, but it can be
00345    *  any type that supports @c front(), @c push_back, @c pop_back,
00346    *  and random-access iterators, such as std::deque or an
00347    *  appropriate user-defined type.
00348    *
00349    *  The third template parameter supplies the means of making
00350    *  priority comparisons.  It defaults to @c less<value_type> but
00351    *  can be anything defining a strict weak ordering.
00352    *
00353    *  Members not found in "normal" containers are @c container_type,
00354    *  which is a typedef for the second Sequence parameter, and @c
00355    *  push, @c pop, and @c top, which are standard %queue operations.
00356    *
00357    *  @note No equality/comparison operators are provided for
00358    *  %priority_queue.
00359    *
00360    *  @note Sorting of the elements takes place as they are added to,
00361    *  and removed from, the %priority_queue using the
00362    *  %priority_queue's member functions.  If you access the elements
00363    *  by other means, and change their data such that the sorting
00364    *  order would be different, the %priority_queue will not re-sort
00365    *  the elements for you.  (How could it know to do so?)
00366   */
00367   template<typename _Tp, typename _Sequence = vector<_Tp>,
00368        typename _Compare  = less<typename _Sequence::value_type> >
00369     class priority_queue
00370     {
00371       // concept requirements
00372       typedef typename _Sequence::value_type _Sequence_value_type;
00373       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00374       __glibcxx_class_requires(_Sequence, _SequenceConcept)
00375       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
00376       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00377       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
00378                 _BinaryFunctionConcept)
00379 
00380     public:
00381       typedef typename _Sequence::value_type                value_type;
00382       typedef typename _Sequence::reference                 reference;
00383       typedef typename _Sequence::const_reference           const_reference;
00384       typedef typename _Sequence::size_type                 size_type;
00385       typedef          _Sequence                            container_type;
00386 
00387     protected:
00388       //  See queue::c for notes on these names.
00389       _Sequence  c;
00390       _Compare   comp;
00391 
00392     public:
00393       /**
00394        *  @brief  Default constructor creates no elements.
00395        */
00396 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00397       explicit
00398       priority_queue(const _Compare& __x = _Compare(),
00399              const _Sequence& __s = _Sequence())
00400       : c(__s), comp(__x)
00401       { std::make_heap(c.begin(), c.end(), comp); }
00402 #else
00403       explicit
00404       priority_queue(const _Compare& __x,
00405              const _Sequence& __s)
00406       : c(__s), comp(__x)
00407       { std::make_heap(c.begin(), c.end(), comp); }
00408 
00409       explicit
00410       priority_queue(const _Compare& __x = _Compare(),
00411              _Sequence&& __s = _Sequence())
00412       : c(std::move(__s)), comp(__x)
00413       { std::make_heap(c.begin(), c.end(), comp); }
00414 #endif
00415 
00416       /**
00417        *  @brief  Builds a %queue from a range.
00418        *  @param  first  An input iterator.
00419        *  @param  last  An input iterator.
00420        *  @param  x  A comparison functor describing a strict weak ordering.
00421        *  @param  s  An initial sequence with which to start.
00422        *
00423        *  Begins by copying @a s, inserting a copy of the elements
00424        *  from @a [first,last) into the copy of @a s, then ordering
00425        *  the copy according to @a x.
00426        *
00427        *  For more information on function objects, see the
00428        *  documentation on @link functors functor base
00429        *  classes@endlink.
00430        */
00431 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00432       template<typename _InputIterator>
00433         priority_queue(_InputIterator __first, _InputIterator __last,
00434                const _Compare& __x = _Compare(),
00435                const _Sequence& __s = _Sequence())
00436     : c(__s), comp(__x)
00437         {
00438       __glibcxx_requires_valid_range(__first, __last);
00439       c.insert(c.end(), __first, __last);
00440       std::make_heap(c.begin(), c.end(), comp);
00441     }
00442 #else
00443       template<typename _InputIterator>
00444         priority_queue(_InputIterator __first, _InputIterator __last,
00445                const _Compare& __x,
00446                const _Sequence& __s)
00447     : c(__s), comp(__x)
00448         {
00449       __glibcxx_requires_valid_range(__first, __last);
00450       c.insert(c.end(), __first, __last);
00451       std::make_heap(c.begin(), c.end(), comp);
00452     }
00453 
00454       template<typename _InputIterator>
00455         priority_queue(_InputIterator __first, _InputIterator __last,
00456                const _Compare& __x = _Compare(),
00457                _Sequence&& __s = _Sequence())
00458     : c(std::move(__s)), comp(__x)
00459         {
00460       __glibcxx_requires_valid_range(__first, __last);
00461       c.insert(c.end(), __first, __last);
00462       std::make_heap(c.begin(), c.end(), comp);
00463     }
00464 
00465       priority_queue(priority_queue&& __pq)
00466       : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
00467 
00468       priority_queue&
00469       operator=(priority_queue&& __pq)
00470       {
00471     c = std::move(__pq.c);
00472     comp = std::move(__pq.comp);
00473     return *this;
00474       }
00475 #endif
00476 
00477       /**
00478        *  Returns true if the %queue is empty.
00479        */
00480       bool
00481       empty() const
00482       { return c.empty(); }
00483 
00484       /**  Returns the number of elements in the %queue.  */
00485       size_type
00486       size() const
00487       { return c.size(); }
00488 
00489       /**
00490        *  Returns a read-only (constant) reference to the data at the first
00491        *  element of the %queue.
00492        */
00493       const_reference
00494       top() const
00495       {
00496     __glibcxx_requires_nonempty();
00497     return c.front();
00498       }
00499 
00500       /**
00501        *  @brief  Add data to the %queue.
00502        *  @param  x  Data to be added.
00503        *
00504        *  This is a typical %queue operation.
00505        *  The time complexity of the operation depends on the underlying
00506        *  sequence.
00507        */
00508       void
00509       push(const value_type& __x)
00510       {
00511     c.push_back(__x);
00512     std::push_heap(c.begin(), c.end(), comp);
00513       }
00514 
00515 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00516       void
00517       push(value_type&& __x)
00518       {
00519     c.push_back(std::move(__x));
00520     std::push_heap(c.begin(), c.end(), comp);
00521       }
00522 
00523       template<typename... _Args>
00524         void
00525         emplace(_Args&&... __args)
00526     {
00527       c.emplace_back(std::forward<_Args>(__args)...);
00528       std::push_heap(c.begin(), c.end(), comp);
00529     }
00530 #endif
00531 
00532       /**
00533        *  @brief  Removes first element.
00534        *
00535        *  This is a typical %queue operation.  It shrinks the %queue
00536        *  by one.  The time complexity of the operation depends on the
00537        *  underlying sequence.
00538        *
00539        *  Note that no data is returned, and if the first element's
00540        *  data is needed, it should be retrieved before pop() is
00541        *  called.
00542        */
00543       void
00544       pop()
00545       {
00546     __glibcxx_requires_nonempty();
00547     std::pop_heap(c.begin(), c.end(), comp);
00548     c.pop_back();
00549       }
00550 
00551 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00552       void
00553       swap(priority_queue&& __pq)
00554       {
00555     using std::swap;
00556     c.swap(__pq.c);
00557     swap(comp, __pq.comp);
00558       }
00559 #endif
00560     };
00561 
00562   // No equality/comparison operators are provided for priority_queue.
00563 
00564 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00565   template<typename _Tp, typename _Sequence, typename _Compare>
00566     inline void
00567     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00568      priority_queue<_Tp, _Sequence, _Compare>& __y)
00569     { __x.swap(__y); }
00570 
00571   template<typename _Tp, typename _Sequence, typename _Compare>
00572     inline void
00573     swap(priority_queue<_Tp, _Sequence, _Compare>&& __x,
00574      priority_queue<_Tp, _Sequence, _Compare>& __y)
00575     { __x.swap(__y); }
00576 
00577   template<typename _Tp, typename _Sequence, typename _Compare>
00578     inline void
00579     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00580      priority_queue<_Tp, _Sequence, _Compare>&& __y)
00581     { __x.swap(__y); }
00582 #endif
00583 
00584 _GLIBCXX_END_NAMESPACE
00585 
00586 #endif /* _STL_QUEUE_H */

Generated on Thu Jul 23 21:16:22 2009 for libstdc++ by  doxygen 1.5.8