contrib/gcc-8.0/libstdc++-v3/include/bits/stl_queue.h

   1 // Queue implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2018 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996,1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/stl_queue.h
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{queue}
  54  */
  55
  56 #ifndef _STL_QUEUE_H
  57 #define _STL_QUEUE_H 1
  58
  59 #include <bits/concept_check.h>
  60 #include <debug/debug.h>
  61 #if __cplusplus >= 201103L
  62 # include <bits/uses_allocator.h>
  63 #endif
  64
  65 namespace std _GLIBCXX_VISIBILITY(default)
  66 {
  67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  68
  69   /**
  70    *  @brief  A standard container giving FIFO behavior.
  71    *
  72    *  @ingroup sequences
  73    *
  74    *  @tparam _Tp  Type of element.
  75    *  @tparam _Sequence  Type of underlying sequence, defaults to deque<_Tp>.
  76    *
  77    *  Meets many of the requirements of a
  78    *  <a href="tables.html#65">container</a>,
  79    *  but does not define anything to do with iterators.  Very few of the
  80    *  other standard container interfaces are defined.
  81    *
  82    *  This is not a true container, but an @e adaptor.  It holds another
  83    *  container, and provides a wrapper interface to that container.  The
  84    *  wrapper is what enforces strict first-in-first-out %queue behavior.
  85    *
  86    *  The second template parameter defines the type of the underlying
  87    *  sequence/container.  It defaults to std::deque, but it can be any type
  88    *  that supports @c front, @c back, @c push_back, and @c pop_front,
  89    *  such as std::list or an appropriate user-defined type.
  90    *
  91    *  Members not found in @a normal containers are @c container_type,
  92    *  which is a typedef for the second Sequence parameter, and @c push and
  93    *  @c pop, which are standard %queue/FIFO operations.
  94   */
  95   template<typename _Tp, typename _Sequence = deque<_Tp> >
  96     class queue
  97     {
  98 #ifdef _GLIBCXX_CONCEPT_CHECKS
  99       // concept requirements
 100       typedef typename _Sequence::value_type _Sequence_value_type;
 101 # if __cplusplus < 201103L
 102       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 103 # endif
 104       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
 105       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
 106       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 107 #endif
 108
 109       template<typename _Tp1, typename _Seq1>
 110         friend bool
 111         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 112
 113       template<typename _Tp1, typename _Seq1>
 114         friend bool
 115         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 116
 117 #if __cplusplus >= 201103L
 118       template<typename _Alloc>
 119         using _Uses = typename
 120           enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
 121 #endif
 122
 123     public:
 124       typedef typename  _Sequence::value_type           value_type;
 125       typedef typename  _Sequence::reference            reference;
 126       typedef typename  _Sequence::const_reference      const_reference;
 127       typedef typename  _Sequence::size_type            size_type;
 128       typedef           _Sequence                       container_type;
 129
 130     protected:
 131       /*  Maintainers wondering why this isn't uglified as per style
 132        *  guidelines should note that this name is specified in the standard,
 133        *  C++98 [23.2.3.1].
 134        *  (Why? Presumably for the same reason that it's protected instead
 135        *  of private: to allow derivation.  But none of the other
 136        *  containers allow for derivation.  Odd.)
 137        */
 138        ///  @c c is the underlying container.
 139       _Sequence c;
 140
 141     public:
 142       /**
 143        *  @brief  Default constructor creates no elements.
 144        */
 145 #if __cplusplus < 201103L
 146       explicit
 147       queue(const _Sequence& __c = _Sequence())
 148       : c(__c) { }
 149 #else
 150       template<typename _Seq = _Sequence, typename _Requires = typename
 151                enable_if<is_default_constructible<_Seq>::value>::type>
 152         queue()
 153         : c() { }
 154
 155       explicit
 156       queue(const _Sequence& __c)
 157       : c(__c) { }
 158
 159       explicit
 160       queue(_Sequence&& __c)
 161       : c(std::move(__c)) { }
 162
 163       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 164         explicit
 165         queue(const _Alloc& __a)
 166         : c(__a) { }
 167
 168       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 169         queue(const _Sequence& __c, const _Alloc& __a)
 170         : c(__c, __a) { }
 171
 172       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 173         queue(_Sequence&& __c, const _Alloc& __a)
 174         : c(std::move(__c), __a) { }
 175
 176       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 177         queue(const queue& __q, const _Alloc& __a)
 178         : c(__q.c, __a) { }
 179
 180       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 181         queue(queue&& __q, const _Alloc& __a)
 182         : c(std::move(__q.c), __a) { }
 183 #endif
 184
 185       /**
 186        *  Returns true if the %queue is empty.
 187        */
 188       bool
 189       empty() const
 190       { return c.empty(); }
 191
 192       /**  Returns the number of elements in the %queue.  */
 193       size_type
 194       size() const
 195       { return c.size(); }
 196
 197       /**
 198        *  Returns a read/write reference to the data at the first
 199        *  element of the %queue.
 200        */
 201       reference
 202       front()
 203       {
 204         __glibcxx_requires_nonempty();
 205         return c.front();
 206       }
 207
 208       /**
 209        *  Returns a read-only (constant) reference to the data at the first
 210        *  element of the %queue.
 211        */
 212       const_reference
 213       front() const
 214       {
 215         __glibcxx_requires_nonempty();
 216         return c.front();
 217       }
 218
 219       /**
 220        *  Returns a read/write reference to the data at the last
 221        *  element of the %queue.
 222        */
 223       reference
 224       back()
 225       {
 226         __glibcxx_requires_nonempty();
 227         return c.back();
 228       }
 229
 230       /**
 231        *  Returns a read-only (constant) reference to the data at the last
 232        *  element of the %queue.
 233        */
 234       const_reference
 235       back() const
 236       {
 237         __glibcxx_requires_nonempty();
 238         return c.back();
 239       }
 240
 241       /**
 242        *  @brief  Add data to the end of the %queue.
 243        *  @param  __x  Data to be added.
 244        *
 245        *  This is a typical %queue operation.  The function creates an
 246        *  element at the end of the %queue and assigns the given data
 247        *  to it.  The time complexity of the operation depends on the
 248        *  underlying sequence.
 249        */
 250       void
 251       push(const value_type& __x)
 252       { c.push_back(__x); }
 253
 254 #if __cplusplus >= 201103L
 255       void
 256       push(value_type&& __x)
 257       { c.push_back(std::move(__x)); }
 258
 259 #if __cplusplus > 201402L
 260       template<typename... _Args>
 261         decltype(auto)
 262         emplace(_Args&&... __args)
 263         { return c.emplace_back(std::forward<_Args>(__args)...); }
 264 #else
 265       template<typename... _Args>
 266         void
 267         emplace(_Args&&... __args)
 268         { c.emplace_back(std::forward<_Args>(__args)...); }
 269 #endif
 270 #endif
 271
 272       /**
 273        *  @brief  Removes first element.
 274        *
 275        *  This is a typical %queue operation.  It shrinks the %queue by one.
 276        *  The time complexity of the operation depends on the underlying
 277        *  sequence.
 278        *
 279        *  Note that no data is returned, and if the first element's
 280        *  data is needed, it should be retrieved before pop() is
 281        *  called.
 282        */
 283       void
 284       pop()
 285       {
 286         __glibcxx_requires_nonempty();
 287         c.pop_front();
 288       }
 289
 290 #if __cplusplus >= 201103L
 291       void
 292       swap(queue& __q)
 293 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 294       noexcept(__is_nothrow_swappable<_Sequence>::value)
 295 #else
 296       noexcept(__is_nothrow_swappable<_Tp>::value)
 297 #endif
 298       {
 299         using std::swap;
 300         swap(c, __q.c);
 301       }
 302 #endif // __cplusplus >= 201103L
 303     };
 304
 305 #if __cpp_deduction_guides >= 201606
 306   template<typename _Container,
 307            typename = enable_if_t<!__is_allocator<_Container>::value>>
 308     queue(_Container) -> queue<typename _Container::value_type, _Container>;
 309
 310   template<typename _Container, typename _Allocator,
 311            typename = enable_if_t<!__is_allocator<_Container>::value>,
 312            typename = enable_if_t<__is_allocator<_Allocator>::value>>
 313     queue(_Container, _Allocator)
 314     -> queue<typename _Container::value_type, _Container>;
 315 #endif
 316
 317   /**
 318    *  @brief  Queue equality comparison.
 319    *  @param  __x  A %queue.
 320    *  @param  __y  A %queue of the same type as @a __x.
 321    *  @return  True iff the size and elements of the queues are equal.
 322    *
 323    *  This is an equivalence relation.  Complexity and semantics depend on the
 324    *  underlying sequence type, but the expected rules are:  this relation is
 325    *  linear in the size of the sequences, and queues are considered equivalent
 326    *  if their sequences compare equal.
 327   */
 328   template<typename _Tp, typename _Seq>
 329     inline bool
 330     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 331     { return __x.c == __y.c; }
 332
 333   /**
 334    *  @brief  Queue ordering relation.
 335    *  @param  __x  A %queue.
 336    *  @param  __y  A %queue of the same type as @a x.
 337    *  @return  True iff @a __x is lexicographically less than @a __y.
 338    *
 339    *  This is an total ordering relation.  Complexity and semantics
 340    *  depend on the underlying sequence type, but the expected rules
 341    *  are: this relation is linear in the size of the sequences, the
 342    *  elements must be comparable with @c <, and
 343    *  std::lexicographical_compare() is usually used to make the
 344    *  determination.
 345   */
 346   template<typename _Tp, typename _Seq>
 347     inline bool
 348     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 349     { return __x.c < __y.c; }
 350
 351   /// Based on operator==
 352   template<typename _Tp, typename _Seq>
 353     inline bool
 354     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 355     { return !(__x == __y); }
 356
 357   /// Based on operator<
 358   template<typename _Tp, typename _Seq>
 359     inline bool
 360     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 361     { return __y < __x; }
 362
 363   /// Based on operator<
 364   template<typename _Tp, typename _Seq>
 365     inline bool
 366     operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 367     { return !(__y < __x); }
 368
 369   /// Based on operator<
 370   template<typename _Tp, typename _Seq>
 371     inline bool
 372     operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 373     { return !(__x < __y); }
 374
 375 #if __cplusplus >= 201103L
 376   template<typename _Tp, typename _Seq>
 377     inline
 378 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 379     // Constrained free swap overload, see p0185r1
 380     typename enable_if<__is_swappable<_Seq>::value>::type
 381 #else
 382     void
 383 #endif
 384     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
 385     noexcept(noexcept(__x.swap(__y)))
 386     { __x.swap(__y); }
 387
 388   template<typename _Tp, typename _Seq, typename _Alloc>
 389     struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
 390     : public uses_allocator<_Seq, _Alloc>::type { };
 391 #endif // __cplusplus >= 201103L
 392
 393   /**
 394    *  @brief  A standard container automatically sorting its contents.
 395    *
 396    *  @ingroup sequences
 397    *
 398    *  @tparam _Tp  Type of element.
 399    *  @tparam _Sequence  Type of underlying sequence, defaults to vector<_Tp>.
 400    *  @tparam _Compare  Comparison function object type, defaults to
 401    *                    less<_Sequence::value_type>.
 402    *
 403    *  This is not a true container, but an @e adaptor.  It holds
 404    *  another container, and provides a wrapper interface to that
 405    *  container.  The wrapper is what enforces priority-based sorting
 406    *  and %queue behavior.  Very few of the standard container/sequence
 407    *  interface requirements are met (e.g., iterators).
 408    *
 409    *  The second template parameter defines the type of the underlying
 410    *  sequence/container.  It defaults to std::vector, but it can be
 411    *  any type that supports @c front(), @c push_back, @c pop_back,
 412    *  and random-access iterators, such as std::deque or an
 413    *  appropriate user-defined type.
 414    *
 415    *  The third template parameter supplies the means of making
 416    *  priority comparisons.  It defaults to @c less<value_type> but
 417    *  can be anything defining a strict weak ordering.
 418    *
 419    *  Members not found in @a normal containers are @c container_type,
 420    *  which is a typedef for the second Sequence parameter, and @c
 421    *  push, @c pop, and @c top, which are standard %queue operations.
 422    *
 423    *  @note No equality/comparison operators are provided for
 424    *  %priority_queue.
 425    *
 426    *  @note Sorting of the elements takes place as they are added to,
 427    *  and removed from, the %priority_queue using the
 428    *  %priority_queue's member functions.  If you access the elements
 429    *  by other means, and change their data such that the sorting
 430    *  order would be different, the %priority_queue will not re-sort
 431    *  the elements for you.  (How could it know to do so?)
 432   */
 433   template<typename _Tp, typename _Sequence = vector<_Tp>,
 434            typename _Compare  = less<typename _Sequence::value_type> >
 435     class priority_queue
 436     {
 437 #ifdef _GLIBCXX_CONCEPT_CHECKS
 438       // concept requirements
 439       typedef typename _Sequence::value_type _Sequence_value_type;
 440 # if __cplusplus < 201103L
 441       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 442 # endif
 443       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 444       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 445       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 446       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
 447                                 _BinaryFunctionConcept)
 448 #endif
 449
 450 #if __cplusplus >= 201103L
 451       template<typename _Alloc>
 452         using _Uses = typename
 453           enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
 454 #endif
 455
 456     public:
 457       typedef typename  _Sequence::value_type           value_type;
 458       typedef typename  _Sequence::reference             reference;
 459       typedef typename  _Sequence::const_reference         const_reference;
 460       typedef typename  _Sequence::size_type             size_type;
 461       typedef           _Sequence                           container_type;
 462       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 463       // DR 2684. priority_queue lacking comparator typedef
 464       typedef          _Compare                             value_compare;
 465
 466     protected:
 467       //  See queue::c for notes on these names.
 468       _Sequence  c;
 469       _Compare   comp;
 470
 471     public:
 472       /**
 473        *  @brief  Default constructor creates no elements.
 474        */
 475 #if __cplusplus < 201103L
 476       explicit
 477       priority_queue(const _Compare& __x = _Compare(),
 478                      const _Sequence& __s = _Sequence())
 479       : c(__s), comp(__x)
 480       { std::make_heap(c.begin(), c.end(), comp); }
 481 #else
 482       template<typename _Seq = _Sequence, typename _Requires = typename
 483                enable_if<__and_<is_default_constructible<_Compare>,
 484                                 is_default_constructible<_Seq>>::value>::type>
 485         priority_queue()
 486         : c(), comp() { }
 487
 488       explicit
 489       priority_queue(const _Compare& __x, const _Sequence& __s)
 490       : c(__s), comp(__x)
 491       { std::make_heap(c.begin(), c.end(), comp); }
 492
 493       explicit
 494       priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
 495       : c(std::move(__s)), comp(__x)
 496       { std::make_heap(c.begin(), c.end(), comp); }
 497
 498       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 499         explicit
 500         priority_queue(const _Alloc& __a)
 501         : c(__a), comp() { }
 502
 503       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 504         priority_queue(const _Compare& __x, const _Alloc& __a)
 505         : c(__a), comp(__x) { }
 506
 507       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 508         priority_queue(const _Compare& __x, const _Sequence& __c,
 509                        const _Alloc& __a)
 510         : c(__c, __a), comp(__x) { }
 511
 512       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 513         priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
 514         : c(std::move(__c), __a), comp(__x) { }
 515
 516       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 517         priority_queue(const priority_queue& __q, const _Alloc& __a)
 518         : c(__q.c, __a), comp(__q.comp) { }
 519
 520       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 521         priority_queue(priority_queue&& __q, const _Alloc& __a)
 522         : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
 523 #endif
 524
 525       /**
 526        *  @brief  Builds a %queue from a range.
 527        *  @param  __first  An input iterator.
 528        *  @param  __last  An input iterator.
 529        *  @param  __x  A comparison functor describing a strict weak ordering.
 530        *  @param  __s  An initial sequence with which to start.
 531        *
 532        *  Begins by copying @a __s, inserting a copy of the elements
 533        *  from @a [first,last) into the copy of @a __s, then ordering
 534        *  the copy according to @a __x.
 535        *
 536        *  For more information on function objects, see the
 537        *  documentation on @link functors functor base
 538        *  classes@endlink.
 539        */
 540 #if __cplusplus < 201103L
 541       template<typename _InputIterator>
 542         priority_queue(_InputIterator __first, _InputIterator __last,
 543                        const _Compare& __x = _Compare(),
 544                        const _Sequence& __s = _Sequence())
 545         : c(__s), comp(__x)
 546         {
 547           __glibcxx_requires_valid_range(__first, __last);
 548           c.insert(c.end(), __first, __last);
 549           std::make_heap(c.begin(), c.end(), comp);
 550         }
 551 #else
 552       template<typename _InputIterator>
 553         priority_queue(_InputIterator __first, _InputIterator __last,
 554                        const _Compare& __x,
 555                        const _Sequence& __s)
 556         : c(__s), comp(__x)
 557         {
 558           __glibcxx_requires_valid_range(__first, __last);
 559           c.insert(c.end(), __first, __last);
 560           std::make_heap(c.begin(), c.end(), comp);
 561         }
 562
 563       template<typename _InputIterator>
 564         priority_queue(_InputIterator __first, _InputIterator __last,
 565                        const _Compare& __x = _Compare(),
 566                        _Sequence&& __s = _Sequence())
 567         : c(std::move(__s)), comp(__x)
 568         {
 569           __glibcxx_requires_valid_range(__first, __last);
 570           c.insert(c.end(), __first, __last);
 571           std::make_heap(c.begin(), c.end(), comp);
 572         }
 573 #endif
 574
 575       /**
 576        *  Returns true if the %queue is empty.
 577        */
 578       bool
 579       empty() const
 580       { return c.empty(); }
 581
 582       /**  Returns the number of elements in the %queue.  */
 583       size_type
 584       size() const
 585       { return c.size(); }
 586
 587       /**
 588        *  Returns a read-only (constant) reference to the data at the first
 589        *  element of the %queue.
 590        */
 591       const_reference
 592       top() const
 593       {
 594         __glibcxx_requires_nonempty();
 595         return c.front();
 596       }
 597
 598       /**
 599        *  @brief  Add data to the %queue.
 600        *  @param  __x  Data to be added.
 601        *
 602        *  This is a typical %queue operation.
 603        *  The time complexity of the operation depends on the underlying
 604        *  sequence.
 605        */
 606       void
 607       push(const value_type& __x)
 608       {
 609         c.push_back(__x);
 610         std::push_heap(c.begin(), c.end(), comp);
 611       }
 612
 613 #if __cplusplus >= 201103L
 614       void
 615       push(value_type&& __x)
 616       {
 617         c.push_back(std::move(__x));
 618         std::push_heap(c.begin(), c.end(), comp);
 619       }
 620
 621       template<typename... _Args>
 622         void
 623         emplace(_Args&&... __args)
 624         {
 625           c.emplace_back(std::forward<_Args>(__args)...);
 626           std::push_heap(c.begin(), c.end(), comp);
 627         }
 628 #endif
 629
 630       /**
 631        *  @brief  Removes first element.
 632        *
 633        *  This is a typical %queue operation.  It shrinks the %queue
 634        *  by one.  The time complexity of the operation depends on the
 635        *  underlying sequence.
 636        *
 637        *  Note that no data is returned, and if the first element's
 638        *  data is needed, it should be retrieved before pop() is
 639        *  called.
 640        */
 641       void
 642       pop()
 643       {
 644         __glibcxx_requires_nonempty();
 645         std::pop_heap(c.begin(), c.end(), comp);
 646         c.pop_back();
 647       }
 648
 649 #if __cplusplus >= 201103L
 650       void
 651       swap(priority_queue& __pq)
 652       noexcept(__and_<
 653 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 654                  __is_nothrow_swappable<_Sequence>,
 655 #else
 656                  __is_nothrow_swappable<_Tp>,
 657 #endif
 658                  __is_nothrow_swappable<_Compare>
 659                >::value)
 660       {
 661         using std::swap;
 662         swap(c, __pq.c);
 663         swap(comp, __pq.comp);
 664       }
 665 #endif // __cplusplus >= 201103L
 666     };
 667
 668 #if __cpp_deduction_guides >= 201606
 669   template<typename _Compare, typename _Container,
 670            typename = enable_if_t<!__is_allocator<_Compare>::value>,
 671            typename = enable_if_t<!__is_allocator<_Container>::value>>
 672     priority_queue(_Compare, _Container)
 673     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 674
 675   template<typename _InputIterator, typename _ValT
 676            = typename iterator_traits<_InputIterator>::value_type,
 677            typename _Compare = less<_ValT>,
 678            typename _Container = vector<_ValT>,
 679            typename = _RequireInputIter<_InputIterator>,
 680            typename = enable_if_t<!__is_allocator<_Compare>::value>,
 681            typename = enable_if_t<!__is_allocator<_Container>::value>>
 682     priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
 683                    _Container = _Container())
 684     -> priority_queue<_ValT, _Container, _Compare>;
 685
 686   template<typename _Compare, typename _Container, typename _Allocator,
 687            typename = enable_if_t<!__is_allocator<_Compare>::value>,
 688            typename = enable_if_t<!__is_allocator<_Container>::value>,
 689            typename = enable_if_t<__is_allocator<_Allocator>::value>>
 690     priority_queue(_Compare, _Container, _Allocator)
 691     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 692 #endif
 693
 694   // No equality/comparison operators are provided for priority_queue.
 695
 696 #if __cplusplus >= 201103L
 697   template<typename _Tp, typename _Sequence, typename _Compare>
 698     inline
 699 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 700     // Constrained free swap overload, see p0185r1
 701     typename enable_if<__and_<__is_swappable<_Sequence>,
 702                               __is_swappable<_Compare>>::value>::type
 703 #else
 704     void
 705 #endif
 706     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
 707          priority_queue<_Tp, _Sequence, _Compare>& __y)
 708     noexcept(noexcept(__x.swap(__y)))
 709     { __x.swap(__y); }
 710
 711   template<typename _Tp, typename _Sequence, typename _Compare,
 712            typename _Alloc>
 713     struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
 714     : public uses_allocator<_Sequence, _Alloc>::type { };
 715 #endif // __cplusplus >= 201103L
 716
 717 _GLIBCXX_END_NAMESPACE_VERSION
 718 } // namespace
 719
 720 #endif /* _STL_QUEUE_H */