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 @a 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 #endif
00321 
00322   /**
00323    *  @brief  A standard container automatically sorting its contents.
00324    *
00325    *  @ingroup sequences
00326    *
00327    *  This is not a true container, but an @e adaptor.  It holds
00328    *  another container, and provides a wrapper interface to that
00329    *  container.  The wrapper is what enforces priority-based sorting 
00330    *  and %queue behavior.  Very few of the standard container/sequence
00331    *  interface requirements are met (e.g., iterators).
00332    *
00333    *  The second template parameter defines the type of the underlying
00334    *  sequence/container.  It defaults to std::vector, but it can be
00335    *  any type that supports @c front(), @c push_back, @c pop_back,
00336    *  and random-access iterators, such as std::deque or an
00337    *  appropriate user-defined type.
00338    *
00339    *  The third template parameter supplies the means of making
00340    *  priority comparisons.  It defaults to @c less<value_type> but
00341    *  can be anything defining a strict weak ordering.
00342    *
00343    *  Members not found in @a normal containers are @c container_type,
00344    *  which is a typedef for the second Sequence parameter, and @c
00345    *  push, @c pop, and @c top, which are standard %queue operations.
00346    *
00347    *  @note No equality/comparison operators are provided for
00348    *  %priority_queue.
00349    *
00350    *  @note Sorting of the elements takes place as they are added to,
00351    *  and removed from, the %priority_queue using the
00352    *  %priority_queue's member functions.  If you access the elements
00353    *  by other means, and change their data such that the sorting
00354    *  order would be different, the %priority_queue will not re-sort
00355    *  the elements for you.  (How could it know to do so?)
00356   */
00357   template<typename _Tp, typename _Sequence = vector<_Tp>,
00358        typename _Compare  = less<typename _Sequence::value_type> >
00359     class priority_queue
00360     {
00361       // concept requirements
00362       typedef typename _Sequence::value_type _Sequence_value_type;
00363       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00364       __glibcxx_class_requires(_Sequence, _SequenceConcept)
00365       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
00366       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00367       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
00368                 _BinaryFunctionConcept)
00369 
00370     public:
00371       typedef typename _Sequence::value_type                value_type;
00372       typedef typename _Sequence::reference                 reference;
00373       typedef typename _Sequence::const_reference           const_reference;
00374       typedef typename _Sequence::size_type                 size_type;
00375       typedef          _Sequence                            container_type;
00376 
00377     protected:
00378       //  See queue::c for notes on these names.
00379       _Sequence  c;
00380       _Compare   comp;
00381 
00382     public:
00383       /**
00384        *  @brief  Default constructor creates no elements.
00385        */
00386 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00387       explicit
00388       priority_queue(const _Compare& __x = _Compare(),
00389              const _Sequence& __s = _Sequence())
00390       : c(__s), comp(__x)
00391       { std::make_heap(c.begin(), c.end(), comp); }
00392 #else
00393       explicit
00394       priority_queue(const _Compare& __x,
00395              const _Sequence& __s)
00396       : c(__s), comp(__x)
00397       { std::make_heap(c.begin(), c.end(), comp); }
00398 
00399       explicit
00400       priority_queue(const _Compare& __x = _Compare(),
00401              _Sequence&& __s = _Sequence())
00402       : c(std::move(__s)), comp(__x)
00403       { std::make_heap(c.begin(), c.end(), comp); }
00404 #endif
00405 
00406       /**
00407        *  @brief  Builds a %queue from a range.
00408        *  @param  first  An input iterator.
00409        *  @param  last  An input iterator.
00410        *  @param  x  A comparison functor describing a strict weak ordering.
00411        *  @param  s  An initial sequence with which to start.
00412        *
00413        *  Begins by copying @a s, inserting a copy of the elements
00414        *  from @a [first,last) into the copy of @a s, then ordering
00415        *  the copy according to @a x.
00416        *
00417        *  For more information on function objects, see the
00418        *  documentation on @link functors functor base
00419        *  classes@endlink.
00420        */
00421 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00422       template<typename _InputIterator>
00423         priority_queue(_InputIterator __first, _InputIterator __last,
00424                const _Compare& __x = _Compare(),
00425                const _Sequence& __s = _Sequence())
00426     : c(__s), comp(__x)
00427         {
00428       __glibcxx_requires_valid_range(__first, __last);
00429       c.insert(c.end(), __first, __last);
00430       std::make_heap(c.begin(), c.end(), comp);
00431     }
00432 #else
00433       template<typename _InputIterator>
00434         priority_queue(_InputIterator __first, _InputIterator __last,
00435                const _Compare& __x,
00436                const _Sequence& __s)
00437     : c(__s), comp(__x)
00438         {
00439       __glibcxx_requires_valid_range(__first, __last);
00440       c.insert(c.end(), __first, __last);
00441       std::make_heap(c.begin(), c.end(), comp);
00442     }
00443 
00444       template<typename _InputIterator>
00445         priority_queue(_InputIterator __first, _InputIterator __last,
00446                const _Compare& __x = _Compare(),
00447                _Sequence&& __s = _Sequence())
00448     : c(std::move(__s)), comp(__x)
00449         {
00450       __glibcxx_requires_valid_range(__first, __last);
00451       c.insert(c.end(), __first, __last);
00452       std::make_heap(c.begin(), c.end(), comp);
00453     }
00454 
00455       priority_queue(priority_queue&& __pq)
00456       : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
00457 
00458       priority_queue&
00459       operator=(priority_queue&& __pq)
00460       {
00461     c = std::move(__pq.c);
00462     comp = std::move(__pq.comp);
00463     return *this;
00464       }
00465 #endif
00466 
00467       /**
00468        *  Returns true if the %queue is empty.
00469        */
00470       bool
00471       empty() const
00472       { return c.empty(); }
00473 
00474       /**  Returns the number of elements in the %queue.  */
00475       size_type
00476       size() const
00477       { return c.size(); }
00478 
00479       /**
00480        *  Returns a read-only (constant) reference to the data at the first
00481        *  element of the %queue.
00482        */
00483       const_reference
00484       top() const
00485       {
00486     __glibcxx_requires_nonempty();
00487     return c.front();
00488       }
00489 
00490       /**
00491        *  @brief  Add data to the %queue.
00492        *  @param  x  Data to be added.
00493        *
00494        *  This is a typical %queue operation.
00495        *  The time complexity of the operation depends on the underlying
00496        *  sequence.
00497        */
00498       void
00499       push(const value_type& __x)
00500       {
00501     c.push_back(__x);
00502     std::push_heap(c.begin(), c.end(), comp);
00503       }
00504 
00505 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00506       void
00507       push(value_type&& __x)
00508       {
00509     c.push_back(std::move(__x));
00510     std::push_heap(c.begin(), c.end(), comp);
00511       }
00512 
00513       template<typename... _Args>
00514         void
00515         emplace(_Args&&... __args)
00516     {
00517       c.emplace_back(std::forward<_Args>(__args)...);
00518       std::push_heap(c.begin(), c.end(), comp);
00519     }
00520 #endif
00521 
00522       /**
00523        *  @brief  Removes first element.
00524        *
00525        *  This is a typical %queue operation.  It shrinks the %queue
00526        *  by one.  The time complexity of the operation depends on the
00527        *  underlying sequence.
00528        *
00529        *  Note that no data is returned, and if the first element's
00530        *  data is needed, it should be retrieved before pop() is
00531        *  called.
00532        */
00533       void
00534       pop()
00535       {
00536     __glibcxx_requires_nonempty();
00537     std::pop_heap(c.begin(), c.end(), comp);
00538     c.pop_back();
00539       }
00540 
00541 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00542       void
00543       swap(priority_queue& __pq)
00544       {
00545     using std::swap;
00546     c.swap(__pq.c);
00547     swap(comp, __pq.comp);
00548       }
00549 #endif
00550     };
00551 
00552   // No equality/comparison operators are provided for priority_queue.
00553 
00554 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00555   template<typename _Tp, typename _Sequence, typename _Compare>
00556     inline void
00557     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00558      priority_queue<_Tp, _Sequence, _Compare>& __y)
00559     { __x.swap(__y); }
00560 #endif
00561 
00562 _GLIBCXX_END_NAMESPACE
00563 
00564 #endif /* _STL_QUEUE_H */