xref: /freebsd/contrib/llvm-project/libcxx/include/queue (revision 5ca8e32633c4ffbbcd6762e5888b6a4ba0708c6c) 
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_BEGIN_NAMESPACE_STD
287
288template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue;
289
290template <class _Tp, class _Container>
291_LIBCPP_INLINE_VISIBILITY
292bool
293operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
294
295template <class _Tp, class _Container>
296_LIBCPP_INLINE_VISIBILITY
297bool
298operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
299
300template <class _Tp, class _Container /*= deque<_Tp>*/>
301class _LIBCPP_TEMPLATE_VIS queue
302{
303public:
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
311protected:
312    container_type c;
313
314public:
315    _LIBCPP_INLINE_VISIBILITY
316    queue()
317        _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
318        : c() {}
319
320    _LIBCPP_INLINE_VISIBILITY
321    queue(const queue& __q) : c(__q.c) {}
322
323#if _LIBCPP_STD_VER >= 23
324    template <class _InputIterator,
325              class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>>
326    _LIBCPP_HIDE_FROM_ABI
327    queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
328
329    template <_ContainerCompatibleRange<_Tp> _Range>
330    _LIBCPP_HIDE_FROM_ABI
331    queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}
332
333    template <class _InputIterator,
334              class _Alloc,
335              class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
336              class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>>
337    _LIBCPP_HIDE_FROM_ABI
338    queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc) : c(__first, __second, __alloc) {}
339
340    template <_ContainerCompatibleRange<_Tp> _Range,
341              class _Alloc,
342              class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>>
343    _LIBCPP_HIDE_FROM_ABI
344    queue(from_range_t, _Range&& __range, const _Alloc& __alloc)
345      : c(from_range, std::forward<_Range>(__range), __alloc) {}
346
347#endif
348
349    _LIBCPP_INLINE_VISIBILITY
350    queue& operator=(const queue& __q) {c = __q.c; return *this;}
351
352#ifndef _LIBCPP_CXX03_LANG
353    _LIBCPP_INLINE_VISIBILITY
354    queue(queue&& __q)
355        _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
356        : c(_VSTD::move(__q.c)) {}
357
358    _LIBCPP_INLINE_VISIBILITY
359    queue& operator=(queue&& __q)
360        _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
361        {c = _VSTD::move(__q.c); return *this;}
362#endif // _LIBCPP_CXX03_LANG
363
364    _LIBCPP_INLINE_VISIBILITY
365    explicit queue(const container_type& __c)  : c(__c) {}
366#ifndef _LIBCPP_CXX03_LANG
367    _LIBCPP_INLINE_VISIBILITY
368    explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
369#endif // _LIBCPP_CXX03_LANG
370    template <class _Alloc>
371        _LIBCPP_INLINE_VISIBILITY
372        explicit queue(const _Alloc& __a,
373                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
374            : c(__a) {}
375    template <class _Alloc>
376        _LIBCPP_INLINE_VISIBILITY
377        queue(const queue& __q, const _Alloc& __a,
378                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
379            : c(__q.c, __a) {}
380    template <class _Alloc>
381        _LIBCPP_INLINE_VISIBILITY
382        queue(const container_type& __c, const _Alloc& __a,
383                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
384            : c(__c, __a) {}
385#ifndef _LIBCPP_CXX03_LANG
386    template <class _Alloc>
387        _LIBCPP_INLINE_VISIBILITY
388        queue(container_type&& __c, const _Alloc& __a,
389                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
390            : c(_VSTD::move(__c), __a) {}
391    template <class _Alloc>
392        _LIBCPP_INLINE_VISIBILITY
393        queue(queue&& __q, const _Alloc& __a,
394                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
395            : c(_VSTD::move(__q.c), __a) {}
396
397#endif // _LIBCPP_CXX03_LANG
398
399    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
400    bool      empty() const {return c.empty();}
401    _LIBCPP_INLINE_VISIBILITY
402    size_type size() const  {return c.size();}
403
404    _LIBCPP_INLINE_VISIBILITY
405    reference       front()       {return c.front();}
406    _LIBCPP_INLINE_VISIBILITY
407    const_reference front() const {return c.front();}
408    _LIBCPP_INLINE_VISIBILITY
409    reference       back()        {return c.back();}
410    _LIBCPP_INLINE_VISIBILITY
411    const_reference back() const  {return c.back();}
412
413    _LIBCPP_INLINE_VISIBILITY
414    void push(const value_type& __v) {c.push_back(__v);}
415#ifndef _LIBCPP_CXX03_LANG
416    _LIBCPP_INLINE_VISIBILITY
417    void push(value_type&& __v)      {c.push_back(_VSTD::move(__v));}
418
419#if _LIBCPP_STD_VER >= 23
420    template <_ContainerCompatibleRange<_Tp> _Range>
421    _LIBCPP_HIDE_FROM_ABI
422    void push_range(_Range&& __range) {
423      if constexpr (requires (container_type& __c) {
424        __c.append_range(std::forward<_Range>(__range));
425      }) {
426        c.append_range(std::forward<_Range>(__range));
427      } else {
428        ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
429      }
430    }
431#endif
432
433    template <class... _Args>
434        _LIBCPP_INLINE_VISIBILITY
435#if _LIBCPP_STD_VER >= 17
436        decltype(auto) emplace(_Args&&... __args)
437            { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
438#else
439        void     emplace(_Args&&... __args)
440            {        c.emplace_back(_VSTD::forward<_Args>(__args)...);}
441#endif
442#endif // _LIBCPP_CXX03_LANG
443    _LIBCPP_INLINE_VISIBILITY
444    void pop() {c.pop_front();}
445
446    _LIBCPP_INLINE_VISIBILITY
447    void swap(queue& __q)
448        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
449    {
450        using _VSTD::swap;
451        swap(c, __q.c);
452    }
453
454    _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
455
456    template <class _T1, class _OtherContainer>
457    friend
458    _LIBCPP_INLINE_VISIBILITY
459    bool
460    operator==(const queue<_T1, _OtherContainer>& __x,const queue<_T1, _OtherContainer>& __y);
461
462    template <class _T1, class _OtherContainer>
463    friend
464    _LIBCPP_INLINE_VISIBILITY
465    bool
466    operator< (const queue<_T1, _OtherContainer>& __x,const queue<_T1, _OtherContainer>& __y);
467};
468
469#if _LIBCPP_STD_VER >= 17
470template<class _Container,
471         class = enable_if_t<!__is_allocator<_Container>::value>
472>
473queue(_Container)
474    -> queue<typename _Container::value_type, _Container>;
475
476template<class _Container,
477         class _Alloc,
478         class = enable_if_t<!__is_allocator<_Container>::value>,
479         class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
480>
481queue(_Container, _Alloc)
482    -> queue<typename _Container::value_type, _Container>;
483#endif
484
485#if _LIBCPP_STD_VER >= 23
486template <class _InputIterator,
487          class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>>
488queue(_InputIterator, _InputIterator)
489    -> queue<__iter_value_type<_InputIterator>>;
490
491template <ranges::input_range _Range>
492queue(from_range_t, _Range&&)
493    -> queue<ranges::range_value_t<_Range>>;
494
495template <class _InputIterator,
496          class _Alloc,
497          class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
498          class = __enable_if_t<__is_allocator<_Alloc>::value>>
499queue(_InputIterator, _InputIterator, _Alloc)
500    -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
501
502template <ranges::input_range _Range,
503          class _Alloc,
504          class = __enable_if_t<__is_allocator<_Alloc>::value>>
505queue(from_range_t, _Range&&, _Alloc)
506    -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;
507#endif
508
509template <class _Tp, class _Container>
510inline _LIBCPP_INLINE_VISIBILITY
511bool
512operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
513{
514    return __x.c == __y.c;
515}
516
517template <class _Tp, class _Container>
518inline _LIBCPP_INLINE_VISIBILITY
519bool
520operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
521{
522    return __x.c < __y.c;
523}
524
525template <class _Tp, class _Container>
526inline _LIBCPP_INLINE_VISIBILITY
527bool
528operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
529{
530    return !(__x == __y);
531}
532
533template <class _Tp, class _Container>
534inline _LIBCPP_INLINE_VISIBILITY
535bool
536operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
537{
538    return __y < __x;
539}
540
541template <class _Tp, class _Container>
542inline _LIBCPP_INLINE_VISIBILITY
543bool
544operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
545{
546    return !(__x < __y);
547}
548
549template <class _Tp, class _Container>
550inline _LIBCPP_INLINE_VISIBILITY
551bool
552operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
553{
554    return !(__y < __x);
555}
556
557#if _LIBCPP_STD_VER >= 20
558
559template <class _Tp, three_way_comparable _Container>
560_LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>
561operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
562    // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors
563    return __x.__get_container() <=> __y.__get_container();
564}
565
566#endif
567
568template <class _Tp, class _Container>
569inline _LIBCPP_INLINE_VISIBILITY
570__enable_if_t<__is_swappable<_Container>::value, void>
571swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
572    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
573{
574    __x.swap(__y);
575}
576
577template <class _Tp, class _Container, class _Alloc>
578struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc>
579    : public uses_allocator<_Container, _Alloc>
580{
581};
582
583template <class _Tp, class _Container = vector<_Tp>,
584          class _Compare = less<typename _Container::value_type> >
585class _LIBCPP_TEMPLATE_VIS priority_queue
586{
587public:
588    typedef _Container                               container_type;
589    typedef _Compare                                 value_compare;
590    typedef typename container_type::value_type      value_type;
591    typedef typename container_type::reference       reference;
592    typedef typename container_type::const_reference const_reference;
593    typedef typename container_type::size_type       size_type;
594    static_assert((is_same<_Tp, value_type>::value), "" );
595
596protected:
597    container_type c;
598    value_compare comp;
599
600public:
601    _LIBCPP_INLINE_VISIBILITY
602    priority_queue()
603        _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
604                   is_nothrow_default_constructible<value_compare>::value)
605        : c(), comp() {}
606
607    _LIBCPP_INLINE_VISIBILITY
608    priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
609
610    _LIBCPP_INLINE_VISIBILITY
611    priority_queue& operator=(const priority_queue& __q)
612        {c = __q.c; comp = __q.comp; return *this;}
613
614#ifndef _LIBCPP_CXX03_LANG
615    _LIBCPP_INLINE_VISIBILITY
616    priority_queue(priority_queue&& __q)
617        _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
618                   is_nothrow_move_constructible<value_compare>::value)
619        : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
620
621    _LIBCPP_INLINE_VISIBILITY
622    priority_queue& operator=(priority_queue&& __q)
623        _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
624                   is_nothrow_move_assignable<value_compare>::value)
625        {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
626#endif // _LIBCPP_CXX03_LANG
627
628    _LIBCPP_INLINE_VISIBILITY
629    explicit priority_queue(const value_compare& __comp)
630        : c(), comp(__comp) {}
631    _LIBCPP_INLINE_VISIBILITY
632    priority_queue(const value_compare& __comp, const container_type& __c);
633#ifndef _LIBCPP_CXX03_LANG
634    _LIBCPP_INLINE_VISIBILITY
635    priority_queue(const value_compare& __comp, container_type&& __c);
636#endif
637    template <class _InputIter, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> >
638        _LIBCPP_INLINE_VISIBILITY
639        priority_queue(_InputIter __f, _InputIter __l,
640                       const value_compare& __comp = value_compare());
641    template <class _InputIter, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> >
642        _LIBCPP_INLINE_VISIBILITY
643        priority_queue(_InputIter __f, _InputIter __l,
644                       const value_compare& __comp, const container_type& __c);
645#ifndef _LIBCPP_CXX03_LANG
646    template <class _InputIter, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> >
647        _LIBCPP_INLINE_VISIBILITY
648        priority_queue(_InputIter __f, _InputIter __l,
649                       const value_compare& __comp, container_type&& __c);
650#endif // _LIBCPP_CXX03_LANG
651
652#if _LIBCPP_STD_VER >= 23
653    template <_ContainerCompatibleRange<_Tp> _Range>
654    _LIBCPP_HIDE_FROM_ABI
655    priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare())
656    : c(from_range, std::forward<_Range>(__range)),
657      comp(__comp) {
658      std::make_heap(c.begin(), c.end(), comp);
659    }
660#endif
661
662    template <class _Alloc>
663        _LIBCPP_INLINE_VISIBILITY
664        explicit priority_queue(const _Alloc& __a,
665                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
666    template <class _Alloc>
667        _LIBCPP_INLINE_VISIBILITY
668        priority_queue(const value_compare& __comp, const _Alloc& __a,
669                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
670    template <class _Alloc>
671        _LIBCPP_INLINE_VISIBILITY
672        priority_queue(const value_compare& __comp, const container_type& __c,
673                       const _Alloc& __a,
674                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
675    template <class _Alloc>
676        _LIBCPP_INLINE_VISIBILITY
677        priority_queue(const priority_queue& __q, const _Alloc& __a,
678                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
679#ifndef _LIBCPP_CXX03_LANG
680    template <class _Alloc>
681        _LIBCPP_INLINE_VISIBILITY
682        priority_queue(const value_compare& __comp, container_type&& __c,
683                       const _Alloc& __a,
684                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
685    template <class _Alloc>
686        _LIBCPP_INLINE_VISIBILITY
687        priority_queue(priority_queue&& __q, const _Alloc& __a,
688                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
689#endif // _LIBCPP_CXX03_LANG
690
691    template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> >
692        _LIBCPP_INLINE_VISIBILITY
693        priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a,
694                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
695
696    template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> >
697        _LIBCPP_INLINE_VISIBILITY
698        priority_queue(_InputIter __f, _InputIter __l,
699                       const value_compare& __comp, const _Alloc& __a,
700                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
701
702    template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> >
703        _LIBCPP_INLINE_VISIBILITY
704        priority_queue(_InputIter __f, _InputIter __l,
705                       const value_compare& __comp, const container_type& __c, const _Alloc& __a,
706                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
707
708#ifndef _LIBCPP_CXX03_LANG
709    template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> >
710        _LIBCPP_INLINE_VISIBILITY
711        priority_queue(_InputIter __f, _InputIter __l,
712                       const value_compare& __comp, container_type&& __c, const _Alloc& __a,
713                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
714#endif  // _LIBCPP_CXX03_LANG
715
716#if _LIBCPP_STD_VER >= 23
717
718    template <_ContainerCompatibleRange<_Tp> _Range,
719              class _Alloc,
720              class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
721    _LIBCPP_HIDE_FROM_ABI
722    priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a)
723    : c(from_range, std::forward<_Range>(__range), __a),
724      comp(__comp) {
725      std::make_heap(c.begin(), c.end(), comp);
726    }
727
728    template <_ContainerCompatibleRange<_Tp> _Range,
729              class _Alloc,
730              class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
731    _LIBCPP_HIDE_FROM_ABI
732    priority_queue(from_range_t, _Range&& __range, const _Alloc& __a)
733    : c(from_range, std::forward<_Range>(__range), __a),
734      comp() {
735      std::make_heap(c.begin(), c.end(), comp);
736    }
737
738#endif
739
740    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
741    bool            empty() const {return c.empty();}
742    _LIBCPP_INLINE_VISIBILITY
743    size_type       size() const  {return c.size();}
744    _LIBCPP_INLINE_VISIBILITY
745    const_reference top() const   {return c.front();}
746
747    _LIBCPP_INLINE_VISIBILITY
748    void push(const value_type& __v);
749#ifndef _LIBCPP_CXX03_LANG
750    _LIBCPP_INLINE_VISIBILITY
751    void push(value_type&& __v);
752
753#if _LIBCPP_STD_VER >= 23
754    template <_ContainerCompatibleRange<_Tp> _Range>
755    _LIBCPP_HIDE_FROM_ABI
756    void push_range(_Range&& __range) {
757      if constexpr (requires (container_type& __c) {
758        __c.append_range(std::forward<_Range>(__range));
759      }) {
760        c.append_range(std::forward<_Range>(__range));
761      } else {
762        ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
763      }
764
765      std::make_heap(c.begin(), c.end(), comp);
766    }
767#endif
768
769    template <class... _Args>
770    _LIBCPP_INLINE_VISIBILITY
771    void emplace(_Args&&... __args);
772#endif // _LIBCPP_CXX03_LANG
773    _LIBCPP_INLINE_VISIBILITY
774    void pop();
775
776    _LIBCPP_INLINE_VISIBILITY
777    void swap(priority_queue& __q)
778        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
779                   __is_nothrow_swappable<value_compare>::value);
780
781    _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
782};
783
784#if _LIBCPP_STD_VER >= 17
785template <class _Compare,
786          class _Container,
787          class = enable_if_t<!__is_allocator<_Compare>::value>,
788          class = enable_if_t<!__is_allocator<_Container>::value>
789>
790priority_queue(_Compare, _Container)
791    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
792
793template<class _InputIterator,
794         class _Compare = less<__iter_value_type<_InputIterator>>,
795         class _Container = vector<__iter_value_type<_InputIterator>>,
796         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
797         class = enable_if_t<!__is_allocator<_Compare>::value>,
798         class = enable_if_t<!__is_allocator<_Container>::value>
799>
800priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
801    -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
802
803template<class _Compare,
804         class _Container,
805         class _Alloc,
806         class = enable_if_t<!__is_allocator<_Compare>::value>,
807         class = enable_if_t<!__is_allocator<_Container>::value>,
808         class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
809>
810priority_queue(_Compare, _Container, _Alloc)
811    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
812
813template<class _InputIterator, class _Allocator,
814         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
815         class = enable_if_t<__is_allocator<_Allocator>::value>
816>
817priority_queue(_InputIterator, _InputIterator, _Allocator)
818    -> priority_queue<__iter_value_type<_InputIterator>,
819                      vector<__iter_value_type<_InputIterator>, _Allocator>,
820                      less<__iter_value_type<_InputIterator>>>;
821
822template<class _InputIterator, class _Compare, class _Allocator,
823         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
824         class = enable_if_t<!__is_allocator<_Compare>::value>,
825         class = enable_if_t<__is_allocator<_Allocator>::value>
826>
827priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
828    -> priority_queue<__iter_value_type<_InputIterator>,
829                      vector<__iter_value_type<_InputIterator>, _Allocator>, _Compare>;
830
831template<class _InputIterator, class _Compare, class _Container, class _Alloc,
832         class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
833         class = enable_if_t<!__is_allocator<_Compare>::value>,
834         class = enable_if_t<!__is_allocator<_Container>::value>,
835         class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
836>
837priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
838    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
839#endif
840
841#if _LIBCPP_STD_VER >= 23
842
843template <ranges::input_range _Range,
844          class _Compare = less<ranges::range_value_t<_Range>>,
845          class = enable_if_t<!__is_allocator<_Compare>::value>>
846priority_queue(from_range_t, _Range&&, _Compare = _Compare())
847    -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>;
848
849template <ranges::input_range _Range,
850          class _Compare,
851          class _Alloc,
852          class = enable_if_t<!__is_allocator<_Compare>::value>,
853          class = enable_if_t<__is_allocator<_Alloc>::value>>
854priority_queue(from_range_t, _Range&&, _Compare, _Alloc)
855    -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>,
856                        _Compare>;
857
858template <ranges::input_range _Range,
859          class _Alloc,
860          class = enable_if_t<__is_allocator<_Alloc>::value>>
861priority_queue(from_range_t, _Range&&, _Alloc)
862    -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>;
863
864#endif
865
866template <class _Tp, class _Container, class _Compare>
867inline
868priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
869                                                          const container_type& __c)
870    : c(__c),
871      comp(__comp)
872{
873    _VSTD::make_heap(c.begin(), c.end(), comp);
874}
875
876#ifndef _LIBCPP_CXX03_LANG
877
878template <class _Tp, class _Container, class _Compare>
879inline
880priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
881                                                          container_type&& __c)
882    : c(_VSTD::move(__c)),
883      comp(__comp)
884{
885    _VSTD::make_heap(c.begin(), c.end(), comp);
886}
887
888#endif // _LIBCPP_CXX03_LANG
889
890template <class _Tp, class _Container, class _Compare>
891template <class _InputIter, class>
892inline
893priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
894                                                          const value_compare& __comp)
895    : c(__f, __l),
896      comp(__comp)
897{
898    _VSTD::make_heap(c.begin(), c.end(), comp);
899}
900
901template <class _Tp, class _Container, class _Compare>
902template <class _InputIter, class>
903inline
904priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
905                                                          const value_compare& __comp,
906                                                          const container_type& __c)
907    : c(__c),
908      comp(__comp)
909{
910    c.insert(c.end(), __f, __l);
911    _VSTD::make_heap(c.begin(), c.end(), comp);
912}
913
914#ifndef _LIBCPP_CXX03_LANG
915
916template <class _Tp, class _Container, class _Compare>
917template <class _InputIter, class>
918inline
919priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
920                                                          const value_compare& __comp,
921                                                          container_type&& __c)
922    : c(_VSTD::move(__c)),
923      comp(__comp)
924{
925    c.insert(c.end(), __f, __l);
926    _VSTD::make_heap(c.begin(), c.end(), comp);
927}
928
929#endif // _LIBCPP_CXX03_LANG
930
931template <class _Tp, class _Container, class _Compare>
932template <class _Alloc>
933inline
934priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
935                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
936    : c(__a)
937{
938}
939
940template <class _Tp, class _Container, class _Compare>
941template <class _Alloc>
942inline
943priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
944                                                          const _Alloc& __a,
945                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
946    : c(__a),
947      comp(__comp)
948{
949}
950
951template <class _Tp, class _Container, class _Compare>
952template <class _Alloc>
953inline
954priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
955                                                          const container_type& __c,
956                                                          const _Alloc& __a,
957                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
958    : c(__c, __a),
959      comp(__comp)
960{
961    _VSTD::make_heap(c.begin(), c.end(), comp);
962}
963
964template <class _Tp, class _Container, class _Compare>
965template <class _Alloc>
966inline
967priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
968                                                          const _Alloc& __a,
969                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
970    : c(__q.c, __a),
971      comp(__q.comp)
972{
973}
974
975#ifndef _LIBCPP_CXX03_LANG
976
977template <class _Tp, class _Container, class _Compare>
978template <class _Alloc>
979inline
980priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
981                                                          container_type&& __c,
982                                                          const _Alloc& __a,
983                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
984    : c(_VSTD::move(__c), __a),
985      comp(__comp)
986{
987    _VSTD::make_heap(c.begin(), c.end(), comp);
988}
989
990template <class _Tp, class _Container, class _Compare>
991template <class _Alloc>
992inline
993priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
994                                                          const _Alloc& __a,
995                       __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
996    : c(_VSTD::move(__q.c), __a),
997      comp(_VSTD::move(__q.comp))
998{
999}
1000
1001#endif  // _LIBCPP_CXX03_LANG
1002
1003template <class _Tp, class _Container, class _Compare>
1004template <class _InputIter, class _Alloc, class>
1005inline
1006priority_queue<_Tp, _Container, _Compare>::priority_queue(
1007        _InputIter __f, _InputIter __l, const _Alloc& __a,
1008        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
1009    : c(__f, __l, __a),
1010      comp()
1011{
1012    _VSTD::make_heap(c.begin(), c.end(), comp);
1013}
1014
1015template <class _Tp, class _Container, class _Compare>
1016template <class _InputIter, class _Alloc, class>
1017inline
1018priority_queue<_Tp, _Container, _Compare>::priority_queue(
1019        _InputIter __f, _InputIter __l,
1020        const value_compare& __comp, const _Alloc& __a,
1021        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
1022    : c(__f, __l, __a),
1023      comp(__comp)
1024{
1025    _VSTD::make_heap(c.begin(), c.end(), comp);
1026}
1027
1028template <class _Tp, class _Container, class _Compare>
1029template <class _InputIter, class _Alloc, class>
1030inline
1031priority_queue<_Tp, _Container, _Compare>::priority_queue(
1032        _InputIter __f, _InputIter __l,
1033        const value_compare& __comp, const container_type& __c, const _Alloc& __a,
1034        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
1035    : c(__c, __a),
1036      comp(__comp)
1037{
1038    c.insert(c.end(), __f, __l);
1039    _VSTD::make_heap(c.begin(), c.end(), comp);
1040}
1041
1042#ifndef _LIBCPP_CXX03_LANG
1043template <class _Tp, class _Container, class _Compare>
1044template <class _InputIter, class _Alloc, class>
1045inline
1046priority_queue<_Tp, _Container, _Compare>::priority_queue(
1047        _InputIter __f, _InputIter __l, const value_compare& __comp,
1048        container_type&& __c, const _Alloc& __a,
1049        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
1050    : c(_VSTD::move(__c), __a),
1051      comp(__comp)
1052{
1053    c.insert(c.end(), __f, __l);
1054    _VSTD::make_heap(c.begin(), c.end(), comp);
1055}
1056#endif  // _LIBCPP_CXX03_LANG
1057
1058template <class _Tp, class _Container, class _Compare>
1059inline
1060void
1061priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
1062{
1063    c.push_back(__v);
1064    _VSTD::push_heap(c.begin(), c.end(), comp);
1065}
1066
1067#ifndef _LIBCPP_CXX03_LANG
1068
1069template <class _Tp, class _Container, class _Compare>
1070inline
1071void
1072priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
1073{
1074    c.push_back(_VSTD::move(__v));
1075    _VSTD::push_heap(c.begin(), c.end(), comp);
1076}
1077
1078template <class _Tp, class _Container, class _Compare>
1079template <class... _Args>
1080inline
1081void
1082priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
1083{
1084    c.emplace_back(_VSTD::forward<_Args>(__args)...);
1085    _VSTD::push_heap(c.begin(), c.end(), comp);
1086}
1087
1088#endif // _LIBCPP_CXX03_LANG
1089
1090template <class _Tp, class _Container, class _Compare>
1091inline
1092void
1093priority_queue<_Tp, _Container, _Compare>::pop()
1094{
1095    _VSTD::pop_heap(c.begin(), c.end(), comp);
1096    c.pop_back();
1097}
1098
1099template <class _Tp, class _Container, class _Compare>
1100inline
1101void
1102priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
1103        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
1104                   __is_nothrow_swappable<value_compare>::value)
1105{
1106    using _VSTD::swap;
1107    swap(c, __q.c);
1108    swap(comp, __q.comp);
1109}
1110
1111template <class _Tp, class _Container, class _Compare>
1112inline _LIBCPP_INLINE_VISIBILITY
1113__enable_if_t<
1114    __is_swappable<_Container>::value && __is_swappable<_Compare>::value,
1115    void
1116>
1117swap(priority_queue<_Tp, _Container, _Compare>& __x,
1118     priority_queue<_Tp, _Container, _Compare>& __y)
1119    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1120{
1121    __x.swap(__y);
1122}
1123
1124template <class _Tp, class _Container, class _Compare, class _Alloc>
1125struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
1126    : public uses_allocator<_Container, _Alloc>
1127{
1128};
1129
1130_LIBCPP_END_NAMESPACE_STD
1131
1132#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1133#  include <concepts>
1134#  include <cstdlib>
1135#  include <functional>
1136#  include <type_traits>
1137#endif
1138
1139#endif // _LIBCPP_QUEUE
1140