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