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