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

   1 // Queue implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2025 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 #if __glibcxx_containers_ranges // C++ >= 23
  65 # include <ranges> // ranges::to
  66 # include <bits/ranges_algobase.h> // ranges::copy
  67 #endif
  68
  69 namespace std _GLIBCXX_VISIBILITY(default)
  70 {
  71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  72
  73 #if __glibcxx_format_ranges
  74   template<typename, typename> class formatter;
  75 #endif
  76
  77   /**
  78    *  @brief  A standard container giving FIFO behavior.
  79    *
  80    *  @ingroup sequences
  81    *
  82    *  @tparam _Tp  Type of element.
  83    *  @tparam _Sequence  Type of underlying sequence, defaults to deque<_Tp>.
  84    *
  85    *  Meets many of the requirements of a
  86    *  <a href="tables.html#65">container</a>,
  87    *  but does not define anything to do with iterators.  Very few of the
  88    *  other standard container interfaces are defined.
  89    *
  90    *  This is not a true container, but an @e adaptor.  It holds another
  91    *  container, and provides a wrapper interface to that container.  The
  92    *  wrapper is what enforces strict first-in-first-out %queue behavior.
  93    *
  94    *  The second template parameter defines the type of the underlying
  95    *  sequence/container.  It defaults to std::deque, but it can be any type
  96    *  that supports @c front, @c back, @c push_back, and @c pop_front,
  97    *  such as std::list or an appropriate user-defined type.
  98    *
  99    *  Members not found in @a normal containers are @c container_type,
 100    *  which is a typedef for the second Sequence parameter, and @c push and
 101    *  @c pop, which are standard %queue/FIFO operations.
 102   */
 103   template<typename _Tp, typename _Sequence = deque<_Tp> >
 104     class queue
 105     {
 106 #ifdef _GLIBCXX_CONCEPT_CHECKS
 107       // concept requirements
 108       typedef typename _Sequence::value_type _Sequence_value_type;
 109 # if __cplusplus < 201103L
 110       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 111 # endif
 112       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
 113       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
 114       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 115 #endif
 116
 117       template<typename _Tp1, typename _Seq1>
 118         friend bool
 119         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 120
 121       template<typename _Tp1, typename _Seq1>
 122         friend bool
 123         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 124
 125 #if __cpp_lib_three_way_comparison
 126       template<typename _Tp1, three_way_comparable _Seq1>
 127         friend compare_three_way_result_t<_Seq1>
 128         operator<=>(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
 129 #endif
 130
 131 #if __cplusplus >= 201103L
 132       template<typename _Alloc>
 133         using _Uses = typename
 134           enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
 135
 136 #if __cplusplus >= 201703L
 137       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 138       // 2566. Requirements on the first template parameter of container
 139       // adaptors
 140       static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
 141           "value_type must be the same as the underlying container");
 142 #endif // C++17
 143 #endif // C++11
 144
 145     public:
 146       typedef typename  _Sequence::value_type           value_type;
 147       typedef typename  _Sequence::reference            reference;
 148       typedef typename  _Sequence::const_reference      const_reference;
 149       typedef typename  _Sequence::size_type            size_type;
 150       typedef           _Sequence                       container_type;
 151
 152     protected:
 153       /*  Maintainers wondering why this isn't uglified as per style
 154        *  guidelines should note that this name is specified in the standard,
 155        *  C++98 [23.2.3.1].
 156        *  (Why? Presumably for the same reason that it's protected instead
 157        *  of private: to allow derivation.  But none of the other
 158        *  containers allow for derivation.  Odd.)
 159        */
 160        ///  @c c is the underlying container.
 161       _Sequence c;
 162
 163     public:
 164       /**
 165        *  @brief  Default constructor creates no elements.
 166        */
 167 #if __cplusplus < 201103L
 168       explicit
 169       queue(const _Sequence& __c = _Sequence())
 170       : c(__c) { }
 171 #else
 172       template<typename _Seq = _Sequence, typename _Requires = typename
 173                enable_if<is_default_constructible<_Seq>::value>::type>
 174         queue()
 175         : c() { }
 176
 177       explicit
 178       queue(const _Sequence& __c)
 179       : c(__c) { }
 180
 181       explicit
 182       queue(_Sequence&& __c)
 183       : c(std::move(__c)) { }
 184
 185       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 186         explicit
 187         queue(const _Alloc& __a)
 188         : c(__a) { }
 189
 190       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 191         queue(const _Sequence& __c, const _Alloc& __a)
 192         : c(__c, __a) { }
 193
 194       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 195         queue(_Sequence&& __c, const _Alloc& __a)
 196         : c(std::move(__c), __a) { }
 197
 198       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 199         queue(const queue& __q, const _Alloc& __a)
 200         : c(__q.c, __a) { }
 201
 202       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 203         queue(queue&& __q, const _Alloc& __a)
 204         : c(std::move(__q.c), __a) { }
 205 #endif
 206
 207 #ifdef __glibcxx_adaptor_iterator_pair_constructor // C++ >= 23 && HOSTED
 208       template<typename _InputIterator,
 209                typename = _RequireInputIter<_InputIterator>>
 210         queue(_InputIterator __first, _InputIterator __last)
 211         : c(__first, __last) { }
 212
 213       template<typename _InputIterator, typename _Alloc,
 214                typename = _RequireInputIter<_InputIterator>,
 215                typename = _Uses<_Alloc>>
 216         queue(_InputIterator __first, _InputIterator __last, const _Alloc& __a)
 217         : c(__first, __last, __a) { }
 218 #endif
 219
 220 #if __glibcxx_containers_ranges // C++ >= 23
 221       /**
 222        * @brief Construct a queue from a range.
 223        * @since C++23
 224        */
 225       template<__detail::__container_compatible_range<_Tp> _Rg>
 226         queue(from_range_t, _Rg&& __rg)
 227         : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg)))
 228         { }
 229
 230       /**
 231        * @brief Construct a queue from a range.
 232        * @since C++23
 233        */
 234       template<__detail::__container_compatible_range<_Tp> _Rg,
 235                typename _Alloc>
 236         queue(from_range_t, _Rg&& __rg, const _Alloc& __a)
 237         : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a))
 238         { }
 239 #endif
 240
 241       /**
 242        *  Returns true if the %queue is empty.
 243        */
 244       _GLIBCXX_NODISCARD bool
 245       empty() const
 246       { return c.empty(); }
 247
 248       /**  Returns the number of elements in the %queue.  */
 249       _GLIBCXX_NODISCARD
 250       size_type
 251       size() const
 252       { return c.size(); }
 253
 254       /**
 255        *  Returns a read/write reference to the data at the first
 256        *  element of the %queue.
 257        */
 258       _GLIBCXX_NODISCARD
 259       reference
 260       front()
 261       {
 262         __glibcxx_requires_nonempty();
 263         return c.front();
 264       }
 265
 266       /**
 267        *  Returns a read-only (constant) reference to the data at the first
 268        *  element of the %queue.
 269        */
 270       _GLIBCXX_NODISCARD
 271       const_reference
 272       front() const
 273       {
 274         __glibcxx_requires_nonempty();
 275         return c.front();
 276       }
 277
 278       /**
 279        *  Returns a read/write reference to the data at the last
 280        *  element of the %queue.
 281        */
 282       _GLIBCXX_NODISCARD
 283       reference
 284       back()
 285       {
 286         __glibcxx_requires_nonempty();
 287         return c.back();
 288       }
 289
 290       /**
 291        *  Returns a read-only (constant) reference to the data at the last
 292        *  element of the %queue.
 293        */
 294       _GLIBCXX_NODISCARD
 295       const_reference
 296       back() const
 297       {
 298         __glibcxx_requires_nonempty();
 299         return c.back();
 300       }
 301
 302       /**
 303        *  @brief  Add data to the end of the %queue.
 304        *  @param  __x  Data to be added.
 305        *
 306        *  This is a typical %queue operation.  The function creates an
 307        *  element at the end of the %queue and assigns the given data
 308        *  to it.  The time complexity of the operation depends on the
 309        *  underlying sequence.
 310        */
 311       void
 312       push(const value_type& __x)
 313       { c.push_back(__x); }
 314
 315 #if __cplusplus >= 201103L
 316       void
 317       push(value_type&& __x)
 318       { c.push_back(std::move(__x)); }
 319
 320 #if __cplusplus > 201402L
 321       template<typename... _Args>
 322         decltype(auto)
 323         emplace(_Args&&... __args)
 324         { return c.emplace_back(std::forward<_Args>(__args)...); }
 325 #else
 326       template<typename... _Args>
 327         void
 328         emplace(_Args&&... __args)
 329         { c.emplace_back(std::forward<_Args>(__args)...); }
 330 #endif
 331 #endif
 332
 333 #if __glibcxx_containers_ranges // C++ >= 23
 334       template<__detail::__container_compatible_range<_Tp> _Rg>
 335         void
 336         push_range(_Rg&& __rg)
 337         {
 338           if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); })
 339             c.append_range(std::forward<_Rg>(__rg));
 340           else
 341             ranges::copy(__rg, std::back_inserter(c));
 342         }
 343 #endif
 344
 345       /**
 346        *  @brief  Removes first element.
 347        *
 348        *  This is a typical %queue operation.  It shrinks the %queue by one.
 349        *  The time complexity of the operation depends on the underlying
 350        *  sequence.
 351        *
 352        *  Note that no data is returned, and if the first element's
 353        *  data is needed, it should be retrieved before pop() is
 354        *  called.
 355        */
 356       void
 357       pop()
 358       {
 359         __glibcxx_requires_nonempty();
 360         c.pop_front();
 361       }
 362
 363 #if __cplusplus >= 201103L
 364       void
 365       swap(queue& __q)
 366 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 367       noexcept(__is_nothrow_swappable<_Sequence>::value)
 368 #else
 369       noexcept(__is_nothrow_swappable<_Tp>::value)
 370 #endif
 371       {
 372         using std::swap;
 373         swap(c, __q.c);
 374       }
 375 #endif // __cplusplus >= 201103L
 376
 377 #if __glibcxx_format_ranges
 378       friend class formatter<queue<_Tp, _Sequence>, char>;
 379       friend class formatter<queue<_Tp, _Sequence>, wchar_t>;
 380 #endif
 381     };
 382
 383 #if __cpp_deduction_guides >= 201606
 384   template<typename _Container,
 385            typename = _RequireNotAllocator<_Container>>
 386     queue(_Container) -> queue<typename _Container::value_type, _Container>;
 387
 388   template<typename _Container, typename _Allocator,
 389            typename = _RequireNotAllocator<_Container>>
 390     queue(_Container, _Allocator)
 391     -> queue<typename _Container::value_type, _Container>;
 392
 393 #ifdef __glibcxx_adaptor_iterator_pair_constructor
 394   template<typename _InputIterator,
 395            typename _ValT
 396              = typename iterator_traits<_InputIterator>::value_type,
 397            typename = _RequireInputIter<_InputIterator>>
 398     queue(_InputIterator, _InputIterator) -> queue<_ValT>;
 399
 400   template<typename _InputIterator, typename _Allocator,
 401            typename _ValT
 402              = typename iterator_traits<_InputIterator>::value_type,
 403            typename = _RequireInputIter<_InputIterator>,
 404            typename = _RequireAllocator<_Allocator>>
 405     queue(_InputIterator, _InputIterator, _Allocator)
 406     -> queue<_ValT, deque<_ValT, _Allocator>>;
 407 #endif
 408
 409 #if __glibcxx_containers_ranges // C++ >= 23
 410   template<ranges::input_range _Rg>
 411     queue(from_range_t, _Rg&&) -> queue<ranges::range_value_t<_Rg>>;
 412
 413   template<ranges::input_range _Rg, __allocator_like _Alloc>
 414     queue(from_range_t, _Rg&&, _Alloc)
 415     -> queue<ranges::range_value_t<_Rg>,
 416              deque<ranges::range_value_t<_Rg>, _Alloc>>;
 417 #endif
 418 #endif
 419
 420   /**
 421    *  @brief  Queue equality comparison.
 422    *  @param  __x  A %queue.
 423    *  @param  __y  A %queue of the same type as @a __x.
 424    *  @return  True iff the size and elements of the queues are equal.
 425    *
 426    *  This is an equivalence relation.  Complexity and semantics depend on the
 427    *  underlying sequence type, but the expected rules are:  this relation is
 428    *  linear in the size of the sequences, and queues are considered equivalent
 429    *  if their sequences compare equal.
 430   */
 431   template<typename _Tp, typename _Seq>
 432     _GLIBCXX_NODISCARD
 433     inline bool
 434     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 435     { return __x.c == __y.c; }
 436
 437   /**
 438    *  @brief  Queue ordering relation.
 439    *  @param  __x  A %queue.
 440    *  @param  __y  A %queue of the same type as @a x.
 441    *  @return  True iff @a __x is lexicographically less than @a __y.
 442    *
 443    *  This is an total ordering relation.  Complexity and semantics
 444    *  depend on the underlying sequence type, but the expected rules
 445    *  are: this relation is linear in the size of the sequences, the
 446    *  elements must be comparable with @c <, and
 447    *  std::lexicographical_compare() is usually used to make the
 448    *  determination.
 449   */
 450   template<typename _Tp, typename _Seq>
 451     _GLIBCXX_NODISCARD
 452     inline bool
 453     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 454     { return __x.c < __y.c; }
 455
 456   /// Based on operator==
 457   template<typename _Tp, typename _Seq>
 458     _GLIBCXX_NODISCARD
 459     inline bool
 460     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 461     { return !(__x == __y); }
 462
 463   /// Based on operator<
 464   template<typename _Tp, typename _Seq>
 465     _GLIBCXX_NODISCARD
 466     inline bool
 467     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 468     { return __y < __x; }
 469
 470   /// Based on operator<
 471   template<typename _Tp, typename _Seq>
 472     _GLIBCXX_NODISCARD
 473     inline bool
 474     operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 475     { return !(__y < __x); }
 476
 477   /// Based on operator<
 478   template<typename _Tp, typename _Seq>
 479     _GLIBCXX_NODISCARD
 480     inline bool
 481     operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 482     { return !(__x < __y); }
 483
 484 #if __cpp_lib_three_way_comparison
 485   template<typename _Tp, three_way_comparable _Seq>
 486     [[nodiscard]]
 487     inline compare_three_way_result_t<_Seq>
 488     operator<=>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
 489     { return __x.c <=> __y.c; }
 490 #endif
 491
 492 #if __cplusplus >= 201103L
 493   template<typename _Tp, typename _Seq>
 494     inline
 495 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 496     // Constrained free swap overload, see p0185r1
 497     typename enable_if<__is_swappable<_Seq>::value>::type
 498 #else
 499     void
 500 #endif
 501     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
 502     noexcept(noexcept(__x.swap(__y)))
 503     { __x.swap(__y); }
 504
 505   template<typename _Tp, typename _Seq, typename _Alloc>
 506     struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
 507     : public uses_allocator<_Seq, _Alloc>::type { };
 508 #endif // __cplusplus >= 201103L
 509
 510   /**
 511    *  @brief  A standard container automatically sorting its contents.
 512    *
 513    *  @ingroup sequences
 514    *
 515    *  @tparam _Tp  Type of element.
 516    *  @tparam _Sequence  Type of underlying sequence, defaults to vector<_Tp>.
 517    *  @tparam _Compare  Comparison function object type, defaults to
 518    *                    less<_Sequence::value_type>.
 519    *
 520    *  This is not a true container, but an @e adaptor.  It holds
 521    *  another container, and provides a wrapper interface to that
 522    *  container.  The wrapper is what enforces priority-based sorting
 523    *  and %queue behavior.  Very few of the standard container/sequence
 524    *  interface requirements are met (e.g., iterators).
 525    *
 526    *  The second template parameter defines the type of the underlying
 527    *  sequence/container.  It defaults to std::vector, but it can be
 528    *  any type that supports @c front(), @c push_back, @c pop_back,
 529    *  and random-access iterators, such as std::deque or an
 530    *  appropriate user-defined type.
 531    *
 532    *  The third template parameter supplies the means of making
 533    *  priority comparisons.  It defaults to @c less<value_type> but
 534    *  can be anything defining a strict weak ordering.
 535    *
 536    *  Members not found in @a normal containers are @c container_type,
 537    *  which is a typedef for the second Sequence parameter, and @c
 538    *  push, @c pop, and @c top, which are standard %queue operations.
 539    *
 540    *  @note No equality/comparison operators are provided for
 541    *  %priority_queue.
 542    *
 543    *  @note Sorting of the elements takes place as they are added to,
 544    *  and removed from, the %priority_queue using the
 545    *  %priority_queue's member functions.  If you access the elements
 546    *  by other means, and change their data such that the sorting
 547    *  order would be different, the %priority_queue will not re-sort
 548    *  the elements for you.  (How could it know to do so?)
 549   */
 550   template<typename _Tp, typename _Sequence = vector<_Tp>,
 551            typename _Compare  = less<typename _Sequence::value_type> >
 552     class priority_queue
 553     {
 554 #ifdef _GLIBCXX_CONCEPT_CHECKS
 555       // concept requirements
 556       typedef typename _Sequence::value_type _Sequence_value_type;
 557 # if __cplusplus < 201103L
 558       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 559 # endif
 560       __glibcxx_class_requires(_Sequence, _SequenceConcept)
 561       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
 562       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
 563       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
 564                                 _BinaryFunctionConcept)
 565 #endif
 566
 567 #if __cplusplus >= 201103L
 568       template<typename _Alloc>
 569         using _Uses = typename
 570           enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
 571
 572 #if __cplusplus >= 201703L
 573       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 574       // 2566. Requirements on the first template parameter of container
 575       // adaptors
 576       static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
 577           "value_type must be the same as the underlying container");
 578 #endif // C++17
 579 #endif // C++11
 580
 581     public:
 582       typedef typename  _Sequence::value_type           value_type;
 583       typedef typename  _Sequence::reference            reference;
 584       typedef typename  _Sequence::const_reference      const_reference;
 585       typedef typename  _Sequence::size_type            size_type;
 586       typedef           _Sequence                       container_type;
 587       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 588       // DR 2684. priority_queue lacking comparator typedef
 589       typedef          _Compare                         value_compare;
 590
 591     protected:
 592       //  See queue::c for notes on these names.
 593       _Sequence  c;
 594       _Compare   comp;
 595
 596     public:
 597       /**
 598        *  @brief  Default constructor creates no elements.
 599        */
 600 #if __cplusplus < 201103L
 601       explicit
 602       priority_queue(const _Compare& __x = _Compare(),
 603                      const _Sequence& __s = _Sequence())
 604       : c(__s), comp(__x)
 605       { std::make_heap(c.begin(), c.end(), comp); }
 606 #else
 607       template<typename _Seq = _Sequence, typename _Requires = typename
 608                enable_if<__and_<is_default_constructible<_Compare>,
 609                                 is_default_constructible<_Seq>>::value>::type>
 610         priority_queue()
 611         : c(), comp() { }
 612
 613       explicit
 614       priority_queue(const _Compare& __x, const _Sequence& __s)
 615       : c(__s), comp(__x)
 616       { std::make_heap(c.begin(), c.end(), comp); }
 617
 618       explicit
 619       priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
 620       : c(std::move(__s)), comp(__x)
 621       { std::make_heap(c.begin(), c.end(), comp); }
 622
 623       priority_queue(const priority_queue&) = default;
 624       priority_queue& operator=(const priority_queue&) = default;
 625
 626       priority_queue(priority_queue&& __q)
 627       noexcept(__and_<is_nothrow_move_constructible<_Sequence>,
 628                       is_nothrow_move_constructible<_Compare>>::value)
 629       : c(std::move(__q.c)), comp(std::move(__q.comp))
 630       { __q.c.clear(); }
 631
 632       priority_queue&
 633       operator=(priority_queue&& __q)
 634       noexcept(__and_<is_nothrow_move_assignable<_Sequence>,
 635                       is_nothrow_move_assignable<_Compare>>::value)
 636       {
 637         c = std::move(__q.c);
 638         __q.c.clear();
 639         comp = std::move(__q.comp);
 640         return *this;
 641       }
 642
 643       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 644         explicit
 645         priority_queue(const _Alloc& __a)
 646         : c(__a), comp() { }
 647
 648       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 649         priority_queue(const _Compare& __x, const _Alloc& __a)
 650         : c(__a), comp(__x) { }
 651
 652       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 653       // 2537. Constructors [...] taking allocators should call make_heap
 654       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 655         priority_queue(const _Compare& __x, const _Sequence& __c,
 656                        const _Alloc& __a)
 657         : c(__c, __a), comp(__x)
 658         { std::make_heap(c.begin(), c.end(), comp); }
 659
 660       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 661         priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
 662         : c(std::move(__c), __a), comp(__x)
 663         { std::make_heap(c.begin(), c.end(), comp); }
 664
 665       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 666         priority_queue(const priority_queue& __q, const _Alloc& __a)
 667         : c(__q.c, __a), comp(__q.comp) { }
 668
 669       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 670         priority_queue(priority_queue&& __q, const _Alloc& __a)
 671         : c(std::move(__q.c), __a), comp(std::move(__q.comp))
 672         { __q.c.clear(); }
 673 #endif
 674
 675       /**
 676        *  @brief  Builds a %queue from a range.
 677        *  @param  __first  An input iterator.
 678        *  @param  __last  An input iterator.
 679        *  @param  __x  A comparison functor describing a strict weak ordering.
 680        *  @param  __s  An initial sequence with which to start.
 681        *
 682        *  Begins by copying @a __s, inserting a copy of the elements
 683        *  from @a [first,last) into the copy of @a __s, then ordering
 684        *  the copy according to @a __x.
 685        *
 686        *  For more information on function objects, see the
 687        *  documentation on @link functors functor base classes@endlink.
 688        */
 689 #if __cplusplus < 201103L
 690       template<typename _InputIterator>
 691         priority_queue(_InputIterator __first, _InputIterator __last,
 692                        const _Compare& __x = _Compare(),
 693                        const _Sequence& __s = _Sequence())
 694         : c(__s), comp(__x)
 695         {
 696           __glibcxx_requires_valid_range(__first, __last);
 697           c.insert(c.end(), __first, __last);
 698           std::make_heap(c.begin(), c.end(), comp);
 699         }
 700 #else
 701       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 702       // 3529. priority_queue(first, last) should construct c with (first, last)
 703       template<typename _InputIterator,
 704                typename = std::_RequireInputIter<_InputIterator>>
 705         priority_queue(_InputIterator __first, _InputIterator __last,
 706                        const _Compare& __x = _Compare())
 707         : c(__first, __last), comp(__x)
 708         { std::make_heap(c.begin(), c.end(), comp); }
 709
 710       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 711       // 3522. Missing requirement on InputIterator template parameter
 712       template<typename _InputIterator,
 713                typename = std::_RequireInputIter<_InputIterator>>
 714         priority_queue(_InputIterator __first, _InputIterator __last,
 715                        const _Compare& __x, const _Sequence& __s)
 716         : c(__s), comp(__x)
 717         {
 718           __glibcxx_requires_valid_range(__first, __last);
 719           c.insert(c.end(), __first, __last);
 720           std::make_heap(c.begin(), c.end(), comp);
 721         }
 722
 723       template<typename _InputIterator,
 724                typename = std::_RequireInputIter<_InputIterator>>
 725         priority_queue(_InputIterator __first, _InputIterator __last,
 726                        const _Compare& __x, _Sequence&& __s)
 727         : c(std::move(__s)), comp(__x)
 728         {
 729           __glibcxx_requires_valid_range(__first, __last);
 730           c.insert(c.end(), __first, __last);
 731           std::make_heap(c.begin(), c.end(), comp);
 732         }
 733
 734       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 735       // 3506. Missing allocator-extended constructors for priority_queue
 736       template<typename _InputIterator, typename _Alloc,
 737                typename = std::_RequireInputIter<_InputIterator>,
 738                typename _Requires = _Uses<_Alloc>>
 739         priority_queue(_InputIterator __first, _InputIterator __last,
 740                        const _Alloc& __alloc)
 741         : c(__first, __last, __alloc), comp()
 742         { std::make_heap(c.begin(), c.end(), comp); }
 743
 744       template<typename _InputIterator, typename _Alloc,
 745                typename = std::_RequireInputIter<_InputIterator>,
 746                typename _Requires = _Uses<_Alloc>>
 747         priority_queue(_InputIterator __first, _InputIterator __last,
 748                        const _Compare& __x, const _Alloc& __alloc)
 749         : c(__first, __last, __alloc), comp(__x)
 750         { std::make_heap(c.begin(), c.end(), comp); }
 751
 752       template<typename _InputIterator, typename _Alloc,
 753                typename = std::_RequireInputIter<_InputIterator>,
 754                typename _Requires = _Uses<_Alloc>>
 755         priority_queue(_InputIterator __first, _InputIterator __last,
 756                        const _Compare& __x, const _Sequence& __s,
 757                        const _Alloc& __alloc)
 758         : c(__s, __alloc), comp(__x)
 759         {
 760           __glibcxx_requires_valid_range(__first, __last);
 761           c.insert(c.end(), __first, __last);
 762           std::make_heap(c.begin(), c.end(), comp);
 763         }
 764
 765       template<typename _InputIterator, typename _Alloc,
 766                typename _Requires = _Uses<_Alloc>>
 767         priority_queue(_InputIterator __first, _InputIterator __last,
 768                        const _Compare& __x, _Sequence&& __s,
 769                        const _Alloc& __alloc)
 770         : c(std::move(__s), __alloc), comp(__x)
 771         {
 772           __glibcxx_requires_valid_range(__first, __last);
 773           c.insert(c.end(), __first, __last);
 774           std::make_heap(c.begin(), c.end(), comp);
 775         }
 776 #endif
 777
 778 #if __glibcxx_containers_ranges // C++ >= 23
 779       /**
 780        * @brief Construct a priority_queue from a range.
 781        * @since C++23
 782        *
 783        * @{
 784        */
 785       template<__detail::__container_compatible_range<_Tp> _Rg>
 786         priority_queue(from_range_t, _Rg&& __rg,
 787                        const _Compare& __x = _Compare())
 788         : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg))), comp(__x)
 789         { std::make_heap(c.begin(), c.end(), comp); }
 790
 791       template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc>
 792         priority_queue(from_range_t, _Rg&& __rg, const _Compare& __x,
 793                        const _Alloc& __a)
 794         : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp(__x)
 795         { std::make_heap(c.begin(), c.end(), comp); }
 796
 797       template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc>
 798         priority_queue(from_range_t, _Rg&& __rg, const _Alloc& __a)
 799         : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp()
 800         { std::make_heap(c.begin(), c.end(), comp); }
 801       /// @}
 802 #endif
 803
 804       /**
 805        *  Returns true if the %queue is empty.
 806        */
 807       _GLIBCXX_NODISCARD bool
 808       empty() const
 809       { return c.empty(); }
 810
 811       /**  Returns the number of elements in the %queue.  */
 812       _GLIBCXX_NODISCARD
 813       size_type
 814       size() const
 815       { return c.size(); }
 816
 817       /**
 818        *  Returns a read-only (constant) reference to the data at the first
 819        *  element of the %queue.
 820        */
 821       _GLIBCXX_NODISCARD
 822       const_reference
 823       top() const
 824       {
 825         __glibcxx_requires_nonempty();
 826         return c.front();
 827       }
 828
 829       /**
 830        *  @brief  Add data to the %queue.
 831        *  @param  __x  Data to be added.
 832        *
 833        *  This is a typical %queue operation.
 834        *  The time complexity of the operation depends on the underlying
 835        *  sequence.
 836        */
 837       void
 838       push(const value_type& __x)
 839       {
 840         c.push_back(__x);
 841         std::push_heap(c.begin(), c.end(), comp);
 842       }
 843
 844 #if __cplusplus >= 201103L
 845       void
 846       push(value_type&& __x)
 847       {
 848         c.push_back(std::move(__x));
 849         std::push_heap(c.begin(), c.end(), comp);
 850       }
 851
 852       template<typename... _Args>
 853         void
 854         emplace(_Args&&... __args)
 855         {
 856           c.emplace_back(std::forward<_Args>(__args)...);
 857           std::push_heap(c.begin(), c.end(), comp);
 858         }
 859 #endif
 860
 861 #if __glibcxx_containers_ranges // C++ >= 23
 862       template<__detail::__container_compatible_range<_Tp> _Rg>
 863         void
 864         push_range(_Rg&& __rg)
 865         {
 866           if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); })
 867             c.append_range(std::forward<_Rg>(__rg));
 868           else
 869             ranges::copy(__rg, std::back_inserter(c));
 870           std::make_heap(c.begin(), c.end(), comp);
 871         }
 872 #endif
 873
 874       /**
 875        *  @brief  Removes first element.
 876        *
 877        *  This is a typical %queue operation.  It shrinks the %queue
 878        *  by one.  The time complexity of the operation depends on the
 879        *  underlying sequence.
 880        *
 881        *  Note that no data is returned, and if the first element's
 882        *  data is needed, it should be retrieved before pop() is
 883        *  called.
 884        */
 885       void
 886       pop()
 887       {
 888         __glibcxx_requires_nonempty();
 889         std::pop_heap(c.begin(), c.end(), comp);
 890         c.pop_back();
 891       }
 892
 893 #if __cplusplus >= 201103L
 894       void
 895       swap(priority_queue& __pq)
 896       noexcept(__and_<
 897 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 898                  __is_nothrow_swappable<_Sequence>,
 899 #else
 900                  __is_nothrow_swappable<_Tp>,
 901 #endif
 902                  __is_nothrow_swappable<_Compare>
 903                >::value)
 904       {
 905         using std::swap;
 906         swap(c, __pq.c);
 907         swap(comp, __pq.comp);
 908       }
 909 #endif // __cplusplus >= 201103L
 910
 911 #if __glibcxx_format_ranges
 912       friend class formatter<priority_queue<_Tp, _Sequence, _Compare>, char>;
 913       friend class formatter<priority_queue<_Tp, _Sequence, _Compare>, wchar_t>;
 914 #endif
 915     };
 916
 917 #if __cpp_deduction_guides >= 201606
 918   template<typename _Compare, typename _Container,
 919            typename = _RequireNotAllocator<_Compare>,
 920            typename = _RequireNotAllocator<_Container>>
 921     priority_queue(_Compare, _Container)
 922     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 923
 924   template<typename _InputIterator, typename _ValT
 925            = typename iterator_traits<_InputIterator>::value_type,
 926            typename _Compare = less<_ValT>,
 927            typename _Container = vector<_ValT>,
 928            typename = _RequireInputIter<_InputIterator>,
 929            typename = _RequireNotAllocator<_Compare>,
 930            typename = _RequireNotAllocator<_Container>>
 931     priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
 932                    _Container = _Container())
 933     -> priority_queue<_ValT, _Container, _Compare>;
 934
 935   template<typename _Compare, typename _Container, typename _Allocator,
 936            typename = _RequireNotAllocator<_Compare>,
 937            typename = _RequireNotAllocator<_Container>>
 938     priority_queue(_Compare, _Container, _Allocator)
 939     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 940
 941 #if __glibcxx_containers_ranges // C++ >= 23
 942   template<ranges::input_range _Rg,
 943            __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
 944            __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>>
 945     priority_queue(from_range_t, _Rg&&, _Compare = _Compare(),
 946                    _Alloc = _Alloc())
 947       -> priority_queue<ranges::range_value_t<_Rg>,
 948                         vector<ranges::range_value_t<_Rg>, _Alloc>,
 949                         _Compare>;
 950
 951   template<ranges::input_range _Rg, __allocator_like _Alloc>
 952     priority_queue(from_range_t, _Rg&&, _Alloc)
 953       -> priority_queue<ranges::range_value_t<_Rg>,
 954                         vector<ranges::range_value_t<_Rg>, _Alloc>>;
 955 #endif
 956 #endif
 957
 958   // No equality/comparison operators are provided for priority_queue.
 959
 960 #if __cplusplus >= 201103L
 961   template<typename _Tp, typename _Sequence, typename _Compare>
 962     inline
 963 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
 964     // Constrained free swap overload, see p0185r1
 965     typename enable_if<__and_<__is_swappable<_Sequence>,
 966                               __is_swappable<_Compare>>::value>::type
 967 #else
 968     void
 969 #endif
 970     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
 971          priority_queue<_Tp, _Sequence, _Compare>& __y)
 972     noexcept(noexcept(__x.swap(__y)))
 973     { __x.swap(__y); }
 974
 975   template<typename _Tp, typename _Sequence, typename _Compare,
 976            typename _Alloc>
 977     struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
 978     : public uses_allocator<_Sequence, _Alloc>::type { };
 979 #endif // __cplusplus >= 201103L
 980
 981 _GLIBCXX_END_NAMESPACE_VERSION
 982 } // namespace
 983
 984 #endif /* _STL_QUEUE_H */