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