xref: /llvm-project-15.0.7/libcxx/include/queue (revision f07dd8d0) 
1// -*- C++ -*-
2//===--------------------------- queue ------------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_QUEUE
12#define _LIBCPP_QUEUE
13
14/*
15    queue synopsis
16
17namespace std
18{
19
20template <class T, class Container = deque<T>>
21class queue
22{
23public:
24    typedef Container                                container_type;
25    typedef typename container_type::value_type      value_type;
26    typedef typename container_type::reference       reference;
27    typedef typename container_type::const_reference const_reference;
28    typedef typename container_type::size_type       size_type;
29
30protected:
31    container_type c;
32
33public:
34    queue() = default;
35    ~queue() = default;
36
37    queue(const queue& q) = default;
38    queue(queue&& q) = default;
39
40    queue& operator=(const queue& q) = default;
41    queue& operator=(queue&& q) = default;
42
43    explicit queue(const container_type& c);
44    explicit queue(container_type&& c)
45    template <class Alloc>
46        explicit queue(const Alloc& a);
47    template <class Alloc>
48        queue(const container_type& c, const Alloc& a);
49    template <class Alloc>
50        queue(container_type&& c, const Alloc& a);
51    template <class Alloc>
52        queue(const queue& q, const Alloc& a);
53    template <class Alloc>
54        queue(queue&& q, const Alloc& a);
55
56    bool      empty() const;
57    size_type size() const;
58
59    reference       front();
60    const_reference front() const;
61    reference       back();
62    const_reference back() const;
63
64    void push(const value_type& v);
65    void push(value_type&& v);
66    template <class... Args> void emplace(Args&&... args);
67    void pop();
68
69    void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
70};
71
72template <class T, class Container>
73  bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
74
75template <class T, class Container>
76  bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
77
78template <class T, class Container>
79  bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
80
81template <class T, class Container>
82  bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
83
84template <class T, class Container>
85  bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
86
87template <class T, class Container>
88  bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
89
90template <class T, class Container>
91  void swap(queue<T, Container>& x, queue<T, Container>& y)
92  noexcept(noexcept(x.swap(y)));
93
94template <class T, class Container = vector<T>,
95          class Compare = less<typename Container::value_type>>
96class priority_queue
97{
98public:
99    typedef Container                                container_type;
100    typedef typename container_type::value_type      value_type;
101    typedef typename container_type::reference       reference;
102    typedef typename container_type::const_reference const_reference;
103    typedef typename container_type::size_type       size_type;
104
105protected:
106    container_type c;
107    Compare comp;
108
109public:
110    priority_queue() = default;
111    ~priority_queue() = default;
112
113    priority_queue(const priority_queue& q) = default;
114    priority_queue(priority_queue&& q) = default;
115
116    priority_queue& operator=(const priority_queue& q) = default;
117    priority_queue& operator=(priority_queue&& q) = default;
118
119    explicit priority_queue(const Compare& comp);
120    priority_queue(const Compare& comp, const container_type& c);
121    explicit priority_queue(const Compare& comp, container_type&& c);
122    template <class InputIterator>
123        priority_queue(InputIterator first, InputIterator last,
124                       const Compare& comp = Compare());
125    template <class InputIterator>
126        priority_queue(InputIterator first, InputIterator last,
127                       const Compare& comp, const container_type& c);
128    template <class InputIterator>
129        priority_queue(InputIterator first, InputIterator last,
130                       const Compare& comp, container_type&& c);
131    template <class Alloc>
132        explicit priority_queue(const Alloc& a);
133    template <class Alloc>
134        priority_queue(const Compare& comp, const Alloc& a);
135    template <class Alloc>
136        priority_queue(const Compare& comp, const container_type& c,
137                       const Alloc& a);
138    template <class Alloc>
139        priority_queue(const Compare& comp, container_type&& c,
140                       const Alloc& a);
141    template <class Alloc>
142        priority_queue(const priority_queue& q, const Alloc& a);
143    template <class Alloc>
144        priority_queue(priority_queue&& q, const Alloc& a);
145
146    bool            empty() const;
147    size_type       size() const;
148    const_reference top() const;
149
150    void push(const value_type& v);
151    void push(value_type&& v);
152    template <class... Args> void emplace(Args&&... args);
153    void pop();
154
155    void swap(priority_queue& q)
156        noexcept(is_nothrow_swappable_v<Container> &&
157                 is_nothrow_swappable_v<Comp>)
158};
159
160template <class T, class Container, class Compare>
161  void swap(priority_queue<T, Container, Compare>& x,
162            priority_queue<T, Container, Compare>& y)
163            noexcept(noexcept(x.swap(y)));
164
165}  // std
166
167*/
168
169#include <__config>
170#include <deque>
171#include <vector>
172#include <functional>
173#include <algorithm>
174
175#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
176#pragma GCC system_header
177#endif
178
179_LIBCPP_BEGIN_NAMESPACE_STD
180
181template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TYPE_VIS_ONLY queue;
182
183template <class _Tp, class _Container>
184_LIBCPP_INLINE_VISIBILITY
185bool
186operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
187
188template <class _Tp, class _Container>
189_LIBCPP_INLINE_VISIBILITY
190bool
191operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
192
193template <class _Tp, class _Container /*= deque<_Tp>*/>
194class _LIBCPP_TYPE_VIS_ONLY queue
195{
196public:
197    typedef _Container                               container_type;
198    typedef typename container_type::value_type      value_type;
199    typedef typename container_type::reference       reference;
200    typedef typename container_type::const_reference const_reference;
201    typedef typename container_type::size_type       size_type;
202    static_assert((is_same<_Tp, value_type>::value), "" );
203
204protected:
205    container_type c;
206
207public:
208    _LIBCPP_INLINE_VISIBILITY
209    queue()
210        _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
211        : c() {}
212
213    _LIBCPP_INLINE_VISIBILITY
214    queue(const queue& __q) : c(__q.c) {}
215
216#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
217    _LIBCPP_INLINE_VISIBILITY
218    queue(queue&& __q)
219        _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
220        : c(_VSTD::move(__q.c)) {}
221#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
222
223    _LIBCPP_INLINE_VISIBILITY
224    queue& operator=(const queue& __q) {c = __q.c; return *this;}
225
226#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
227    _LIBCPP_INLINE_VISIBILITY
228    queue& operator=(queue&& __q)
229        _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
230        {c = _VSTD::move(__q.c); return *this;}
231#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
232
233    _LIBCPP_INLINE_VISIBILITY
234    explicit queue(const container_type& __c)  : c(__c) {}
235#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
236    _LIBCPP_INLINE_VISIBILITY
237    explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
238#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
239    template <class _Alloc>
240        _LIBCPP_INLINE_VISIBILITY
241        explicit queue(const _Alloc& __a,
242                       typename enable_if<uses_allocator<container_type,
243                                                         _Alloc>::value>::type* = 0)
244            : c(__a) {}
245    template <class _Alloc>
246        _LIBCPP_INLINE_VISIBILITY
247        queue(const queue& __q, const _Alloc& __a,
248                       typename enable_if<uses_allocator<container_type,
249                                                         _Alloc>::value>::type* = 0)
250            : c(__q.c, __a) {}
251    template <class _Alloc>
252        _LIBCPP_INLINE_VISIBILITY
253        queue(const container_type& __c, const _Alloc& __a,
254                       typename enable_if<uses_allocator<container_type,
255                                                         _Alloc>::value>::type* = 0)
256            : c(__c, __a) {}
257#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
258    template <class _Alloc>
259        _LIBCPP_INLINE_VISIBILITY
260        queue(container_type&& __c, const _Alloc& __a,
261                       typename enable_if<uses_allocator<container_type,
262                                                         _Alloc>::value>::type* = 0)
263            : c(_VSTD::move(__c), __a) {}
264    template <class _Alloc>
265        _LIBCPP_INLINE_VISIBILITY
266        queue(queue&& __q, const _Alloc& __a,
267                       typename enable_if<uses_allocator<container_type,
268                                                         _Alloc>::value>::type* = 0)
269            : c(_VSTD::move(__q.c), __a) {}
270
271#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
272
273    _LIBCPP_INLINE_VISIBILITY
274    bool      empty() const {return c.empty();}
275    _LIBCPP_INLINE_VISIBILITY
276    size_type size() const  {return c.size();}
277
278    _LIBCPP_INLINE_VISIBILITY
279    reference       front()       {return c.front();}
280    _LIBCPP_INLINE_VISIBILITY
281    const_reference front() const {return c.front();}
282    _LIBCPP_INLINE_VISIBILITY
283    reference       back()        {return c.back();}
284    _LIBCPP_INLINE_VISIBILITY
285    const_reference back() const  {return c.back();}
286
287    _LIBCPP_INLINE_VISIBILITY
288    void push(const value_type& __v) {c.push_back(__v);}
289#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
290    _LIBCPP_INLINE_VISIBILITY
291    void push(value_type&& __v)      {c.push_back(_VSTD::move(__v));}
292#ifndef _LIBCPP_HAS_NO_VARIADICS
293    template <class... _Args>
294        _LIBCPP_INLINE_VISIBILITY
295        void emplace(_Args&&... __args)
296            {c.emplace_back(_VSTD::forward<_Args>(__args)...);}
297#endif  // _LIBCPP_HAS_NO_VARIADICS
298#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
299    _LIBCPP_INLINE_VISIBILITY
300    void pop() {c.pop_front();}
301
302    _LIBCPP_INLINE_VISIBILITY
303    void swap(queue& __q)
304        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
305    {
306        using _VSTD::swap;
307        swap(c, __q.c);
308    }
309
310    template <class _T1, class _C1>
311    friend
312    _LIBCPP_INLINE_VISIBILITY
313    bool
314    operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
315
316    template <class _T1, class _C1>
317    friend
318    _LIBCPP_INLINE_VISIBILITY
319    bool
320    operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
321};
322
323template <class _Tp, class _Container>
324inline _LIBCPP_INLINE_VISIBILITY
325bool
326operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
327{
328    return __x.c == __y.c;
329}
330
331template <class _Tp, class _Container>
332inline _LIBCPP_INLINE_VISIBILITY
333bool
334operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
335{
336    return __x.c < __y.c;
337}
338
339template <class _Tp, class _Container>
340inline _LIBCPP_INLINE_VISIBILITY
341bool
342operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
343{
344    return !(__x == __y);
345}
346
347template <class _Tp, class _Container>
348inline _LIBCPP_INLINE_VISIBILITY
349bool
350operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
351{
352    return __y < __x;
353}
354
355template <class _Tp, class _Container>
356inline _LIBCPP_INLINE_VISIBILITY
357bool
358operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
359{
360    return !(__x < __y);
361}
362
363template <class _Tp, class _Container>
364inline _LIBCPP_INLINE_VISIBILITY
365bool
366operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
367{
368    return !(__y < __x);
369}
370
371template <class _Tp, class _Container>
372inline _LIBCPP_INLINE_VISIBILITY
373typename enable_if<
374    __is_swappable<_Container>::value,
375    void
376>::type
377swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
378    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
379{
380    __x.swap(__y);
381}
382
383template <class _Tp, class _Container, class _Alloc>
384struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<queue<_Tp, _Container>, _Alloc>
385    : public uses_allocator<_Container, _Alloc>
386{
387};
388
389template <class _Tp, class _Container = vector<_Tp>,
390          class _Compare = less<typename _Container::value_type> >
391class _LIBCPP_TYPE_VIS_ONLY priority_queue
392{
393public:
394    typedef _Container                               container_type;
395    typedef _Compare                                 value_compare;
396    typedef typename container_type::value_type      value_type;
397    typedef typename container_type::reference       reference;
398    typedef typename container_type::const_reference const_reference;
399    typedef typename container_type::size_type       size_type;
400    static_assert((is_same<_Tp, value_type>::value), "" );
401
402protected:
403    container_type c;
404    value_compare comp;
405
406public:
407    _LIBCPP_INLINE_VISIBILITY
408    priority_queue()
409        _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
410                   is_nothrow_default_constructible<value_compare>::value)
411        : c(), comp() {}
412
413    _LIBCPP_INLINE_VISIBILITY
414    priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
415
416#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
417    _LIBCPP_INLINE_VISIBILITY
418    priority_queue(priority_queue&& __q)
419        _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
420                   is_nothrow_move_constructible<value_compare>::value)
421        : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
422#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
423
424    _LIBCPP_INLINE_VISIBILITY
425    priority_queue& operator=(const priority_queue& __q)
426        {c = __q.c; comp = __q.comp; return *this;}
427
428#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
429    _LIBCPP_INLINE_VISIBILITY
430    priority_queue& operator=(priority_queue&& __q)
431        _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
432                   is_nothrow_move_assignable<value_compare>::value)
433        {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
434#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
435
436    _LIBCPP_INLINE_VISIBILITY
437    explicit priority_queue(const value_compare& __comp)
438        : c(), comp(__comp) {}
439    priority_queue(const value_compare& __comp, const container_type& __c);
440#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
441    explicit priority_queue(const value_compare& __comp, container_type&& __c);
442#endif
443    template <class _InputIter>
444        priority_queue(_InputIter __f, _InputIter __l,
445                       const value_compare& __comp = value_compare());
446    template <class _InputIter>
447        priority_queue(_InputIter __f, _InputIter __l,
448                       const value_compare& __comp, const container_type& __c);
449#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
450    template <class _InputIter>
451        priority_queue(_InputIter __f, _InputIter __l,
452                       const value_compare& __comp, container_type&& __c);
453#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
454    template <class _Alloc>
455        explicit priority_queue(const _Alloc& __a,
456                       typename enable_if<uses_allocator<container_type,
457                                                         _Alloc>::value>::type* = 0);
458    template <class _Alloc>
459        priority_queue(const value_compare& __comp, const _Alloc& __a,
460                       typename enable_if<uses_allocator<container_type,
461                                                         _Alloc>::value>::type* = 0);
462    template <class _Alloc>
463        priority_queue(const value_compare& __comp, const container_type& __c,
464                       const _Alloc& __a,
465                       typename enable_if<uses_allocator<container_type,
466                                                         _Alloc>::value>::type* = 0);
467    template <class _Alloc>
468        priority_queue(const priority_queue& __q, const _Alloc& __a,
469                       typename enable_if<uses_allocator<container_type,
470                                                         _Alloc>::value>::type* = 0);
471#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
472    template <class _Alloc>
473        priority_queue(const value_compare& __comp, container_type&& __c,
474                       const _Alloc& __a,
475                       typename enable_if<uses_allocator<container_type,
476                                                         _Alloc>::value>::type* = 0);
477    template <class _Alloc>
478        priority_queue(priority_queue&& __q, const _Alloc& __a,
479                       typename enable_if<uses_allocator<container_type,
480                                                         _Alloc>::value>::type* = 0);
481#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
482
483    _LIBCPP_INLINE_VISIBILITY
484    bool            empty() const {return c.empty();}
485    _LIBCPP_INLINE_VISIBILITY
486    size_type       size() const  {return c.size();}
487    _LIBCPP_INLINE_VISIBILITY
488    const_reference top() const   {return c.front();}
489
490    void push(const value_type& __v);
491#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
492    void push(value_type&& __v);
493#ifndef _LIBCPP_HAS_NO_VARIADICS
494    template <class... _Args> void emplace(_Args&&... __args);
495#endif
496#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
497    void pop();
498
499    void swap(priority_queue& __q)
500        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
501                   __is_nothrow_swappable<value_compare>::value);
502};
503
504template <class _Tp, class _Container, class _Compare>
505inline _LIBCPP_INLINE_VISIBILITY
506priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
507                                                          const container_type& __c)
508    : c(__c),
509      comp(__comp)
510{
511    _VSTD::make_heap(c.begin(), c.end(), comp);
512}
513
514#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
515
516template <class _Tp, class _Container, class _Compare>
517inline _LIBCPP_INLINE_VISIBILITY
518priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
519                                                          container_type&& __c)
520    : c(_VSTD::move(__c)),
521      comp(__comp)
522{
523    _VSTD::make_heap(c.begin(), c.end(), comp);
524}
525
526#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
527
528template <class _Tp, class _Container, class _Compare>
529template <class _InputIter>
530inline _LIBCPP_INLINE_VISIBILITY
531priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
532                                                          const value_compare& __comp)
533    : c(__f, __l),
534      comp(__comp)
535{
536    _VSTD::make_heap(c.begin(), c.end(), comp);
537}
538
539template <class _Tp, class _Container, class _Compare>
540template <class _InputIter>
541inline _LIBCPP_INLINE_VISIBILITY
542priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
543                                                          const value_compare& __comp,
544                                                          const container_type& __c)
545    : c(__c),
546      comp(__comp)
547{
548    c.insert(c.end(), __f, __l);
549    _VSTD::make_heap(c.begin(), c.end(), comp);
550}
551
552#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
553
554template <class _Tp, class _Container, class _Compare>
555template <class _InputIter>
556inline _LIBCPP_INLINE_VISIBILITY
557priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
558                                                          const value_compare& __comp,
559                                                          container_type&& __c)
560    : c(_VSTD::move(__c)),
561      comp(__comp)
562{
563    c.insert(c.end(), __f, __l);
564    _VSTD::make_heap(c.begin(), c.end(), comp);
565}
566
567#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
568
569template <class _Tp, class _Container, class _Compare>
570template <class _Alloc>
571inline _LIBCPP_INLINE_VISIBILITY
572priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
573                       typename enable_if<uses_allocator<container_type,
574                                                         _Alloc>::value>::type*)
575    : c(__a)
576{
577}
578
579template <class _Tp, class _Container, class _Compare>
580template <class _Alloc>
581inline _LIBCPP_INLINE_VISIBILITY
582priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
583                                                          const _Alloc& __a,
584                       typename enable_if<uses_allocator<container_type,
585                                                         _Alloc>::value>::type*)
586    : c(__a),
587      comp(__comp)
588{
589}
590
591template <class _Tp, class _Container, class _Compare>
592template <class _Alloc>
593inline _LIBCPP_INLINE_VISIBILITY
594priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
595                                                          const container_type& __c,
596                                                          const _Alloc& __a,
597                       typename enable_if<uses_allocator<container_type,
598                                                         _Alloc>::value>::type*)
599    : c(__c, __a),
600      comp(__comp)
601{
602    _VSTD::make_heap(c.begin(), c.end(), comp);
603}
604
605template <class _Tp, class _Container, class _Compare>
606template <class _Alloc>
607inline _LIBCPP_INLINE_VISIBILITY
608priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
609                                                          const _Alloc& __a,
610                       typename enable_if<uses_allocator<container_type,
611                                                         _Alloc>::value>::type*)
612    : c(__q.c, __a),
613      comp(__q.comp)
614{
615    _VSTD::make_heap(c.begin(), c.end(), comp);
616}
617
618#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
619
620template <class _Tp, class _Container, class _Compare>
621template <class _Alloc>
622inline _LIBCPP_INLINE_VISIBILITY
623priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
624                                                          container_type&& __c,
625                                                          const _Alloc& __a,
626                       typename enable_if<uses_allocator<container_type,
627                                                         _Alloc>::value>::type*)
628    : c(_VSTD::move(__c), __a),
629      comp(__comp)
630{
631    _VSTD::make_heap(c.begin(), c.end(), comp);
632}
633
634template <class _Tp, class _Container, class _Compare>
635template <class _Alloc>
636inline _LIBCPP_INLINE_VISIBILITY
637priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
638                                                          const _Alloc& __a,
639                       typename enable_if<uses_allocator<container_type,
640                                                         _Alloc>::value>::type*)
641    : c(_VSTD::move(__q.c), __a),
642      comp(_VSTD::move(__q.comp))
643{
644    _VSTD::make_heap(c.begin(), c.end(), comp);
645}
646
647#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
648
649template <class _Tp, class _Container, class _Compare>
650inline _LIBCPP_INLINE_VISIBILITY
651void
652priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
653{
654    c.push_back(__v);
655    _VSTD::push_heap(c.begin(), c.end(), comp);
656}
657
658#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
659
660template <class _Tp, class _Container, class _Compare>
661inline _LIBCPP_INLINE_VISIBILITY
662void
663priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
664{
665    c.push_back(_VSTD::move(__v));
666    _VSTD::push_heap(c.begin(), c.end(), comp);
667}
668
669#ifndef _LIBCPP_HAS_NO_VARIADICS
670
671template <class _Tp, class _Container, class _Compare>
672template <class... _Args>
673inline _LIBCPP_INLINE_VISIBILITY
674void
675priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
676{
677    c.emplace_back(_VSTD::forward<_Args>(__args)...);
678    _VSTD::push_heap(c.begin(), c.end(), comp);
679}
680
681#endif  // _LIBCPP_HAS_NO_VARIADICS
682#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
683
684template <class _Tp, class _Container, class _Compare>
685inline _LIBCPP_INLINE_VISIBILITY
686void
687priority_queue<_Tp, _Container, _Compare>::pop()
688{
689    _VSTD::pop_heap(c.begin(), c.end(), comp);
690    c.pop_back();
691}
692
693template <class _Tp, class _Container, class _Compare>
694inline _LIBCPP_INLINE_VISIBILITY
695void
696priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
697        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
698                   __is_nothrow_swappable<value_compare>::value)
699{
700    using _VSTD::swap;
701    swap(c, __q.c);
702    swap(comp, __q.comp);
703}
704
705template <class _Tp, class _Container, class _Compare>
706inline _LIBCPP_INLINE_VISIBILITY
707typename enable_if<
708    __is_swappable<_Container>::value
709    && __is_swappable<_Compare>::value,
710    void
711>::type
712swap(priority_queue<_Tp, _Container, _Compare>& __x,
713     priority_queue<_Tp, _Container, _Compare>& __y)
714    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
715{
716    __x.swap(__y);
717}
718
719template <class _Tp, class _Container, class _Compare, class _Alloc>
720struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
721    : public uses_allocator<_Container, _Alloc>
722{
723};
724
725_LIBCPP_END_NAMESPACE_STD
726
727#endif  // _LIBCPP_QUEUE
728