1// -*- C++ -*-
2//===--------------------------- queue ------------------------------------===//
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_type& c);
126    template <class InputIterator>
127        priority_queue(InputIterator first, InputIterator last,
128                       const Compare& comp, container_type&& 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_type& c,
135                       const Alloc& a);
136    template <class Alloc>
137        priority_queue(const Compare& comp, container_type&& c,
138                       const Alloc& a);
139    template <class Alloc>
140        priority_queue(const priority_queue& q, const Alloc& a);
141    template <class Alloc>
142        priority_queue(priority_queue&& q, const Alloc& a);
143
144    bool            empty() const;
145    size_type       size() const;
146    const_reference top() const;
147
148    void push(const value_type& v);
149    void push(value_type&& v);
150    template <class... Args> void emplace(Args&&... args);
151    void pop();
152
153    void swap(priority_queue& q)
154        noexcept(is_nothrow_swappable_v<Container> &&
155                 is_nothrow_swappable_v<Comp>)
156};
157
158template <class Compare, class Container>
159priority_queue(Compare, Container)
160    -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
161
162template<class InputIterator,
163         class Compare = less<typename iterator_traits<InputIterator>::value_type>,
164         class Container = vector<typename iterator_traits<InputIterator>::value_type>>
165priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
166    -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>; // C++17
167
168template<class Compare, class Container, class Allocator>
169priority_queue(Compare, Container, Allocator)
170    -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
171
172template <class T, class Container, class Compare>
173  void swap(priority_queue<T, Container, Compare>& x,
174            priority_queue<T, Container, Compare>& y)
175            noexcept(noexcept(x.swap(y)));
176
177}  // std
178
179*/
180
181#include <__config>
182#include <__memory/uses_allocator.h>
183#include <__utility/forward.h>
184#include <algorithm>
185#include <compare>
186#include <deque>
187#include <functional>
188#include <vector>
189
190#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
191#pragma GCC system_header
192#endif
193
194_LIBCPP_BEGIN_NAMESPACE_STD
195
196template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue;
197
198template <class _Tp, class _Container>
199_LIBCPP_INLINE_VISIBILITY
200bool
201operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
202
203template <class _Tp, class _Container>
204_LIBCPP_INLINE_VISIBILITY
205bool
206operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
207
208template <class _Tp, class _Container /*= deque<_Tp>*/>
209class _LIBCPP_TEMPLATE_VIS queue
210{
211public:
212    typedef _Container                               container_type;
213    typedef typename container_type::value_type      value_type;
214    typedef typename container_type::reference       reference;
215    typedef typename container_type::const_reference const_reference;
216    typedef typename container_type::size_type       size_type;
217    static_assert((is_same<_Tp, value_type>::value), "" );
218
219protected:
220    container_type c;
221
222public:
223    _LIBCPP_INLINE_VISIBILITY
224    queue()
225        _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
226        : c() {}
227
228    _LIBCPP_INLINE_VISIBILITY
229    queue(const queue& __q) : c(__q.c) {}
230
231    _LIBCPP_INLINE_VISIBILITY
232    queue& operator=(const queue& __q) {c = __q.c; return *this;}
233
234#ifndef _LIBCPP_CXX03_LANG
235    _LIBCPP_INLINE_VISIBILITY
236    queue(queue&& __q)
237        _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
238        : c(_VSTD::move(__q.c)) {}
239
240    _LIBCPP_INLINE_VISIBILITY
241    queue& operator=(queue&& __q)
242        _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
243        {c = _VSTD::move(__q.c); return *this;}
244#endif // _LIBCPP_CXX03_LANG
245
246    _LIBCPP_INLINE_VISIBILITY
247    explicit queue(const container_type& __c)  : c(__c) {}
248#ifndef _LIBCPP_CXX03_LANG
249    _LIBCPP_INLINE_VISIBILITY
250    explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
251#endif // _LIBCPP_CXX03_LANG
252    template <class _Alloc>
253        _LIBCPP_INLINE_VISIBILITY
254        explicit queue(const _Alloc& __a,
255                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0)
256            : c(__a) {}
257    template <class _Alloc>
258        _LIBCPP_INLINE_VISIBILITY
259        queue(const queue& __q, const _Alloc& __a,
260                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0)
261            : c(__q.c, __a) {}
262    template <class _Alloc>
263        _LIBCPP_INLINE_VISIBILITY
264        queue(const container_type& __c, const _Alloc& __a,
265                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0)
266            : c(__c, __a) {}
267#ifndef _LIBCPP_CXX03_LANG
268    template <class _Alloc>
269        _LIBCPP_INLINE_VISIBILITY
270        queue(container_type&& __c, const _Alloc& __a,
271                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0)
272            : c(_VSTD::move(__c), __a) {}
273    template <class _Alloc>
274        _LIBCPP_INLINE_VISIBILITY
275        queue(queue&& __q, const _Alloc& __a,
276                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0)
277            : c(_VSTD::move(__q.c), __a) {}
278
279#endif // _LIBCPP_CXX03_LANG
280
281    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
282    bool      empty() const {return c.empty();}
283    _LIBCPP_INLINE_VISIBILITY
284    size_type size() const  {return c.size();}
285
286    _LIBCPP_INLINE_VISIBILITY
287    reference       front()       {return c.front();}
288    _LIBCPP_INLINE_VISIBILITY
289    const_reference front() const {return c.front();}
290    _LIBCPP_INLINE_VISIBILITY
291    reference       back()        {return c.back();}
292    _LIBCPP_INLINE_VISIBILITY
293    const_reference back() const  {return c.back();}
294
295    _LIBCPP_INLINE_VISIBILITY
296    void push(const value_type& __v) {c.push_back(__v);}
297#ifndef _LIBCPP_CXX03_LANG
298    _LIBCPP_INLINE_VISIBILITY
299    void push(value_type&& __v)      {c.push_back(_VSTD::move(__v));}
300    template <class... _Args>
301        _LIBCPP_INLINE_VISIBILITY
302#if _LIBCPP_STD_VER > 14
303        decltype(auto) emplace(_Args&&... __args)
304            { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
305#else
306        void     emplace(_Args&&... __args)
307            {        c.emplace_back(_VSTD::forward<_Args>(__args)...);}
308#endif
309#endif // _LIBCPP_CXX03_LANG
310    _LIBCPP_INLINE_VISIBILITY
311    void pop() {c.pop_front();}
312
313    _LIBCPP_INLINE_VISIBILITY
314    void swap(queue& __q)
315        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
316    {
317        using _VSTD::swap;
318        swap(c, __q.c);
319    }
320
321    template <class _T1, class _C1>
322    friend
323    _LIBCPP_INLINE_VISIBILITY
324    bool
325    operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
326
327    template <class _T1, class _C1>
328    friend
329    _LIBCPP_INLINE_VISIBILITY
330    bool
331    operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
332};
333
334#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
335template<class _Container,
336         class = _EnableIf<!__is_allocator<_Container>::value>
337>
338queue(_Container)
339    -> queue<typename _Container::value_type, _Container>;
340
341template<class _Container,
342         class _Alloc,
343         class = _EnableIf<!__is_allocator<_Container>::value>,
344         class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
345>
346queue(_Container, _Alloc)
347    -> queue<typename _Container::value_type, _Container>;
348#endif
349
350template <class _Tp, class _Container>
351inline _LIBCPP_INLINE_VISIBILITY
352bool
353operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
354{
355    return __x.c == __y.c;
356}
357
358template <class _Tp, class _Container>
359inline _LIBCPP_INLINE_VISIBILITY
360bool
361operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
362{
363    return __x.c < __y.c;
364}
365
366template <class _Tp, class _Container>
367inline _LIBCPP_INLINE_VISIBILITY
368bool
369operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
370{
371    return !(__x == __y);
372}
373
374template <class _Tp, class _Container>
375inline _LIBCPP_INLINE_VISIBILITY
376bool
377operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
378{
379    return __y < __x;
380}
381
382template <class _Tp, class _Container>
383inline _LIBCPP_INLINE_VISIBILITY
384bool
385operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
386{
387    return !(__x < __y);
388}
389
390template <class _Tp, class _Container>
391inline _LIBCPP_INLINE_VISIBILITY
392bool
393operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
394{
395    return !(__y < __x);
396}
397
398template <class _Tp, class _Container>
399inline _LIBCPP_INLINE_VISIBILITY
400_EnableIf<__is_swappable<_Container>::value, void>
401swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
402    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
403{
404    __x.swap(__y);
405}
406
407template <class _Tp, class _Container, class _Alloc>
408struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc>
409    : public uses_allocator<_Container, _Alloc>
410{
411};
412
413template <class _Tp, class _Container = vector<_Tp>,
414          class _Compare = less<typename _Container::value_type> >
415class _LIBCPP_TEMPLATE_VIS priority_queue
416{
417public:
418    typedef _Container                               container_type;
419    typedef _Compare                                 value_compare;
420    typedef typename container_type::value_type      value_type;
421    typedef typename container_type::reference       reference;
422    typedef typename container_type::const_reference const_reference;
423    typedef typename container_type::size_type       size_type;
424    static_assert((is_same<_Tp, value_type>::value), "" );
425
426protected:
427    container_type c;
428    value_compare comp;
429
430public:
431    _LIBCPP_INLINE_VISIBILITY
432    priority_queue()
433        _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
434                   is_nothrow_default_constructible<value_compare>::value)
435        : c(), comp() {}
436
437    _LIBCPP_INLINE_VISIBILITY
438    priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
439
440    _LIBCPP_INLINE_VISIBILITY
441    priority_queue& operator=(const priority_queue& __q)
442        {c = __q.c; comp = __q.comp; return *this;}
443
444#ifndef _LIBCPP_CXX03_LANG
445    _LIBCPP_INLINE_VISIBILITY
446    priority_queue(priority_queue&& __q)
447        _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
448                   is_nothrow_move_constructible<value_compare>::value)
449        : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
450
451    _LIBCPP_INLINE_VISIBILITY
452    priority_queue& operator=(priority_queue&& __q)
453        _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
454                   is_nothrow_move_assignable<value_compare>::value)
455        {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
456#endif // _LIBCPP_CXX03_LANG
457
458    _LIBCPP_INLINE_VISIBILITY
459    explicit priority_queue(const value_compare& __comp)
460        : c(), comp(__comp) {}
461    _LIBCPP_INLINE_VISIBILITY
462    priority_queue(const value_compare& __comp, const container_type& __c);
463#ifndef _LIBCPP_CXX03_LANG
464    _LIBCPP_INLINE_VISIBILITY
465    priority_queue(const value_compare& __comp, container_type&& __c);
466#endif
467    template <class _InputIter>
468        _LIBCPP_INLINE_VISIBILITY
469        priority_queue(_InputIter __f, _InputIter __l,
470                       const value_compare& __comp = value_compare());
471    template <class _InputIter>
472        _LIBCPP_INLINE_VISIBILITY
473        priority_queue(_InputIter __f, _InputIter __l,
474                       const value_compare& __comp, const container_type& __c);
475#ifndef _LIBCPP_CXX03_LANG
476    template <class _InputIter>
477        _LIBCPP_INLINE_VISIBILITY
478        priority_queue(_InputIter __f, _InputIter __l,
479                       const value_compare& __comp, container_type&& __c);
480#endif // _LIBCPP_CXX03_LANG
481    template <class _Alloc>
482        _LIBCPP_INLINE_VISIBILITY
483        explicit priority_queue(const _Alloc& __a,
484                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
485    template <class _Alloc>
486        _LIBCPP_INLINE_VISIBILITY
487        priority_queue(const value_compare& __comp, const _Alloc& __a,
488                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
489    template <class _Alloc>
490        _LIBCPP_INLINE_VISIBILITY
491        priority_queue(const value_compare& __comp, const container_type& __c,
492                       const _Alloc& __a,
493                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
494    template <class _Alloc>
495        _LIBCPP_INLINE_VISIBILITY
496        priority_queue(const priority_queue& __q, const _Alloc& __a,
497                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
498#ifndef _LIBCPP_CXX03_LANG
499    template <class _Alloc>
500        _LIBCPP_INLINE_VISIBILITY
501        priority_queue(const value_compare& __comp, container_type&& __c,
502                       const _Alloc& __a,
503                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
504    template <class _Alloc>
505        _LIBCPP_INLINE_VISIBILITY
506        priority_queue(priority_queue&& __q, const _Alloc& __a,
507                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
508#endif // _LIBCPP_CXX03_LANG
509
510    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
511    bool            empty() const {return c.empty();}
512    _LIBCPP_INLINE_VISIBILITY
513    size_type       size() const  {return c.size();}
514    _LIBCPP_INLINE_VISIBILITY
515    const_reference top() const   {return c.front();}
516
517    _LIBCPP_INLINE_VISIBILITY
518    void push(const value_type& __v);
519#ifndef _LIBCPP_CXX03_LANG
520    _LIBCPP_INLINE_VISIBILITY
521    void push(value_type&& __v);
522    template <class... _Args>
523    _LIBCPP_INLINE_VISIBILITY
524    void emplace(_Args&&... __args);
525#endif // _LIBCPP_CXX03_LANG
526    _LIBCPP_INLINE_VISIBILITY
527    void pop();
528
529    _LIBCPP_INLINE_VISIBILITY
530    void swap(priority_queue& __q)
531        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
532                   __is_nothrow_swappable<value_compare>::value);
533};
534
535#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
536template <class _Compare,
537          class _Container,
538          class = _EnableIf<!__is_allocator<_Compare>::value>,
539          class = _EnableIf<!__is_allocator<_Container>::value>
540>
541priority_queue(_Compare, _Container)
542    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
543
544template<class _InputIterator,
545         class _Compare = less<__iter_value_type<_InputIterator>>,
546         class _Container = vector<__iter_value_type<_InputIterator>>,
547         class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::value>,
548         class = _EnableIf<!__is_allocator<_Compare>::value>,
549         class = _EnableIf<!__is_allocator<_Container>::value>
550>
551priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
552    -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
553
554template<class _Compare,
555         class _Container,
556         class _Alloc,
557         class = _EnableIf<!__is_allocator<_Compare>::value>,
558         class = _EnableIf<!__is_allocator<_Container>::value>,
559         class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
560>
561priority_queue(_Compare, _Container, _Alloc)
562    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
563#endif
564
565template <class _Tp, class _Container, class _Compare>
566inline
567priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
568                                                          const container_type& __c)
569    : c(__c),
570      comp(__comp)
571{
572    _VSTD::make_heap(c.begin(), c.end(), comp);
573}
574
575#ifndef _LIBCPP_CXX03_LANG
576
577template <class _Tp, class _Container, class _Compare>
578inline
579priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
580                                                          container_type&& __c)
581    : c(_VSTD::move(__c)),
582      comp(__comp)
583{
584    _VSTD::make_heap(c.begin(), c.end(), comp);
585}
586
587#endif // _LIBCPP_CXX03_LANG
588
589template <class _Tp, class _Container, class _Compare>
590template <class _InputIter>
591inline
592priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
593                                                          const value_compare& __comp)
594    : c(__f, __l),
595      comp(__comp)
596{
597    _VSTD::make_heap(c.begin(), c.end(), comp);
598}
599
600template <class _Tp, class _Container, class _Compare>
601template <class _InputIter>
602inline
603priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
604                                                          const value_compare& __comp,
605                                                          const container_type& __c)
606    : c(__c),
607      comp(__comp)
608{
609    c.insert(c.end(), __f, __l);
610    _VSTD::make_heap(c.begin(), c.end(), comp);
611}
612
613#ifndef _LIBCPP_CXX03_LANG
614
615template <class _Tp, class _Container, class _Compare>
616template <class _InputIter>
617inline
618priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
619                                                          const value_compare& __comp,
620                                                          container_type&& __c)
621    : c(_VSTD::move(__c)),
622      comp(__comp)
623{
624    c.insert(c.end(), __f, __l);
625    _VSTD::make_heap(c.begin(), c.end(), comp);
626}
627
628#endif // _LIBCPP_CXX03_LANG
629
630template <class _Tp, class _Container, class _Compare>
631template <class _Alloc>
632inline
633priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
634                       _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
635    : c(__a)
636{
637}
638
639template <class _Tp, class _Container, class _Compare>
640template <class _Alloc>
641inline
642priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
643                                                          const _Alloc& __a,
644                       _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
645    : c(__a),
646      comp(__comp)
647{
648}
649
650template <class _Tp, class _Container, class _Compare>
651template <class _Alloc>
652inline
653priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
654                                                          const container_type& __c,
655                                                          const _Alloc& __a,
656                       _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
657    : c(__c, __a),
658      comp(__comp)
659{
660    _VSTD::make_heap(c.begin(), c.end(), comp);
661}
662
663template <class _Tp, class _Container, class _Compare>
664template <class _Alloc>
665inline
666priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
667                                                          const _Alloc& __a,
668                       _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
669    : c(__q.c, __a),
670      comp(__q.comp)
671{
672    _VSTD::make_heap(c.begin(), c.end(), comp);
673}
674
675#ifndef _LIBCPP_CXX03_LANG
676
677template <class _Tp, class _Container, class _Compare>
678template <class _Alloc>
679inline
680priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
681                                                          container_type&& __c,
682                                                          const _Alloc& __a,
683                       _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
684    : c(_VSTD::move(__c), __a),
685      comp(__comp)
686{
687    _VSTD::make_heap(c.begin(), c.end(), comp);
688}
689
690template <class _Tp, class _Container, class _Compare>
691template <class _Alloc>
692inline
693priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
694                                                          const _Alloc& __a,
695                       _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
696    : c(_VSTD::move(__q.c), __a),
697      comp(_VSTD::move(__q.comp))
698{
699    _VSTD::make_heap(c.begin(), c.end(), comp);
700}
701
702#endif // _LIBCPP_CXX03_LANG
703
704template <class _Tp, class _Container, class _Compare>
705inline
706void
707priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
708{
709    c.push_back(__v);
710    _VSTD::push_heap(c.begin(), c.end(), comp);
711}
712
713#ifndef _LIBCPP_CXX03_LANG
714
715template <class _Tp, class _Container, class _Compare>
716inline
717void
718priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
719{
720    c.push_back(_VSTD::move(__v));
721    _VSTD::push_heap(c.begin(), c.end(), comp);
722}
723
724template <class _Tp, class _Container, class _Compare>
725template <class... _Args>
726inline
727void
728priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
729{
730    c.emplace_back(_VSTD::forward<_Args>(__args)...);
731    _VSTD::push_heap(c.begin(), c.end(), comp);
732}
733
734#endif // _LIBCPP_CXX03_LANG
735
736template <class _Tp, class _Container, class _Compare>
737inline
738void
739priority_queue<_Tp, _Container, _Compare>::pop()
740{
741    _VSTD::pop_heap(c.begin(), c.end(), comp);
742    c.pop_back();
743}
744
745template <class _Tp, class _Container, class _Compare>
746inline
747void
748priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
749        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
750                   __is_nothrow_swappable<value_compare>::value)
751{
752    using _VSTD::swap;
753    swap(c, __q.c);
754    swap(comp, __q.comp);
755}
756
757template <class _Tp, class _Container, class _Compare>
758inline _LIBCPP_INLINE_VISIBILITY
759_EnableIf<
760    __is_swappable<_Container>::value && __is_swappable<_Compare>::value,
761    void
762>
763swap(priority_queue<_Tp, _Container, _Compare>& __x,
764     priority_queue<_Tp, _Container, _Compare>& __y)
765    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
766{
767    __x.swap(__y);
768}
769
770template <class _Tp, class _Container, class _Compare, class _Alloc>
771struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
772    : public uses_allocator<_Container, _Alloc>
773{
774};
775
776_LIBCPP_END_NAMESPACE_STD
777
778#endif // _LIBCPP_QUEUE
779