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 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
 258 #  include <__cxx03/queue>
 259 #else
 260 #  include <__algorithm/make_heap.h>
 261 #  include <__algorithm/pop_heap.h>
 262 #  include <__algorithm/push_heap.h>
 263 #  include <__algorithm/ranges_copy.h>
 264 #  include <__config>
 265 #  include <__functional/operations.h>
 266 #  include <__fwd/deque.h>
 267 #  include <__fwd/queue.h>
 268 #  include <__iterator/back_insert_iterator.h>
 269 #  include <__iterator/iterator_traits.h>
 270 #  include <__memory/uses_allocator.h>
 271 #  include <__ranges/access.h>
 272 #  include <__ranges/concepts.h>
 273 #  include <__ranges/container_compatible_range.h>
 274 #  include <__ranges/from_range.h>
 275 #  include <__utility/forward.h>
 276 #  include <deque>
 277 #  include <vector>
 278 #  include <version>
 279
 280 // standard-mandated includes
 281
 282 // [queue.syn]
 283 #  include <compare>
 284 #  include <initializer_list>
 285
 286 #  if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 287 #    pragma GCC system_header
 288 #  endif
 289
 290 _LIBCPP_PUSH_MACROS
 291 #  include <__undef_macros>
 292
 293 _LIBCPP_BEGIN_NAMESPACE_STD
 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>
 299 _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
 300
 301 template <class _Tp, class _Container /*= deque<_Tp>*/>
 302 class _LIBCPP_TEMPLATE_VIS queue {
 303 public:
 304   typedef _Container container_type;
 305   typedef typename container_type::value_type value_type;
 306   typedef typename container_type::reference reference;
 307   typedef typename container_type::const_reference const_reference;
 308   typedef typename container_type::size_type size_type;
 309   static_assert(is_same<_Tp, value_type>::value, "");
 310
 311 protected:
 312   container_type c;
 313
 314 public:
 315   _LIBCPP_HIDE_FROM_ABI queue() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {}
 316
 317   _LIBCPP_HIDE_FROM_ABI queue(const queue& __q) : c(__q.c) {}
 318
 319 #  if _LIBCPP_STD_VER >= 23
 320   template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
 321   _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
 322
 323   template <_ContainerCompatibleRange<_Tp> _Range>
 324   _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}
 325
 326   template <class _InputIterator,
 327             class _Alloc,
 328             __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
 329             __enable_if_t<uses_allocator<container_type, _Alloc>::value, int>        = 0>
 330   _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc)
 331       : c(__first, __second, __alloc) {}
 332
 333   template <_ContainerCompatibleRange<_Tp> _Range,
 334             class _Alloc,
 335             __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 336   _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range, const _Alloc& __alloc)
 337       : c(from_range, std::forward<_Range>(__range), __alloc) {}
 338
 339 #  endif
 340
 341   _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) {
 342     c = __q.c;
 343     return *this;
 344   }
 345
 346 #  ifndef _LIBCPP_CXX03_LANG
 347   _LIBCPP_HIDE_FROM_ABI queue(queue&& __q) noexcept(is_nothrow_move_constructible<container_type>::value)
 348       : c(std::move(__q.c)) {}
 349
 350   _LIBCPP_HIDE_FROM_ABI queue& operator=(queue&& __q) noexcept(is_nothrow_move_assignable<container_type>::value) {
 351     c = std::move(__q.c);
 352     return *this;
 353   }
 354 #  endif // _LIBCPP_CXX03_LANG
 355
 356   _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {}
 357 #  ifndef _LIBCPP_CXX03_LANG
 358   _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {}
 359 #  endif // _LIBCPP_CXX03_LANG
 360
 361   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 362   _LIBCPP_HIDE_FROM_ABI explicit queue(const _Alloc& __a) : 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 queue& __q, const _Alloc& __a) : c(__q.c, __a) {}
 366
 367   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 368   _LIBCPP_HIDE_FROM_ABI queue(const container_type& __c, const _Alloc& __a) : c(__c, __a) {}
 369
 370 #  ifndef _LIBCPP_CXX03_LANG
 371   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 372   _LIBCPP_HIDE_FROM_ABI queue(container_type&& __c, const _Alloc& __a) : c(std::move(__c), __a) {}
 373
 374   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 375   _LIBCPP_HIDE_FROM_ABI queue(queue&& __q, const _Alloc& __a) : c(std::move(__q.c), __a) {}
 376 #  endif // _LIBCPP_CXX03_LANG
 377
 378   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
 379   _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
 380
 381   _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); }
 382   _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); }
 383   _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); }
 384   _LIBCPP_HIDE_FROM_ABI const_reference back() const { return c.back(); }
 385
 386   _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); }
 387 #  ifndef _LIBCPP_CXX03_LANG
 388   _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); }
 389
 390 #    if _LIBCPP_STD_VER >= 23
 391   template <_ContainerCompatibleRange<_Tp> _Range>
 392   _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
 393     if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
 394       c.append_range(std::forward<_Range>(__range));
 395     } else {
 396       ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
 397     }
 398   }
 399 #    endif
 400
 401   template <class... _Args>
 402   _LIBCPP_HIDE_FROM_ABI
 403 #    if _LIBCPP_STD_VER >= 17
 404   decltype(auto)
 405   emplace(_Args&&... __args) {
 406     return c.emplace_back(std::forward<_Args>(__args)...);
 407   }
 408 #    else
 409   void
 410   emplace(_Args&&... __args) {
 411     c.emplace_back(std::forward<_Args>(__args)...);
 412   }
 413 #    endif
 414 #  endif // _LIBCPP_CXX03_LANG
 415   _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_front(); }
 416
 417   _LIBCPP_HIDE_FROM_ABI void swap(queue& __q) _NOEXCEPT_(__is_nothrow_swappable_v<container_type>) {
 418     using std::swap;
 419     swap(c, __q.c);
 420   }
 421
 422   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
 423
 424   template <class _T1, class _OtherContainer>
 425   friend _LIBCPP_HIDE_FROM_ABI bool
 426   operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
 427
 428   template <class _T1, class _OtherContainer>
 429   friend _LIBCPP_HIDE_FROM_ABI bool
 430   operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
 431 };
 432
 433 #  if _LIBCPP_STD_VER >= 17
 434 template <class _Container, class = enable_if_t<!__is_allocator<_Container>::value> >
 435 queue(_Container) -> queue<typename _Container::value_type, _Container>;
 436
 437 template <class _Container,
 438           class _Alloc,
 439           class = enable_if_t<!__is_allocator<_Container>::value>,
 440           class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
 441 queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>;
 442 #  endif
 443
 444 #  if _LIBCPP_STD_VER >= 23
 445 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
 446 queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>;
 447
 448 template <ranges::input_range _Range>
 449 queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>;
 450
 451 template <class _InputIterator,
 452           class _Alloc,
 453           __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
 454           __enable_if_t<__is_allocator<_Alloc>::value, int>                        = 0>
 455 queue(_InputIterator,
 456       _InputIterator,
 457       _Alloc) -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
 458
 459 template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
 460 queue(from_range_t,
 461       _Range&&,
 462       _Alloc) -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;
 463 #  endif
 464
 465 template <class _Tp, class _Container>
 466 inline _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 467   return __x.c == __y.c;
 468 }
 469
 470 template <class _Tp, class _Container>
 471 inline _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 472   return __x.c < __y.c;
 473 }
 474
 475 template <class _Tp, class _Container>
 476 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 477   return !(__x == __y);
 478 }
 479
 480 template <class _Tp, class _Container>
 481 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 482   return __y < __x;
 483 }
 484
 485 template <class _Tp, class _Container>
 486 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 487   return !(__x < __y);
 488 }
 489
 490 template <class _Tp, class _Container>
 491 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 492   return !(__y < __x);
 493 }
 494
 495 #  if _LIBCPP_STD_VER >= 20
 496
 497 template <class _Tp, three_way_comparable _Container>
 498 _LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>
 499 operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
 500   // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors
 501   return __x.__get_container() <=> __y.__get_container();
 502 }
 503
 504 #  endif
 505
 506 template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0>
 507 inline _LIBCPP_HIDE_FROM_ABI void swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
 508     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
 509   __x.swap(__y);
 510 }
 511
 512 template <class _Tp, class _Container, class _Alloc>
 513 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> {
 514 };
 515
 516 template <class _Tp, class _Container, class _Compare>
 517 class _LIBCPP_TEMPLATE_VIS priority_queue {
 518 public:
 519   typedef _Container container_type;
 520   typedef _Compare value_compare;
 521   typedef typename container_type::value_type value_type;
 522   typedef typename container_type::reference reference;
 523   typedef typename container_type::const_reference const_reference;
 524   typedef typename container_type::size_type size_type;
 525   static_assert(is_same<_Tp, value_type>::value, "");
 526
 527 protected:
 528   container_type c;
 529   value_compare comp;
 530
 531 public:
 532   _LIBCPP_HIDE_FROM_ABI priority_queue() _NOEXCEPT_(
 533       is_nothrow_default_constructible<container_type>::value&& is_nothrow_default_constructible<value_compare>::value)
 534       : c(), comp() {}
 535
 536   _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
 537
 538   _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(const priority_queue& __q) {
 539     c    = __q.c;
 540     comp = __q.comp;
 541     return *this;
 542   }
 543
 544 #  ifndef _LIBCPP_CXX03_LANG
 545   _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q) noexcept(
 546       is_nothrow_move_constructible<container_type>::value && is_nothrow_move_constructible<value_compare>::value)
 547       : c(std::move(__q.c)), comp(std::move(__q.comp)) {}
 548
 549   _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(priority_queue&& __q) noexcept(
 550       is_nothrow_move_assignable<container_type>::value && is_nothrow_move_assignable<value_compare>::value) {
 551     c    = std::move(__q.c);
 552     comp = std::move(__q.comp);
 553     return *this;
 554   }
 555 #  endif // _LIBCPP_CXX03_LANG
 556
 557   _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const value_compare& __comp) : c(), comp(__comp) {}
 558   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c);
 559 #  ifndef _LIBCPP_CXX03_LANG
 560   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c);
 561 #  endif
 562   template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
 563   _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare());
 564
 565   template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
 566   _LIBCPP_HIDE_FROM_ABI
 567   priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c);
 568
 569 #  ifndef _LIBCPP_CXX03_LANG
 570   template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
 571   _LIBCPP_HIDE_FROM_ABI
 572   priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c);
 573 #  endif // _LIBCPP_CXX03_LANG
 574
 575 #  if _LIBCPP_STD_VER >= 23
 576   template <_ContainerCompatibleRange<_Tp> _Range>
 577   _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare())
 578       : c(from_range, std::forward<_Range>(__range)), comp(__comp) {
 579     std::make_heap(c.begin(), c.end(), comp);
 580   }
 581 #  endif
 582
 583   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 584   _LIBCPP_HIDE_FROM_ABI explicit priority_queue(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 _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 value_compare& __comp, const container_type& __c, const _Alloc& __a);
 591
 592   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 593   _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q, const _Alloc& __a);
 594
 595 #  ifndef _LIBCPP_CXX03_LANG
 596   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 597   _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c, const _Alloc& __a);
 598
 599   template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
 600   _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q, const _Alloc& __a);
 601 #  endif // _LIBCPP_CXX03_LANG
 602
 603   template <
 604       class _InputIter,
 605       class _Alloc,
 606       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 607                     int> = 0>
 608   _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a);
 609
 610   template <
 611       class _InputIter,
 612       class _Alloc,
 613       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 614                     int> = 0>
 615   _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a);
 616
 617   template <
 618       class _InputIter,
 619       class _Alloc,
 620       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 621                     int> = 0>
 622   _LIBCPP_HIDE_FROM_ABI priority_queue(
 623       _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a);
 624
 625 #  ifndef _LIBCPP_CXX03_LANG
 626   template <
 627       class _InputIter,
 628       class _Alloc,
 629       __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
 630                     int> = 0>
 631   _LIBCPP_HIDE_FROM_ABI
 632   priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a);
 633 #  endif // _LIBCPP_CXX03_LANG
 634
 635 #  if _LIBCPP_STD_VER >= 23
 636
 637   template <_ContainerCompatibleRange<_Tp> _Range,
 638             class _Alloc,
 639             class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
 640   _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a)
 641       : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) {
 642     std::make_heap(c.begin(), c.end(), comp);
 643   }
 644
 645   template <_ContainerCompatibleRange<_Tp> _Range,
 646             class _Alloc,
 647             class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
 648   _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a)
 649       : c(from_range, std::forward<_Range>(__range), __a), comp() {
 650     std::make_heap(c.begin(), c.end(), comp);
 651   }
 652
 653 #  endif
 654
 655   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
 656   _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
 657   _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.front(); }
 658
 659   _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v);
 660 #  ifndef _LIBCPP_CXX03_LANG
 661   _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v);
 662
 663 #    if _LIBCPP_STD_VER >= 23
 664   template <_ContainerCompatibleRange<_Tp> _Range>
 665   _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
 666     if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
 667       c.append_range(std::forward<_Range>(__range));
 668     } else {
 669       ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
 670     }
 671
 672     std::make_heap(c.begin(), c.end(), comp);
 673   }
 674 #    endif
 675
 676   template <class... _Args>
 677   _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args);
 678 #  endif // _LIBCPP_CXX03_LANG
 679   _LIBCPP_HIDE_FROM_ABI void pop();
 680
 681   _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q)
 682       _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>);
 683
 684   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
 685 };
 686
 687 #  if _LIBCPP_STD_VER >= 17
 688 template <class _Compare,
 689           class _Container,
 690           class = enable_if_t<!__is_allocator<_Compare>::value>,
 691           class = enable_if_t<!__is_allocator<_Container>::value> >
 692 priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 693
 694 template <class _InputIterator,
 695           class _Compare   = less<__iter_value_type<_InputIterator>>,
 696           class _Container = vector<__iter_value_type<_InputIterator>>,
 697           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 698           class            = enable_if_t<!__is_allocator<_Compare>::value>,
 699           class            = enable_if_t<!__is_allocator<_Container>::value> >
 700 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
 701     -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
 702
 703 template <class _Compare,
 704           class _Container,
 705           class _Alloc,
 706           class = enable_if_t<!__is_allocator<_Compare>::value>,
 707           class = enable_if_t<!__is_allocator<_Container>::value>,
 708           class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
 709 priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 710
 711 template <class _InputIterator,
 712           class _Allocator,
 713           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 714           class = enable_if_t<__is_allocator<_Allocator>::value> >
 715 priority_queue(_InputIterator, _InputIterator, _Allocator)
 716     -> priority_queue<__iter_value_type<_InputIterator>,
 717                       vector<__iter_value_type<_InputIterator>, _Allocator>,
 718                       less<__iter_value_type<_InputIterator>>>;
 719
 720 template <class _InputIterator,
 721           class _Compare,
 722           class _Allocator,
 723           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 724           class = enable_if_t<!__is_allocator<_Compare>::value>,
 725           class = enable_if_t<__is_allocator<_Allocator>::value> >
 726 priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
 727     -> priority_queue<__iter_value_type<_InputIterator>,
 728                       vector<__iter_value_type<_InputIterator>, _Allocator>,
 729                       _Compare>;
 730
 731 template <class _InputIterator,
 732           class _Compare,
 733           class _Container,
 734           class _Alloc,
 735           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 736           class = enable_if_t<!__is_allocator<_Compare>::value>,
 737           class = enable_if_t<!__is_allocator<_Container>::value>,
 738           class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
 739 priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
 740     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 741 #  endif
 742
 743 #  if _LIBCPP_STD_VER >= 23
 744
 745 template <ranges::input_range _Range,
 746           class _Compare = less<ranges::range_value_t<_Range>>,
 747           class          = enable_if_t<!__is_allocator<_Compare>::value>>
 748 priority_queue(from_range_t, _Range&&, _Compare = _Compare())
 749     -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>;
 750
 751 template <ranges::input_range _Range,
 752           class _Compare,
 753           class _Alloc,
 754           class = enable_if_t<!__is_allocator<_Compare>::value>,
 755           class = enable_if_t<__is_allocator<_Alloc>::value>>
 756 priority_queue(from_range_t, _Range&&, _Compare, _Alloc)
 757     -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>;
 758
 759 template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator<_Alloc>::value>>
 760 priority_queue(from_range_t, _Range&&, _Alloc)
 761     -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>;
 762
 763 #  endif
 764
 765 template <class _Tp, class _Container, class _Compare>
 766 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, const container_type& __c)
 767     : c(__c), comp(__comp) {
 768   std::make_heap(c.begin(), c.end(), comp);
 769 }
 770
 771 #  ifndef _LIBCPP_CXX03_LANG
 772
 773 template <class _Tp, class _Container, class _Compare>
 774 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, container_type&& __c)
 775     : c(std::move(__c)), comp(__comp) {
 776   std::make_heap(c.begin(), c.end(), comp);
 777 }
 778
 779 #  endif // _LIBCPP_CXX03_LANG
 780
 781 template <class _Tp, class _Container, class _Compare>
 782 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
 783 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 784     _InputIter __f, _InputIter __l, const value_compare& __comp)
 785     : c(__f, __l), comp(__comp) {
 786   std::make_heap(c.begin(), c.end(), comp);
 787 }
 788
 789 template <class _Tp, class _Container, class _Compare>
 790 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
 791 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 792     _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c)
 793     : c(__c), comp(__comp) {
 794   c.insert(c.end(), __f, __l);
 795   std::make_heap(c.begin(), c.end(), comp);
 796 }
 797
 798 #  ifndef _LIBCPP_CXX03_LANG
 799
 800 template <class _Tp, class _Container, class _Compare>
 801 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
 802 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 803     _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c)
 804     : c(std::move(__c)), comp(__comp) {
 805   c.insert(c.end(), __f, __l);
 806   std::make_heap(c.begin(), c.end(), comp);
 807 }
 808
 809 #  endif // _LIBCPP_CXX03_LANG
 810
 811 template <class _Tp, class _Container, class _Compare>
 812 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 813 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a) : c(__a) {}
 814
 815 template <class _Tp, class _Container, class _Compare>
 816 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 817 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, const _Alloc& __a)
 818     : c(__a), comp(__comp) {}
 819
 820 template <class _Tp, class _Container, class _Compare>
 821 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 822 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 823     const value_compare& __comp, const container_type& __c, const _Alloc& __a)
 824     : c(__c, __a), comp(__comp) {
 825   std::make_heap(c.begin(), c.end(), comp);
 826 }
 827
 828 template <class _Tp, class _Container, class _Compare>
 829 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 830 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, const _Alloc& __a)
 831     : c(__q.c, __a), comp(__q.comp) {}
 832
 833 #  ifndef _LIBCPP_CXX03_LANG
 834
 835 template <class _Tp, class _Container, class _Compare>
 836 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 837 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 838     const value_compare& __comp, container_type&& __c, const _Alloc& __a)
 839     : c(std::move(__c), __a), comp(__comp) {
 840   std::make_heap(c.begin(), c.end(), comp);
 841 }
 842
 843 template <class _Tp, class _Container, class _Compare>
 844 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
 845 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, const _Alloc& __a)
 846     : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {}
 847
 848 #  endif // _LIBCPP_CXX03_LANG
 849
 850 template <class _Tp, class _Container, class _Compare>
 851 template <
 852     class _InputIter,
 853     class _Alloc,
 854     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 855 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a)
 856     : c(__f, __l, __a), comp() {
 857   std::make_heap(c.begin(), c.end(), comp);
 858 }
 859
 860 template <class _Tp, class _Container, class _Compare>
 861 template <
 862     class _InputIter,
 863     class _Alloc,
 864     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 865 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 866     _InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a)
 867     : c(__f, __l, __a), comp(__comp) {
 868   std::make_heap(c.begin(), c.end(), comp);
 869 }
 870
 871 template <class _Tp, class _Container, class _Compare>
 872 template <
 873     class _InputIter,
 874     class _Alloc,
 875     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 876 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 877     _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a)
 878     : c(__c, __a), comp(__comp) {
 879   c.insert(c.end(), __f, __l);
 880   std::make_heap(c.begin(), c.end(), comp);
 881 }
 882
 883 #  ifndef _LIBCPP_CXX03_LANG
 884 template <class _Tp, class _Container, class _Compare>
 885 template <
 886     class _InputIter,
 887     class _Alloc,
 888     __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
 889 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
 890     _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a)
 891     : c(std::move(__c), __a), comp(__comp) {
 892   c.insert(c.end(), __f, __l);
 893   std::make_heap(c.begin(), c.end(), comp);
 894 }
 895 #  endif // _LIBCPP_CXX03_LANG
 896
 897 template <class _Tp, class _Container, class _Compare>
 898 inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) {
 899   c.push_back(__v);
 900   std::push_heap(c.begin(), c.end(), comp);
 901 }
 902
 903 #  ifndef _LIBCPP_CXX03_LANG
 904
 905 template <class _Tp, class _Container, class _Compare>
 906 inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) {
 907   c.push_back(std::move(__v));
 908   std::push_heap(c.begin(), c.end(), comp);
 909 }
 910
 911 template <class _Tp, class _Container, class _Compare>
 912 template <class... _Args>
 913 inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) {
 914   c.emplace_back(std::forward<_Args>(__args)...);
 915   std::push_heap(c.begin(), c.end(), comp);
 916 }
 917
 918 #  endif // _LIBCPP_CXX03_LANG
 919
 920 template <class _Tp, class _Container, class _Compare>
 921 inline void priority_queue<_Tp, _Container, _Compare>::pop() {
 922   std::pop_heap(c.begin(), c.end(), comp);
 923   c.pop_back();
 924 }
 925
 926 template <class _Tp, class _Container, class _Compare>
 927 inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
 928     _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>) {
 929   using std::swap;
 930   swap(c, __q.c);
 931   swap(comp, __q.comp);
 932 }
 933
 934 template <class _Tp,
 935           class _Container,
 936           class _Compare,
 937           __enable_if_t<__is_swappable_v<_Container> && __is_swappable_v<_Compare>, int> = 0>
 938 inline _LIBCPP_HIDE_FROM_ABI void
 939 swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y)
 940     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
 941   __x.swap(__y);
 942 }
 943
 944 template <class _Tp, class _Container, class _Compare, class _Alloc>
 945 struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
 946     : public uses_allocator<_Container, _Alloc> {};
 947
 948 _LIBCPP_END_NAMESPACE_STD
 949
 950 _LIBCPP_POP_MACROS
 951
 952 #  if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 953 #    include <concepts>
 954 #    include <cstdlib>
 955 #    include <functional>
 956 #    include <type_traits>
 957 #  endif
 958 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
 959
 960 #endif // _LIBCPP_QUEUE