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