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