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