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