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