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