xref: /freebsd-12.1/contrib/libc++/include/queue (revision 2b375b4e) 
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    _LIBCPP_INLINE_VISIBILITY
440    priority_queue(const value_compare& __comp, const container_type& __c);
441#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
442    _LIBCPP_INLINE_VISIBILITY
443    explicit priority_queue(const value_compare& __comp, container_type&& __c);
444#endif
445    template <class _InputIter>
446        _LIBCPP_INLINE_VISIBILITY
447        priority_queue(_InputIter __f, _InputIter __l,
448                       const value_compare& __comp = value_compare());
449    template <class _InputIter>
450        _LIBCPP_INLINE_VISIBILITY
451        priority_queue(_InputIter __f, _InputIter __l,
452                       const value_compare& __comp, const container_type& __c);
453#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
454    template <class _InputIter>
455        _LIBCPP_INLINE_VISIBILITY
456        priority_queue(_InputIter __f, _InputIter __l,
457                       const value_compare& __comp, container_type&& __c);
458#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
459    template <class _Alloc>
460        _LIBCPP_INLINE_VISIBILITY
461        explicit priority_queue(const _Alloc& __a,
462                       typename enable_if<uses_allocator<container_type,
463                                                         _Alloc>::value>::type* = 0);
464    template <class _Alloc>
465        _LIBCPP_INLINE_VISIBILITY
466        priority_queue(const value_compare& __comp, const _Alloc& __a,
467                       typename enable_if<uses_allocator<container_type,
468                                                         _Alloc>::value>::type* = 0);
469    template <class _Alloc>
470        _LIBCPP_INLINE_VISIBILITY
471        priority_queue(const value_compare& __comp, const container_type& __c,
472                       const _Alloc& __a,
473                       typename enable_if<uses_allocator<container_type,
474                                                         _Alloc>::value>::type* = 0);
475    template <class _Alloc>
476        _LIBCPP_INLINE_VISIBILITY
477        priority_queue(const priority_queue& __q, const _Alloc& __a,
478                       typename enable_if<uses_allocator<container_type,
479                                                         _Alloc>::value>::type* = 0);
480#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
481    template <class _Alloc>
482        _LIBCPP_INLINE_VISIBILITY
483        priority_queue(const value_compare& __comp, container_type&& __c,
484                       const _Alloc& __a,
485                       typename enable_if<uses_allocator<container_type,
486                                                         _Alloc>::value>::type* = 0);
487    template <class _Alloc>
488        _LIBCPP_INLINE_VISIBILITY
489        priority_queue(priority_queue&& __q, const _Alloc& __a,
490                       typename enable_if<uses_allocator<container_type,
491                                                         _Alloc>::value>::type* = 0);
492#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
493
494    _LIBCPP_INLINE_VISIBILITY
495    bool            empty() const {return c.empty();}
496    _LIBCPP_INLINE_VISIBILITY
497    size_type       size() const  {return c.size();}
498    _LIBCPP_INLINE_VISIBILITY
499    const_reference top() const   {return c.front();}
500
501    _LIBCPP_INLINE_VISIBILITY
502    void push(const value_type& __v);
503#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
504    _LIBCPP_INLINE_VISIBILITY
505    void push(value_type&& __v);
506#ifndef _LIBCPP_HAS_NO_VARIADICS
507    template <class... _Args> _LIBCPP_INLINE_VISIBILITY void emplace(_Args&&... __args);
508#endif
509#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
510    _LIBCPP_INLINE_VISIBILITY
511    void pop();
512
513    _LIBCPP_INLINE_VISIBILITY
514    void swap(priority_queue& __q)
515        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
516                   __is_nothrow_swappable<value_compare>::value);
517};
518
519template <class _Tp, class _Container, class _Compare>
520inline
521priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
522                                                          const container_type& __c)
523    : c(__c),
524      comp(__comp)
525{
526    _VSTD::make_heap(c.begin(), c.end(), comp);
527}
528
529#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
530
531template <class _Tp, class _Container, class _Compare>
532inline
533priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
534                                                          container_type&& __c)
535    : c(_VSTD::move(__c)),
536      comp(__comp)
537{
538    _VSTD::make_heap(c.begin(), c.end(), comp);
539}
540
541#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
542
543template <class _Tp, class _Container, class _Compare>
544template <class _InputIter>
545inline
546priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
547                                                          const value_compare& __comp)
548    : c(__f, __l),
549      comp(__comp)
550{
551    _VSTD::make_heap(c.begin(), c.end(), comp);
552}
553
554template <class _Tp, class _Container, class _Compare>
555template <class _InputIter>
556inline
557priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
558                                                          const value_compare& __comp,
559                                                          const container_type& __c)
560    : c(__c),
561      comp(__comp)
562{
563    c.insert(c.end(), __f, __l);
564    _VSTD::make_heap(c.begin(), c.end(), comp);
565}
566
567#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
568
569template <class _Tp, class _Container, class _Compare>
570template <class _InputIter>
571inline
572priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
573                                                          const value_compare& __comp,
574                                                          container_type&& __c)
575    : c(_VSTD::move(__c)),
576      comp(__comp)
577{
578    c.insert(c.end(), __f, __l);
579    _VSTD::make_heap(c.begin(), c.end(), comp);
580}
581
582#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
583
584template <class _Tp, class _Container, class _Compare>
585template <class _Alloc>
586inline
587priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
588                       typename enable_if<uses_allocator<container_type,
589                                                         _Alloc>::value>::type*)
590    : c(__a)
591{
592}
593
594template <class _Tp, class _Container, class _Compare>
595template <class _Alloc>
596inline
597priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
598                                                          const _Alloc& __a,
599                       typename enable_if<uses_allocator<container_type,
600                                                         _Alloc>::value>::type*)
601    : c(__a),
602      comp(__comp)
603{
604}
605
606template <class _Tp, class _Container, class _Compare>
607template <class _Alloc>
608inline
609priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
610                                                          const container_type& __c,
611                                                          const _Alloc& __a,
612                       typename enable_if<uses_allocator<container_type,
613                                                         _Alloc>::value>::type*)
614    : c(__c, __a),
615      comp(__comp)
616{
617    _VSTD::make_heap(c.begin(), c.end(), comp);
618}
619
620template <class _Tp, class _Container, class _Compare>
621template <class _Alloc>
622inline
623priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
624                                                          const _Alloc& __a,
625                       typename enable_if<uses_allocator<container_type,
626                                                         _Alloc>::value>::type*)
627    : c(__q.c, __a),
628      comp(__q.comp)
629{
630    _VSTD::make_heap(c.begin(), c.end(), comp);
631}
632
633#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
634
635template <class _Tp, class _Container, class _Compare>
636template <class _Alloc>
637inline
638priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
639                                                          container_type&& __c,
640                                                          const _Alloc& __a,
641                       typename enable_if<uses_allocator<container_type,
642                                                         _Alloc>::value>::type*)
643    : c(_VSTD::move(__c), __a),
644      comp(__comp)
645{
646    _VSTD::make_heap(c.begin(), c.end(), comp);
647}
648
649template <class _Tp, class _Container, class _Compare>
650template <class _Alloc>
651inline
652priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
653                                                          const _Alloc& __a,
654                       typename enable_if<uses_allocator<container_type,
655                                                         _Alloc>::value>::type*)
656    : c(_VSTD::move(__q.c), __a),
657      comp(_VSTD::move(__q.comp))
658{
659    _VSTD::make_heap(c.begin(), c.end(), comp);
660}
661
662#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
663
664template <class _Tp, class _Container, class _Compare>
665inline
666void
667priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
668{
669    c.push_back(__v);
670    _VSTD::push_heap(c.begin(), c.end(), comp);
671}
672
673#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
674
675template <class _Tp, class _Container, class _Compare>
676inline
677void
678priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
679{
680    c.push_back(_VSTD::move(__v));
681    _VSTD::push_heap(c.begin(), c.end(), comp);
682}
683
684#ifndef _LIBCPP_HAS_NO_VARIADICS
685
686template <class _Tp, class _Container, class _Compare>
687template <class... _Args>
688inline
689void
690priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
691{
692    c.emplace_back(_VSTD::forward<_Args>(__args)...);
693    _VSTD::push_heap(c.begin(), c.end(), comp);
694}
695
696#endif  // _LIBCPP_HAS_NO_VARIADICS
697#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
698
699template <class _Tp, class _Container, class _Compare>
700inline
701void
702priority_queue<_Tp, _Container, _Compare>::pop()
703{
704    _VSTD::pop_heap(c.begin(), c.end(), comp);
705    c.pop_back();
706}
707
708template <class _Tp, class _Container, class _Compare>
709inline
710void
711priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
712        _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
713                   __is_nothrow_swappable<value_compare>::value)
714{
715    using _VSTD::swap;
716    swap(c, __q.c);
717    swap(comp, __q.comp);
718}
719
720template <class _Tp, class _Container, class _Compare>
721inline _LIBCPP_INLINE_VISIBILITY
722typename enable_if<
723    __is_swappable<_Container>::value
724    && __is_swappable<_Compare>::value,
725    void
726>::type
727swap(priority_queue<_Tp, _Container, _Compare>& __x,
728     priority_queue<_Tp, _Container, _Compare>& __y)
729    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
730{
731    __x.swap(__y);
732}
733
734template <class _Tp, class _Container, class _Compare, class _Alloc>
735struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
736    : public uses_allocator<_Container, _Alloc>
737{
738};
739
740_LIBCPP_END_NAMESPACE_STD
741
742#endif  // _LIBCPP_QUEUE
743