libstdc++-v3/include/bits/stl_queue.h

   1 // Queue implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2021 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 __cpp_lib_three_way_comparison
 118       template<typename _Tp1, three_way_comparable _Seq1>
 119         friend compare_three_way_result_t<_Seq1>
 120         operator<=>(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 121 #endif
 122
 123 #if __cplusplus >= 201103L
 124       template<typename _Alloc>
 125         using _Uses = typename
 126           enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
 127
 128 #if __cplusplus >= 201703L
 129       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 130       // 2566. Requirements on the first template parameter of container
 131       // adaptors
 132       static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
 133           "value_type must be the same as the underlying container");
 134 #endif // C++17
 135 #endif // C++11
 136
 137     public:
 138       typedef typename  _Sequence::value_type           value_type;
 139       typedef typename  _Sequence::reference            reference;
 140       typedef typename  _Sequence::const_reference      const_reference;
 141       typedef typename  _Sequence::size_type            size_type;
 142       typedef           _Sequence                       container_type;
 143
 144     protected:
 145       /*  Maintainers wondering why this isn't uglified as per style
 146        *  guidelines should note that this name is specified in the standard,
 147        *  C++98 [23.2.3.1].
 148        *  (Why? Presumably for the same reason that it's protected instead
 149        *  of private: to allow derivation.  But none of the other
 150        *  containers allow for derivation.  Odd.)
 151        */
 152        ///  @c c is the underlying container.
 153       _Sequence c;
 154
 155     public:
 156       /**
 157        *  @brief  Default constructor creates no elements.
 158        */
 159 #if __cplusplus < 201103L
 160       explicit
 161       queue(const _Sequence& __c = _Sequence())
 162       : c(__c) { }
 163 #else
 164       template<typename _Seq = _Sequence, typename _Requires = typename
 165                enable_if<is_default_constructible<_Seq>::value>::type>
 166         queue()
 167         : c() { }
 168
 169       explicit
 170       queue(const _Sequence& __c)
 171       : c(__c) { }
 172
 173       explicit
 174       queue(_Sequence&& __c)
 175       : c(std::move(__c)) { }
 176
 177       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 178         explicit
 179         queue(const _Alloc& __a)
 180         : c(__a) { }
 181
 182       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 183         queue(const _Sequence& __c, const _Alloc& __a)
 184         : c(__c, __a) { }
 185
 186       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 187         queue(_Sequence&& __c, const _Alloc& __a)
 188         : c(std::move(__c), __a) { }
 189
 190       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 191         queue(const queue& __q, const _Alloc& __a)
 192         : c(__q.c, __a) { }
 193
 194       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 195         queue(queue&& __q, const _Alloc& __a)
 196         : c(std::move(__q.c), __a) { }
 197 #endif
 198
 199       /**
 200        *  Returns true if the %queue is empty.
 201        */
 202       _GLIBCXX_NODISCARD bool
 203       empty() const
 204       { return c.empty(); }
 205
 206       /**  Returns the number of elements in the %queue.  */
 207       size_type
 208       size() const
 209       { return c.size(); }
 210
 211       /**
 212        *  Returns a read/write reference to the data at the first
 213        *  element of the %queue.
 214        */
 215       reference
 216       front()
 217       {
 218         __glibcxx_requires_nonempty();
 219         return c.front();
 220       }
 221
 222       /**
 223        *  Returns a read-only (constant) reference to the data at the first
 224        *  element of the %queue.
 225        */
 226       const_reference
 227       front() const
 228       {
 229         __glibcxx_requires_nonempty();
 230         return c.front();
 231       }
 232
 233       /**
 234        *  Returns a read/write reference to the data at the last
 235        *  element of the %queue.
 236        */
 237       reference
 238       back()
 239       {
 240         __glibcxx_requires_nonempty();
 241         return c.back();
 242       }
 243
 244       /**
 245        *  Returns a read-only (constant) reference to the data at the last
 246        *  element of the %queue.
 247        */
 248       const_reference
 249       back() const
 250       {
 251         __glibcxx_requires_nonempty();
 252         return c.back();
 253       }
 254
 255       /**
 256        *  @brief  Add data to the end of the %queue.
 257        *  @param  __x  Data to be added.
 258        *
 259        *  This is a typical %queue operation.  The function creates an
 260        *  element at the end of the %queue and assigns the given data
 261        *  to it.  The time complexity of the operation depends on the
 262        *  underlying sequence.
 263        */
 264       void
 265       push(const value_type& __x)
 266       { c.push_back(__x); }
 267
 268 #if __cplusplus >= 201103L
 269       void
 270       push(value_type&& __x)
 271       { c.push_back(std::move(__x)); }
 272
 273 #if __cplusplus > 201402L
 274       template<typename... _Args>
 275         decltype(auto)
 276         emplace(_Args&&... __args)
 277         { return c.emplace_back(std::forward<_Args>(__args)...); }
 278 #else
 279       template<typename... _Args>
 280         void
 281         emplace(_Args&&... __args)
 282         { c.emplace_back(std::forward<_Args>(__args)...); }
 283 #endif
 284 #endif
 285
 286       /**
 287        *  @brief  Removes first element.
 288        *
 289        *  This is a typical %queue operation.  It shrinks the %queue by one.
 290        *  The time complexity of the operation depends on the underlying
 291        *  sequence.
 292        *
 293        *  Note that no data is returned, and if the first element's
 294        *  data is needed, it should be retrieved before pop() is
 295        *  called.
 296        */
 297       void
 298       pop()
 299       {
 300         __glibcxx_requires_nonempty();
 301         c.pop_front();
 302       }
 303
 304 #if __cplusplus >= 201103L
 305       void
 306       swap(queue& __q)
 307 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 308       noexcept(__is_nothrow_swappable<_Sequence>::value)
 309 #else
 310       noexcept(__is_nothrow_swappable<_Tp>::value)
 311 #endif
 312       {
 313         using std::swap;
 314         swap(c, __q.c);
 315       }
 316 #endif // __cplusplus >= 201103L
 317     };
 318
 319 #if __cpp_deduction_guides >= 201606
 320   template<typename _Container,
 321            typename = _RequireNotAllocator<_Container>>
 322     queue(_Container) -> queue<typename _Container::value_type, _Container>;
 323
 324   template<typename _Container, typename _Allocator,
 325            typename = _RequireNotAllocator<_Container>,
 326            typename = _RequireAllocator<_Allocator>>
 327     queue(_Container, _Allocator)
 328     -> queue<typename _Container::value_type, _Container>;
 329 #endif
 330
 331   /**
 332    *  @brief  Queue equality comparison.
 333    *  @param  __x  A %queue.
 334    *  @param  __y  A %queue of the same type as @a __x.
 335    *  @return  True iff the size and elements of the queues are equal.
 336    *
 337    *  This is an equivalence relation.  Complexity and semantics depend on the
 338    *  underlying sequence type, but the expected rules are:  this relation is
 339    *  linear in the size of the sequences, and queues are considered equivalent
 340    *  if their sequences compare equal.
 341   */
 342   template<typename _Tp, typename _Seq>
 343     inline bool
 344     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 345     { return __x.c == __y.c; }
 346
 347   /**
 348    *  @brief  Queue ordering relation.
 349    *  @param  __x  A %queue.
 350    *  @param  __y  A %queue of the same type as @a x.
 351    *  @return  True iff @a __x is lexicographically less than @a __y.
 352    *
 353    *  This is an total ordering relation.  Complexity and semantics
 354    *  depend on the underlying sequence type, but the expected rules
 355    *  are: this relation is linear in the size of the sequences, the
 356    *  elements must be comparable with @c <, and
 357    *  std::lexicographical_compare() is usually used to make the
 358    *  determination.
 359   */
 360   template<typename _Tp, typename _Seq>
 361     inline bool
 362     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 363     { return __x.c < __y.c; }
 364
 365   /// Based on operator==
 366   template<typename _Tp, typename _Seq>
 367     inline bool
 368     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 369     { return !(__x == __y); }
 370
 371   /// Based on operator<
 372   template<typename _Tp, typename _Seq>
 373     inline bool
 374     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 375     { return __y < __x; }
 376
 377   /// Based on operator<
 378   template<typename _Tp, typename _Seq>
 379     inline bool
 380     operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 381     { return !(__y < __x); }
 382
 383   /// Based on operator<
 384   template<typename _Tp, typename _Seq>
 385     inline bool
 386     operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 387     { return !(__x < __y); }
 388
 389 #if __cpp_lib_three_way_comparison
 390   template<typename _Tp, three_way_comparable _Seq>
 391     inline compare_three_way_result_t<_Seq>
 392     operator<=>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 393     { return __x.c <=> __y.c; }
 394 #endif
 395
 396 #if __cplusplus >= 201103L
 397   template<typename _Tp, typename _Seq>
 398     inline
 399 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 400     // Constrained free swap overload, see p0185r1
 401     typename enable_if<__is_swappable<_Seq>::value>::type
 402 #else
 403     void
 404 #endif
 405     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
 406     noexcept(noexcept(__x.swap(__y)))
 407     { __x.swap(__y); }
 408
 409   template<typename _Tp, typename _Seq, typename _Alloc>
 410     struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
 411     : public uses_allocator<_Seq, _Alloc>::type { };
 412 #endif // __cplusplus >= 201103L
 413
 414   /**
 415    *  @brief  A standard container automatically sorting its contents.
 416    *
 417    *  @ingroup sequences
 418    *
 419    *  @tparam _Tp  Type of element.
 420    *  @tparam _Sequence  Type of underlying sequence, defaults to vector<_Tp>.
 421    *  @tparam _Compare  Comparison function object type, defaults to
 422    *                    less<_Sequence::value_type>.
 423    *
 424    *  This is not a true container, but an @e adaptor.  It holds
 425    *  another container, and provides a wrapper interface to that
 426    *  container.  The wrapper is what enforces priority-based sorting
 427    *  and %queue behavior.  Very few of the standard container/sequence
 428    *  interface requirements are met (e.g., iterators).
 429    *
 430    *  The second template parameter defines the type of the underlying
 431    *  sequence/container.  It defaults to std::vector, but it can be
 432    *  any type that supports @c front(), @c push_back, @c pop_back,
 433    *  and random-access iterators, such as std::deque or an
 434    *  appropriate user-defined type.
 435    *
 436    *  The third template parameter supplies the means of making
 437    *  priority comparisons.  It defaults to @c less<value_type> but
 438    *  can be anything defining a strict weak ordering.
 439    *
 440    *  Members not found in @a normal containers are @c container_type,
 441    *  which is a typedef for the second Sequence parameter, and @c
 442    *  push, @c pop, and @c top, which are standard %queue operations.
 443    *
 444    *  @note No equality/comparison operators are provided for
 445    *  %priority_queue.
 446    *
 447    *  @note Sorting of the elements takes place as they are added to,
 448    *  and removed from, the %priority_queue using the
 449    *  %priority_queue's member functions.  If you access the elements
 450    *  by other means, and change their data such that the sorting
 451    *  order would be different, the %priority_queue will not re-sort
 452    *  the elements for you.  (How could it know to do so?)
 453   */
 454   template<typename _Tp, typename _Sequence = vector<_Tp>,
 455            typename _Compare  = less<typename _Sequence::value_type> >
 456     class priority_queue
 457     {
 458 #ifdef _GLIBCXX_CONCEPT_CHECKS
 459       // concept requirements
 460       typedef typename _Sequence::value_type _Sequence_value_type;
 461 # if __cplusplus < 201103L
 462       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 463 # endif
 464       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 465       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 466       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 467       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
 468                                 _BinaryFunctionConcept)
 469 #endif
 470
 471 #if __cplusplus >= 201103L
 472       template<typename _Alloc>
 473         using _Uses = typename
 474           enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
 475
 476 #if __cplusplus >= 201703L
 477       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 478       // 2566. Requirements on the first template parameter of container
 479       // adaptors
 480       static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
 481           "value_type must be the same as the underlying container");
 482 #endif // C++17
 483 #endif // C++11
 484
 485     public:
 486       typedef typename  _Sequence::value_type           value_type;
 487       typedef typename  _Sequence::reference            reference;
 488       typedef typename  _Sequence::const_reference      const_reference;
 489       typedef typename  _Sequence::size_type            size_type;
 490       typedef           _Sequence                       container_type;
 491       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 492       // DR 2684. priority_queue lacking comparator typedef
 493       typedef          _Compare                         value_compare;
 494
 495     protected:
 496       //  See queue::c for notes on these names.
 497       _Sequence  c;
 498       _Compare   comp;
 499
 500     public:
 501       /**
 502        *  @brief  Default constructor creates no elements.
 503        */
 504 #if __cplusplus < 201103L
 505       explicit
 506       priority_queue(const _Compare& __x = _Compare(),
 507                      const _Sequence& __s = _Sequence())
 508       : c(__s), comp(__x)
 509       { std::make_heap(c.begin(), c.end(), comp); }
 510 #else
 511       template<typename _Seq = _Sequence, typename _Requires = typename
 512                enable_if<__and_<is_default_constructible<_Compare>,
 513                                 is_default_constructible<_Seq>>::value>::type>
 514         priority_queue()
 515         : c(), comp() { }
 516
 517       explicit
 518       priority_queue(const _Compare& __x, const _Sequence& __s)
 519       : c(__s), comp(__x)
 520       { std::make_heap(c.begin(), c.end(), comp); }
 521
 522       explicit
 523       priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
 524       : c(std::move(__s)), comp(__x)
 525       { std::make_heap(c.begin(), c.end(), comp); }
 526
 527       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 528         explicit
 529         priority_queue(const _Alloc& __a)
 530         : c(__a), comp() { }
 531
 532       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 533         priority_queue(const _Compare& __x, const _Alloc& __a)
 534         : c(__a), comp(__x) { }
 535
 536       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 537       // 2537. Constructors [...] taking allocators should call make_heap
 538       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 539         priority_queue(const _Compare& __x, const _Sequence& __c,
 540                        const _Alloc& __a)
 541         : c(__c, __a), comp(__x)
 542         { std::make_heap(c.begin(), c.end(), comp); }
 543
 544       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 545         priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
 546         : c(std::move(__c), __a), comp(__x)
 547         { std::make_heap(c.begin(), c.end(), comp); }
 548
 549       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 550         priority_queue(const priority_queue& __q, const _Alloc& __a)
 551         : c(__q.c, __a), comp(__q.comp) { }
 552
 553       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 554         priority_queue(priority_queue&& __q, const _Alloc& __a)
 555         : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
 556 #endif
 557
 558       /**
 559        *  @brief  Builds a %queue from a range.
 560        *  @param  __first  An input iterator.
 561        *  @param  __last  An input iterator.
 562        *  @param  __x  A comparison functor describing a strict weak ordering.
 563        *  @param  __s  An initial sequence with which to start.
 564        *
 565        *  Begins by copying @a __s, inserting a copy of the elements
 566        *  from @a [first,last) into the copy of @a __s, then ordering
 567        *  the copy according to @a __x.
 568        *
 569        *  For more information on function objects, see the
 570        *  documentation on @link functors functor base
 571        *  classes@endlink.
 572        */
 573 #if __cplusplus < 201103L
 574       template<typename _InputIterator>
 575         priority_queue(_InputIterator __first, _InputIterator __last,
 576                        const _Compare& __x = _Compare(),
 577                        const _Sequence& __s = _Sequence())
 578         : c(__s), comp(__x)
 579         {
 580           __glibcxx_requires_valid_range(__first, __last);
 581           c.insert(c.end(), __first, __last);
 582           std::make_heap(c.begin(), c.end(), comp);
 583         }
 584 #else
 585       template<typename _InputIterator>
 586         priority_queue(_InputIterator __first, _InputIterator __last,
 587                        const _Compare& __x,
 588                        const _Sequence& __s)
 589         : c(__s), comp(__x)
 590         {
 591           __glibcxx_requires_valid_range(__first, __last);
 592           c.insert(c.end(), __first, __last);
 593           std::make_heap(c.begin(), c.end(), comp);
 594         }
 595
 596       template<typename _InputIterator>
 597         priority_queue(_InputIterator __first, _InputIterator __last,
 598                        const _Compare& __x = _Compare(),
 599                        _Sequence&& __s = _Sequence())
 600         : c(std::move(__s)), comp(__x)
 601         {
 602           __glibcxx_requires_valid_range(__first, __last);
 603           c.insert(c.end(), __first, __last);
 604           std::make_heap(c.begin(), c.end(), comp);
 605         }
 606 #endif
 607
 608       /**
 609        *  Returns true if the %queue is empty.
 610        */
 611       _GLIBCXX_NODISCARD bool
 612       empty() const
 613       { return c.empty(); }
 614
 615       /**  Returns the number of elements in the %queue.  */
 616       size_type
 617       size() const
 618       { return c.size(); }
 619
 620       /**
 621        *  Returns a read-only (constant) reference to the data at the first
 622        *  element of the %queue.
 623        */
 624       const_reference
 625       top() const
 626       {
 627         __glibcxx_requires_nonempty();
 628         return c.front();
 629       }
 630
 631       /**
 632        *  @brief  Add data to the %queue.
 633        *  @param  __x  Data to be added.
 634        *
 635        *  This is a typical %queue operation.
 636        *  The time complexity of the operation depends on the underlying
 637        *  sequence.
 638        */
 639       void
 640       push(const value_type& __x)
 641       {
 642         c.push_back(__x);
 643         std::push_heap(c.begin(), c.end(), comp);
 644       }
 645
 646 #if __cplusplus >= 201103L
 647       void
 648       push(value_type&& __x)
 649       {
 650         c.push_back(std::move(__x));
 651         std::push_heap(c.begin(), c.end(), comp);
 652       }
 653
 654       template<typename... _Args>
 655         void
 656         emplace(_Args&&... __args)
 657         {
 658           c.emplace_back(std::forward<_Args>(__args)...);
 659           std::push_heap(c.begin(), c.end(), comp);
 660         }
 661 #endif
 662
 663       /**
 664        *  @brief  Removes first element.
 665        *
 666        *  This is a typical %queue operation.  It shrinks the %queue
 667        *  by one.  The time complexity of the operation depends on the
 668        *  underlying sequence.
 669        *
 670        *  Note that no data is returned, and if the first element's
 671        *  data is needed, it should be retrieved before pop() is
 672        *  called.
 673        */
 674       void
 675       pop()
 676       {
 677         __glibcxx_requires_nonempty();
 678         std::pop_heap(c.begin(), c.end(), comp);
 679         c.pop_back();
 680       }
 681
 682 #if __cplusplus >= 201103L
 683       void
 684       swap(priority_queue& __pq)
 685       noexcept(__and_<
 686 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 687                  __is_nothrow_swappable<_Sequence>,
 688 #else
 689                  __is_nothrow_swappable<_Tp>,
 690 #endif
 691                  __is_nothrow_swappable<_Compare>
 692                >::value)
 693       {
 694         using std::swap;
 695         swap(c, __pq.c);
 696         swap(comp, __pq.comp);
 697       }
 698 #endif // __cplusplus >= 201103L
 699     };
 700
 701 #if __cpp_deduction_guides >= 201606
 702   template<typename _Compare, typename _Container,
 703            typename = _RequireNotAllocator<_Compare>,
 704            typename = _RequireNotAllocator<_Container>>
 705     priority_queue(_Compare, _Container)
 706     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 707
 708   template<typename _InputIterator, typename _ValT
 709            = typename iterator_traits<_InputIterator>::value_type,
 710            typename _Compare = less<_ValT>,
 711            typename _Container = vector<_ValT>,
 712            typename = _RequireInputIter<_InputIterator>,
 713            typename = _RequireNotAllocator<_Compare>,
 714            typename = _RequireNotAllocator<_Container>>
 715     priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
 716                    _Container = _Container())
 717     -> priority_queue<_ValT, _Container, _Compare>;
 718
 719   template<typename _Compare, typename _Container, typename _Allocator,
 720            typename = _RequireNotAllocator<_Compare>,
 721            typename = _RequireNotAllocator<_Container>,
 722            typename = _RequireAllocator<_Allocator>>
 723     priority_queue(_Compare, _Container, _Allocator)
 724     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 725 #endif
 726
 727   // No equality/comparison operators are provided for priority_queue.
 728
 729 #if __cplusplus >= 201103L
 730   template<typename _Tp, typename _Sequence, typename _Compare>
 731     inline
 732 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 733     // Constrained free swap overload, see p0185r1
 734     typename enable_if<__and_<__is_swappable<_Sequence>,
 735                               __is_swappable<_Compare>>::value>::type
 736 #else
 737     void
 738 #endif
 739     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
 740          priority_queue<_Tp, _Sequence, _Compare>& __y)
 741     noexcept(noexcept(__x.swap(__y)))
 742     { __x.swap(__y); }
 743
 744   template<typename _Tp, typename _Sequence, typename _Compare,
 745            typename _Alloc>
 746     struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
 747     : public uses_allocator<_Sequence, _Alloc>::type { };
 748 #endif // __cplusplus >= 201103L
 749
 750 _GLIBCXX_END_NAMESPACE_VERSION
 751 } // namespace
 752
 753 #endif /* _STL_QUEUE_H */