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