libcxx/include/queue

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_QUEUE
  11 #define _LIBCPP_QUEUE
  12
  13 /*
  14     queue synopsis
  15
  16 namespace std
  17 {
  18
  19 template <class T, class Container = deque<T>>
  20 class queue
  21 {
  22 public:
  23     typedef Container                                container_type;
  24     typedef typename container_type::value_type      value_type;
  25     typedef typename container_type::reference       reference;
  26     typedef typename container_type::const_reference const_reference;
  27     typedef typename container_type::size_type       size_type;
  28
  29 protected:
  30     container_type c;
  31
  32 public:
  33     queue() = default;
  34     ~queue() = default;
  35
  36     queue(const queue& q) = default;
  37     queue(queue&& q) = default;
  38
  39     queue& operator=(const queue& q) = default;
  40     queue& operator=(queue&& q) = default;
  41
  42     explicit queue(const container_type& c);
  43     explicit queue(container_type&& c)
  44     template<class InputIterator>
  45         queue(InputIterator first, InputIterator last); // since C++23
  46     template<container-compatible-range<T> R> queue(from_range_t, R&& rg); // since C++23
  47     template <class Alloc>
  48         explicit queue(const Alloc& a);
  49     template <class Alloc>
  50         queue(const container_type& c, const Alloc& a);
  51     template <class Alloc>
  52         queue(container_type&& c, const Alloc& a);
  53     template <class Alloc>
  54         queue(const queue& q, const Alloc& a);
  55     template <class Alloc>
  56         queue(queue&& q, const Alloc& a);
  57     template <class InputIterator, class Alloc>
  58         queue(InputIterator first, InputIterator last, const Alloc&); // since C++23
  59     template<container-compatible-range<T> R, class Alloc>
  60         queue(from_range_t, R&& rg, const Alloc&); // since C++23
  61
  62     bool      empty() const;
  63     size_type size() const;
  64
  65     reference       front();
  66     const_reference front() const;
  67     reference       back();
  68     const_reference back() const;
  69
  70     void push(const value_type& v);
  71     void push(value_type&& v);
  72     template<container-compatible-range<T> R>
  73       void push_range(R&& rg); // C++23
  74     template <class... Args> reference emplace(Args&&... args); // reference in C++17
  75     void pop();
  76
  77     void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
  78 };
  79
  80 template<class Container>
  81   queue(Container) -> queue<typename Container::value_type, Container>; // C++17
  82
  83 template<class InputIterator>
  84   queue(InputIterator, InputIterator) -> queue<iter-value-type<InputIterator>>; // since C++23
  85
  86 template<ranges::input_range R>
  87   queue(from_range_t, R&&) -> queue<ranges::range_value_t<R>>; // since C++23
  88
  89 template<class Container, class Allocator>
  90   queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17
  91
  92 template<class InputIterator, class Allocator>
  93   queue(InputIterator, InputIterator, Allocator)
  94   -> queue<iter-value-type<InputIterator>,
  95            deque<iter-value-type<InputIterator>, Allocator>>; // since C++23
  96
  97 template<ranges::input_range R, class Allocator>
  98     queue(from_range_t, R&&, Allocator)
  99       -> queue<ranges::range_value_t<R>, deque<ranges::range_value_t<R>, Allocator>>; // since C++23
 100
 101 template <class T, class Container>
 102   bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
 103
 104 template <class T, class Container>
 105   bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
 106
 107 template <class T, class Container>
 108   bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
 109
 110 template <class T, class Container>
 111   bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
 112
 113 template <class T, class Container>
 114   bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
 115
 116 template <class T, class Container>
 117   bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
 118
 119 template<class T, three_way_comparable Container>
 120   compare_three_way_result_t<Container>
 121     operator<=>(const queue<T, Container>& x, const queue<T, Container>& y);  // since C++20
 122
 123 template <class T, class Container>
 124   void swap(queue<T, Container>& x, queue<T, Container>& y)
 125   noexcept(noexcept(x.swap(y)));
 126
 127 template <class T, class Container = vector<T>,
 128           class Compare = less<typename Container::value_type>>
 129 class priority_queue
 130 {
 131 public:
 132     typedef Container                                container_type;
 133     typedef typename container_type::value_type      value_type;
 134     typedef typename container_type::reference       reference;
 135     typedef typename container_type::const_reference const_reference;
 136     typedef typename container_type::size_type       size_type;
 137
 138 protected:
 139     container_type c;
 140     Compare comp;
 141
 142 public:
 143     priority_queue() : priority_queue(Compare()) {} // C++20
 144     explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
 145     priority_queue(const Compare& x, const Container&);
 146     explicit priority_queue(const Compare& x = Compare(), Container&& = Container()); // before C++20
 147     priority_queue(const Compare& x, Container&&); // C++20
 148     template <class InputIterator>
 149         priority_queue(InputIterator first, InputIterator last,
 150                        const Compare& comp = Compare());
 151     template <class InputIterator>
 152         priority_queue(InputIterator first, InputIterator last,
 153                        const Compare& comp, const Container& c);
 154     template <class InputIterator>
 155         priority_queue(InputIterator first, InputIterator last,
 156                        const Compare& comp, Container&& c);
 157     template <container-compatible-range<T> R>
 158         priority_queue(from_range_t, R&& rg, const Compare& x = Compare()); // since C++23
 159     template <class Alloc>
 160         explicit priority_queue(const Alloc& a);
 161     template <class Alloc>
 162         priority_queue(const Compare& comp, const Alloc& a);
 163     template <class Alloc>
 164         priority_queue(const Compare& comp, const Container& c,
 165                        const Alloc& a);
 166     template <class Alloc>
 167         priority_queue(const Compare& comp, Container&& c,
 168                        const Alloc& a);
 169     template <class InputIterator>
 170         priority_queue(InputIterator first, InputIterator last,
 171                        const Alloc& a);
 172     template <class InputIterator>
 173         priority_queue(InputIterator first, InputIterator last,
 174                        const Compare& comp, const Alloc& a);
 175     template <class InputIterator>
 176         priority_queue(InputIterator first, InputIterator last,
 177                        const Compare& comp, const Container& c, const Alloc& a);
 178     template <class InputIterator>
 179         priority_queue(InputIterator first, InputIterator last,
 180                        const Compare& comp, Container&& c, const Alloc& a);
 181     template <container-compatible-range<T> R, class Alloc>
 182       priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&); // since C++23
 183     template <container-compatible-range<T> R, class Alloc>
 184       priority_queue(from_range_t, R&& rg, const Alloc&); // since C++23
 185     template <class Alloc>
 186         priority_queue(const priority_queue& q, const Alloc& a);
 187     template <class Alloc>
 188         priority_queue(priority_queue&& q, const Alloc& a);
 189
 190     bool            empty() const;
 191     size_type       size() const;
 192     const_reference top() const;
 193
 194     void push(const value_type& v);
 195     void push(value_type&& v);
 196     template<container-compatible-range<T> R>
 197       void push_range(R&& rg); // C++23
 198     template <class... Args> void emplace(Args&&... args);
 199     void pop();
 200
 201     void swap(priority_queue& q)
 202         noexcept(is_nothrow_swappable_v<Container> &&
 203                  is_nothrow_swappable_v<Comp>)
 204 };
 205
 206 template <class Compare, class Container>
 207 priority_queue(Compare, Container)
 208     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 209
 210 template<class InputIterator,
 211          class Compare = less<iter-value-type<InputIterator>>,
 212          class Container = vector<iter-value-type<InputIterator>>>
 213 priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
 214     -> priority_queue<iter-value-type<InputIterator>, Container, Compare>; // C++17
 215
 216 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>>
 217   priority_queue(from_range_t, R&&, Compare = Compare())
 218     -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>>, Compare>; // C++23
 219
 220 template<class Compare, class Container, class Allocator>
 221 priority_queue(Compare, Container, Allocator)
 222     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 223
 224 template<class InputIterator, class Allocator>
 225 priority_queue(InputIterator, InputIterator, Allocator)
 226     -> priority_queue<iter-value-type<InputIterator>,
 227                       vector<iter-value-type<InputIterator>, Allocator>,
 228                       less<iter-value-type<InputIterator>>>; // C++17
 229
 230 template<class InputIterator, class Compare, class Allocator>
 231 priority_queue(InputIterator, InputIterator, Compare, Allocator)
 232     -> priority_queue<iter-value-type<InputIterator>,
 233                       vector<iter-value-type<InputIterator>, Allocator>, Compare>; // C++17
 234
 235 template<class InputIterator, class Compare, class Container, class Allocator>
 236 priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
 237     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 238
 239 template<ranges::input_range R, class Compare, class Allocator>
 240   priority_queue(from_range_t, R&&, Compare, Allocator)
 241     -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>,
 242                         Compare>; // C++23
 243
 244 template<ranges::input_range R, class Allocator>
 245   priority_queue(from_range_t, R&&, Allocator)
 246     -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>>; // C++23
 247
 248 template <class T, class Container, class Compare>
 249   void swap(priority_queue<T, Container, Compare>& x,
 250             priority_queue<T, Container, Compare>& y)
 251             noexcept(noexcept(x.swap(y)));
 252
 253 }  // std
 254
 255 */
 256
 257 #include <__algorithm/make_heap.h>
 258 #include <__algorithm/pop_heap.h>
 259 #include <__algorithm/push_heap.h>
 260 #include <__algorithm/ranges_copy.h>
 261 #include <__config>
 262 #include <__functional/operations.h>
 263 #include <__fwd/deque.h>
 264 #include <__fwd/queue.h>
 265 #include <__iterator/back_insert_iterator.h>
 266 #include <__iterator/iterator_traits.h>
 267 #include <__memory/uses_allocator.h>
 268 #include <__ranges/access.h>
 269 #include <__ranges/concepts.h>
 270 #include <__ranges/container_compatible_range.h>
 271 #include <__ranges/from_range.h>
 272 #include <__utility/forward.h>
 273 #include <deque>
 274 #include <vector>
 275 #include <version>
 276
 277 // standard-mandated includes
 278
 279 // [queue.syn]
 280 #include <compare>
 281 #include <initializer_list>
 282
 283 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 284 #  pragma GCC system_header
 285 #endif
 286
 287 _LIBCPP_PUSH_MACROS
 288 #include <__undef_macros>
 289
 290 _LIBCPP_BEGIN_NAMESPACE_STD
 291
 292 template <class _Tp, class _Container>
 293 _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
 294
 295 template <class _Tp, class _Container>
 296 _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
 297
 298 template <class _Tp, class _Container /*= deque<_Tp>*/>
 299 class _LIBCPP_TEMPLATE_VIS queue {
 300 public:
 301   typedef _Container container_type;
 302   typedef typename container_type::value_type value_type;
 303   typedef typename container_type::reference reference;
 304   typedef typename container_type::const_reference const_reference;
 305   typedef typename container_type::size_type size_type;
 306   static_assert(is_same<_Tp, value_type>::value, "");
 307
 308 protected:
 309   container_type c;
 310
 311 public:
 312   _LIBCPP_HIDE_FROM_ABI queue() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {}
 313
 314   _LIBCPP_HIDE_FROM_ABI queue(const queue& __q) : c(__q.c) {}
 315
 316 #if _LIBCPP_STD_VER >= 23
 317   template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
 318   _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
 319
 320   template <_ContainerCompatibleRange<_Tp> _Range>
 321   _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}
 322
 323   template <class _InputIterator,
 324             class _Alloc,
 325             __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
 326             __enable_if_t<uses_allocator<container_type, _Alloc>::value, int>        = 0>
 327   _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc)
 328       : c(__first, __second, __alloc) {}
 329
 330   template <_ContainerCompatibleRange<_Tp> _Range,
 331             class _Alloc,
 332             __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 333   _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range, const _Alloc& __alloc)
 334       : c(from_range, std::forward<_Range>(__range), __alloc) {}
 335
 336 #endif
 337
 338   _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) {
 339     c = __q.c;
 340     return *this;
 341   }
 342
 343 #ifndef _LIBCPP_CXX03_LANG
 344   _LIBCPP_HIDE_FROM_ABI queue(queue&& __q) noexcept(is_nothrow_move_constructible<container_type>::value)
 345       : c(std::move(__q.c)) {}
 346
 347   _LIBCPP_HIDE_FROM_ABI queue& operator=(queue&& __q) noexcept(is_nothrow_move_assignable<container_type>::value) {
 348     c = std::move(__q.c);
 349     return *this;
 350   }
 351 #endif // _LIBCPP_CXX03_LANG
 352
 353   _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {}
 354 #ifndef _LIBCPP_CXX03_LANG
 355   _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {}
 356 #endif // _LIBCPP_CXX03_LANG
 357
 358   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 359   _LIBCPP_HIDE_FROM_ABI explicit queue(const _Alloc& __a) : c(__a) {}
 360
 361   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 362   _LIBCPP_HIDE_FROM_ABI queue(const queue& __q, const _Alloc& __a) : c(__q.c, __a) {}
 363
 364   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 365   _LIBCPP_HIDE_FROM_ABI queue(const container_type& __c, const _Alloc& __a) : c(__c, __a) {}
 366
 367 #ifndef _LIBCPP_CXX03_LANG
 368   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 369   _LIBCPP_HIDE_FROM_ABI queue(container_type&& __c, const _Alloc& __a) : c(std::move(__c), __a) {}
 370
 371   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 372   _LIBCPP_HIDE_FROM_ABI queue(queue&& __q, const _Alloc& __a) : c(std::move(__q.c), __a) {}
 373 #endif // _LIBCPP_CXX03_LANG
 374
 375   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
 376   _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
 377
 378   _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); }
 379   _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); }
 380   _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); }
 381   _LIBCPP_HIDE_FROM_ABI const_reference back() const { return c.back(); }
 382
 383   _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); }
 384 #ifndef _LIBCPP_CXX03_LANG
 385   _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); }
 386
 387 #  if _LIBCPP_STD_VER >= 23
 388   template <_ContainerCompatibleRange<_Tp> _Range>
 389   _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
 390     if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
 391       c.append_range(std::forward<_Range>(__range));
 392     } else {
 393       ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
 394     }
 395   }
 396 #  endif
 397
 398   template <class... _Args>
 399   _LIBCPP_HIDE_FROM_ABI
 400 #  if _LIBCPP_STD_VER >= 17
 401   decltype(auto)
 402   emplace(_Args&&... __args) {
 403     return c.emplace_back(std::forward<_Args>(__args)...);
 404   }
 405 #  else
 406   void
 407   emplace(_Args&&... __args) {
 408     c.emplace_back(std::forward<_Args>(__args)...);
 409   }
 410 #  endif
 411 #endif // _LIBCPP_CXX03_LANG
 412   _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_front(); }
 413
 414   _LIBCPP_HIDE_FROM_ABI void swap(queue& __q) _NOEXCEPT_(__is_nothrow_swappable_v<container_type>) {
 415     using std::swap;
 416     swap(c, __q.c);
 417   }
 418
 419   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
 420
 421   template <class _T1, class _OtherContainer>
 422   friend _LIBCPP_HIDE_FROM_ABI bool
 423   operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
 424
 425   template <class _T1, class _OtherContainer>
 426   friend _LIBCPP_HIDE_FROM_ABI bool
 427   operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
 428 };
 429
 430 #if _LIBCPP_STD_VER >= 17
 431 template <class _Container, class = enable_if_t<!__is_allocator<_Container>::value> >
 432 queue(_Container) -> queue<typename _Container::value_type, _Container>;
 433
 434 template <class _Container,
 435           class _Alloc,
 436           class = enable_if_t<!__is_allocator<_Container>::value>,
 437           class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
 438 queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>;
 439 #endif
 440
 441 #if _LIBCPP_STD_VER >= 23
 442 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
 443 queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>;
 444
 445 template <ranges::input_range _Range>
 446 queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>;
 447
 448 template <class _InputIterator,
 449           class _Alloc,
 450           __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
 451           __enable_if_t<__is_allocator<_Alloc>::value, int>                        = 0>
 452 queue(_InputIterator,
 453       _InputIterator,
 454       _Alloc) -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
 455
 456 template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
 457 queue(from_range_t,
 458       _Range&&,
 459       _Alloc) -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;
 460 #endif
 461
 462 template <class _Tp, class _Container>
 463 inline _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 464   return __x.c == __y.c;
 465 }
 466
 467 template <class _Tp, class _Container>
 468 inline _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 469   return __x.c < __y.c;
 470 }
 471
 472 template <class _Tp, class _Container>
 473 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 474   return !(__x == __y);
 475 }
 476
 477 template <class _Tp, class _Container>
 478 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 479   return __y < __x;
 480 }
 481
 482 template <class _Tp, class _Container>
 483 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 484   return !(__x < __y);
 485 }
 486
 487 template <class _Tp, class _Container>
 488 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 489   return !(__y < __x);
 490 }
 491
 492 #if _LIBCPP_STD_VER >= 20
 493
 494 template <class _Tp, three_way_comparable _Container>
 495 _LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>
 496 operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 497   // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors
 498   return __x.__get_container() <=> __y.__get_container();
 499 }
 500
 501 #endif
 502
 503 template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0>
 504 inline _LIBCPP_HIDE_FROM_ABI void swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
 505     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
 506   __x.swap(__y);
 507 }
 508
 509 template <class _Tp, class _Container, class _Alloc>
 510 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> {
 511 };
 512
 513 template <class _Tp, class _Container, class _Compare>
 514 class _LIBCPP_TEMPLATE_VIS priority_queue {
 515 public:
 516   typedef _Container container_type;
 517   typedef _Compare value_compare;
 518   typedef typename container_type::value_type value_type;
 519   typedef typename container_type::reference reference;
 520   typedef typename container_type::const_reference const_reference;
 521   typedef typename container_type::size_type size_type;
 522   static_assert(is_same<_Tp, value_type>::value, "");
 523
 524 protected:
 525   container_type c;
 526   value_compare comp;
 527
 528 public:
 529   _LIBCPP_HIDE_FROM_ABI priority_queue() _NOEXCEPT_(
 530       is_nothrow_default_constructible<container_type>::value&& is_nothrow_default_constructible<value_compare>::value)
 531       : c(), comp() {}
 532
 533   _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
 534
 535   _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(const priority_queue& __q) {
 536     c    = __q.c;
 537     comp = __q.comp;
 538     return *this;
 539   }
 540
 541 #ifndef _LIBCPP_CXX03_LANG
 542   _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q) noexcept(
 543       is_nothrow_move_constructible<container_type>::value && is_nothrow_move_constructible<value_compare>::value)
 544       : c(std::move(__q.c)), comp(std::move(__q.comp)) {}
 545
 546   _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(priority_queue&& __q) noexcept(
 547       is_nothrow_move_assignable<container_type>::value && is_nothrow_move_assignable<value_compare>::value) {
 548     c    = std::move(__q.c);
 549     comp = std::move(__q.comp);
 550     return *this;
 551   }
 552 #endif // _LIBCPP_CXX03_LANG
 553
 554   _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const value_compare& __comp) : c(), comp(__comp) {}
 555   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c);
 556 #ifndef _LIBCPP_CXX03_LANG
 557   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c);
 558 #endif
 559   template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
 560   _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare());
 561
 562   template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
 563   _LIBCPP_HIDE_FROM_ABI
 564   priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c);
 565
 566 #ifndef _LIBCPP_CXX03_LANG
 567   template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
 568   _LIBCPP_HIDE_FROM_ABI
 569   priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c);
 570 #endif // _LIBCPP_CXX03_LANG
 571
 572 #if _LIBCPP_STD_VER >= 23
 573   template <_ContainerCompatibleRange<_Tp> _Range>
 574   _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare())
 575       : c(from_range, std::forward<_Range>(__range)), comp(__comp) {
 576     std::make_heap(c.begin(), c.end(), comp);
 577   }
 578 #endif
 579
 580   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 581   _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const _Alloc& __a);
 582
 583   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 584   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const _Alloc& __a);
 585
 586   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 587   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c, const _Alloc& __a);
 588
 589   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 590   _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q, const _Alloc& __a);
 591
 592 #ifndef _LIBCPP_CXX03_LANG
 593   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 594   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c, const _Alloc& __a);
 595
 596   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 597   _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q, const _Alloc& __a);
 598 #endif // _LIBCPP_CXX03_LANG
 599
 600   template <
 601       class _InputIter,
 602       class _Alloc,
 603       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 604                     int> = 0>
 605   _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a);
 606
 607   template <
 608       class _InputIter,
 609       class _Alloc,
 610       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 611                     int> = 0>
 612   _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a);
 613
 614   template <
 615       class _InputIter,
 616       class _Alloc,
 617       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 618                     int> = 0>
 619   _LIBCPP_HIDE_FROM_ABI priority_queue(
 620       _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a);
 621
 622 #ifndef _LIBCPP_CXX03_LANG
 623   template <
 624       class _InputIter,
 625       class _Alloc,
 626       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 627                     int> = 0>
 628   _LIBCPP_HIDE_FROM_ABI
 629   priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a);
 630 #endif // _LIBCPP_CXX03_LANG
 631
 632 #if _LIBCPP_STD_VER >= 23
 633
 634   template <_ContainerCompatibleRange<_Tp> _Range,
 635             class _Alloc,
 636             class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
 637   _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a)
 638       : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) {
 639     std::make_heap(c.begin(), c.end(), comp);
 640   }
 641
 642   template <_ContainerCompatibleRange<_Tp> _Range,
 643             class _Alloc,
 644             class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
 645   _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a)
 646       : c(from_range, std::forward<_Range>(__range), __a), comp() {
 647     std::make_heap(c.begin(), c.end(), comp);
 648   }
 649
 650 #endif
 651
 652   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
 653   _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
 654   _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.front(); }
 655
 656   _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v);
 657 #ifndef _LIBCPP_CXX03_LANG
 658   _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v);
 659
 660 #  if _LIBCPP_STD_VER >= 23
 661   template <_ContainerCompatibleRange<_Tp> _Range>
 662   _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
 663     if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
 664       c.append_range(std::forward<_Range>(__range));
 665     } else {
 666       ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
 667     }
 668
 669     std::make_heap(c.begin(), c.end(), comp);
 670   }
 671 #  endif
 672
 673   template <class... _Args>
 674   _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args);
 675 #endif // _LIBCPP_CXX03_LANG
 676   _LIBCPP_HIDE_FROM_ABI void pop();
 677
 678   _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q)
 679       _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>);
 680
 681   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
 682 };
 683
 684 #if _LIBCPP_STD_VER >= 17
 685 template <class _Compare,
 686           class _Container,
 687           class = enable_if_t<!__is_allocator<_Compare>::value>,
 688           class = enable_if_t<!__is_allocator<_Container>::value> >
 689 priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 690
 691 template <class _InputIterator,
 692           class _Compare   = less<__iter_value_type<_InputIterator>>,
 693           class _Container = vector<__iter_value_type<_InputIterator>>,
 694           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 695           class            = enable_if_t<!__is_allocator<_Compare>::value>,
 696           class            = enable_if_t<!__is_allocator<_Container>::value> >
 697 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
 698     -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
 699
 700 template <class _Compare,
 701           class _Container,
 702           class _Alloc,
 703           class = enable_if_t<!__is_allocator<_Compare>::value>,
 704           class = enable_if_t<!__is_allocator<_Container>::value>,
 705           class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
 706 priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 707
 708 template <class _InputIterator,
 709           class _Allocator,
 710           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 711           class = enable_if_t<__is_allocator<_Allocator>::value> >
 712 priority_queue(_InputIterator, _InputIterator, _Allocator)
 713     -> priority_queue<__iter_value_type<_InputIterator>,
 714                       vector<__iter_value_type<_InputIterator>, _Allocator>,
 715                       less<__iter_value_type<_InputIterator>>>;
 716
 717 template <class _InputIterator,
 718           class _Compare,
 719           class _Allocator,
 720           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 721           class = enable_if_t<!__is_allocator<_Compare>::value>,
 722           class = enable_if_t<__is_allocator<_Allocator>::value> >
 723 priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
 724     -> priority_queue<__iter_value_type<_InputIterator>,
 725                       vector<__iter_value_type<_InputIterator>, _Allocator>,
 726                       _Compare>;
 727
 728 template <class _InputIterator,
 729           class _Compare,
 730           class _Container,
 731           class _Alloc,
 732           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 733           class = enable_if_t<!__is_allocator<_Compare>::value>,
 734           class = enable_if_t<!__is_allocator<_Container>::value>,
 735           class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
 736 priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
 737     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 738 #endif
 739
 740 #if _LIBCPP_STD_VER >= 23
 741
 742 template <ranges::input_range _Range,
 743           class _Compare = less<ranges::range_value_t<_Range>>,
 744           class          = enable_if_t<!__is_allocator<_Compare>::value>>
 745 priority_queue(from_range_t, _Range&&, _Compare = _Compare())
 746     -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>;
 747
 748 template <ranges::input_range _Range,
 749           class _Compare,
 750           class _Alloc,
 751           class = enable_if_t<!__is_allocator<_Compare>::value>,
 752           class = enable_if_t<__is_allocator<_Alloc>::value>>
 753 priority_queue(from_range_t, _Range&&, _Compare, _Alloc)
 754     -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>;
 755
 756 template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator<_Alloc>::value>>
 757 priority_queue(from_range_t, _Range&&, _Alloc)
 758     -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>;
 759
 760 #endif
 761
 762 template <class _Tp, class _Container, class _Compare>
 763 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, const container_type& __c)
 764     : c(__c), comp(__comp) {
 765   std::make_heap(c.begin(), c.end(), comp);
 766 }
 767
 768 #ifndef _LIBCPP_CXX03_LANG
 769
 770 template <class _Tp, class _Container, class _Compare>
 771 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, container_type&& __c)
 772     : c(std::move(__c)), comp(__comp) {
 773   std::make_heap(c.begin(), c.end(), comp);
 774 }
 775
 776 #endif // _LIBCPP_CXX03_LANG
 777
 778 template <class _Tp, class _Container, class _Compare>
 779 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
 780 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 781     _InputIter __f, _InputIter __l, const value_compare& __comp)
 782     : c(__f, __l), comp(__comp) {
 783   std::make_heap(c.begin(), c.end(), comp);
 784 }
 785
 786 template <class _Tp, class _Container, class _Compare>
 787 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
 788 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 789     _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c)
 790     : c(__c), comp(__comp) {
 791   c.insert(c.end(), __f, __l);
 792   std::make_heap(c.begin(), c.end(), comp);
 793 }
 794
 795 #ifndef _LIBCPP_CXX03_LANG
 796
 797 template <class _Tp, class _Container, class _Compare>
 798 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
 799 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 800     _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c)
 801     : c(std::move(__c)), comp(__comp) {
 802   c.insert(c.end(), __f, __l);
 803   std::make_heap(c.begin(), c.end(), comp);
 804 }
 805
 806 #endif // _LIBCPP_CXX03_LANG
 807
 808 template <class _Tp, class _Container, class _Compare>
 809 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 810 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a) : c(__a) {}
 811
 812 template <class _Tp, class _Container, class _Compare>
 813 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 814 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, const _Alloc& __a)
 815     : c(__a), comp(__comp) {}
 816
 817 template <class _Tp, class _Container, class _Compare>
 818 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 819 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 820     const value_compare& __comp, const container_type& __c, const _Alloc& __a)
 821     : c(__c, __a), comp(__comp) {
 822   std::make_heap(c.begin(), c.end(), comp);
 823 }
 824
 825 template <class _Tp, class _Container, class _Compare>
 826 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 827 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, const _Alloc& __a)
 828     : c(__q.c, __a), comp(__q.comp) {}
 829
 830 #ifndef _LIBCPP_CXX03_LANG
 831
 832 template <class _Tp, class _Container, class _Compare>
 833 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 834 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 835     const value_compare& __comp, container_type&& __c, const _Alloc& __a)
 836     : c(std::move(__c), __a), comp(__comp) {
 837   std::make_heap(c.begin(), c.end(), comp);
 838 }
 839
 840 template <class _Tp, class _Container, class _Compare>
 841 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 842 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, const _Alloc& __a)
 843     : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {}
 844
 845 #endif // _LIBCPP_CXX03_LANG
 846
 847 template <class _Tp, class _Container, class _Compare>
 848 template <
 849     class _InputIter,
 850     class _Alloc,
 851     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 852 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a)
 853     : c(__f, __l, __a), comp() {
 854   std::make_heap(c.begin(), c.end(), comp);
 855 }
 856
 857 template <class _Tp, class _Container, class _Compare>
 858 template <
 859     class _InputIter,
 860     class _Alloc,
 861     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 862 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 863     _InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a)
 864     : c(__f, __l, __a), comp(__comp) {
 865   std::make_heap(c.begin(), c.end(), comp);
 866 }
 867
 868 template <class _Tp, class _Container, class _Compare>
 869 template <
 870     class _InputIter,
 871     class _Alloc,
 872     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 873 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 874     _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a)
 875     : c(__c, __a), comp(__comp) {
 876   c.insert(c.end(), __f, __l);
 877   std::make_heap(c.begin(), c.end(), comp);
 878 }
 879
 880 #ifndef _LIBCPP_CXX03_LANG
 881 template <class _Tp, class _Container, class _Compare>
 882 template <
 883     class _InputIter,
 884     class _Alloc,
 885     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 886 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 887     _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a)
 888     : c(std::move(__c), __a), comp(__comp) {
 889   c.insert(c.end(), __f, __l);
 890   std::make_heap(c.begin(), c.end(), comp);
 891 }
 892 #endif // _LIBCPP_CXX03_LANG
 893
 894 template <class _Tp, class _Container, class _Compare>
 895 inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) {
 896   c.push_back(__v);
 897   std::push_heap(c.begin(), c.end(), comp);
 898 }
 899
 900 #ifndef _LIBCPP_CXX03_LANG
 901
 902 template <class _Tp, class _Container, class _Compare>
 903 inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) {
 904   c.push_back(std::move(__v));
 905   std::push_heap(c.begin(), c.end(), comp);
 906 }
 907
 908 template <class _Tp, class _Container, class _Compare>
 909 template <class... _Args>
 910 inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) {
 911   c.emplace_back(std::forward<_Args>(__args)...);
 912   std::push_heap(c.begin(), c.end(), comp);
 913 }
 914
 915 #endif // _LIBCPP_CXX03_LANG
 916
 917 template <class _Tp, class _Container, class _Compare>
 918 inline void priority_queue<_Tp, _Container, _Compare>::pop() {
 919   std::pop_heap(c.begin(), c.end(), comp);
 920   c.pop_back();
 921 }
 922
 923 template <class _Tp, class _Container, class _Compare>
 924 inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
 925     _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>) {
 926   using std::swap;
 927   swap(c, __q.c);
 928   swap(comp, __q.comp);
 929 }
 930
 931 template <class _Tp,
 932           class _Container,
 933           class _Compare,
 934           __enable_if_t<__is_swappable_v<_Container> && __is_swappable_v<_Compare>, int> = 0>
 935 inline _LIBCPP_HIDE_FROM_ABI void
 936 swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y)
 937     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
 938   __x.swap(__y);
 939 }
 940
 941 template <class _Tp, class _Container, class _Compare, class _Alloc>
 942 struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
 943     : public uses_allocator<_Container, _Alloc> {};
 944
 945 _LIBCPP_END_NAMESPACE_STD
 946
 947 _LIBCPP_POP_MACROS
 948
 949 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 950 #  include <concepts>
 951 #  include <cstdlib>
 952 #  include <functional>
 953 #  include <type_traits>
 954 #endif
 955
 956 #endif // _LIBCPP_QUEUE