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