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