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