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