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