2 //===--------------------------- queue ------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
20 template <class T, class Container = deque<T>>
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;
37 queue(const queue& q) = default;
38 queue(queue&& q) = default;
40 queue& operator=(const queue& q) = default;
41 queue& operator=(queue&& q) = default;
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);
57 size_type size() const;
60 const_reference front() const;
62 const_reference back() const;
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
69 void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
72 template <class T, class Container>
73 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
75 template <class T, class Container>
76 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
78 template <class T, class Container>
79 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
81 template <class T, class Container>
82 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
84 template <class T, class Container>
85 bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
87 template <class T, class Container>
88 bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
90 template <class T, class Container>
91 void swap(queue<T, Container>& x, queue<T, Container>& y)
92 noexcept(noexcept(x.swap(y)));
94 template <class T, class Container = vector<T>,
95 class Compare = less<typename Container::value_type>>
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;
110 priority_queue() = default;
111 ~priority_queue() = default;
113 priority_queue(const priority_queue& q) = default;
114 priority_queue(priority_queue&& q) = default;
116 priority_queue& operator=(const priority_queue& q) = default;
117 priority_queue& operator=(priority_queue&& q) = default;
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,
138 template <class Alloc>
139 priority_queue(const Compare& comp, container_type&& c,
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);
147 size_type size() const;
148 const_reference top() const;
150 void push(const value_type& v);
151 void push(value_type&& v);
152 template <class... Args> void emplace(Args&&... args);
155 void swap(priority_queue& q)
156 noexcept(is_nothrow_swappable_v<Container> &&
157 is_nothrow_swappable_v<Comp>)
160 template <class T, class Container, class Compare>
161 void swap(priority_queue<T, Container, Compare>& x,
162 priority_queue<T, Container, Compare>& y)
163 noexcept(noexcept(x.swap(y)));
172 #include <functional>
175 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
176 #pragma GCC system_header
179 _LIBCPP_BEGIN_NAMESPACE_STD
181 template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue;
183 template <class _Tp, class _Container>
184 _LIBCPP_INLINE_VISIBILITY
186 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
188 template <class _Tp, class _Container>
189 _LIBCPP_INLINE_VISIBILITY
191 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
193 template <class _Tp, class _Container /*= deque<_Tp>*/>
194 class _LIBCPP_TEMPLATE_VIS queue
197 typedef _Container container_type;
198 typedef typename container_type::value_type value_type;
199 typedef typename container_type::reference reference;
200 typedef typename container_type::const_reference const_reference;
201 typedef typename container_type::size_type size_type;
202 static_assert((is_same<_Tp, value_type>::value), "" );
208 _LIBCPP_INLINE_VISIBILITY
210 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
213 _LIBCPP_INLINE_VISIBILITY
214 queue(const queue& __q) : c(__q.c) {}
216 _LIBCPP_INLINE_VISIBILITY
217 queue& operator=(const queue& __q) {c = __q.c; return *this;}
219 #ifndef _LIBCPP_CXX03_LANG
220 _LIBCPP_INLINE_VISIBILITY
222 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
223 : c(_VSTD::move(__q.c)) {}
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_CXX03_LANG
231 _LIBCPP_INLINE_VISIBILITY
232 explicit queue(const container_type& __c) : c(__c) {}
233 #ifndef _LIBCPP_CXX03_LANG
234 _LIBCPP_INLINE_VISIBILITY
235 explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
236 #endif // _LIBCPP_CXX03_LANG
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)
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)
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)
255 #ifndef _LIBCPP_CXX03_LANG
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) {}
269 #endif // _LIBCPP_CXX03_LANG
271 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
272 bool empty() const {return c.empty();}
273 _LIBCPP_INLINE_VISIBILITY
274 size_type size() const {return c.size();}
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();}
285 _LIBCPP_INLINE_VISIBILITY
286 void push(const value_type& __v) {c.push_back(__v);}
287 #ifndef _LIBCPP_CXX03_LANG
288 _LIBCPP_INLINE_VISIBILITY
289 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));}
290 template <class... _Args>
291 _LIBCPP_INLINE_VISIBILITY
292 #if _LIBCPP_STD_VER > 14
293 reference emplace(_Args&&... __args)
294 { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
296 void emplace(_Args&&... __args)
297 { c.emplace_back(_VSTD::forward<_Args>(__args)...);}
299 #endif // _LIBCPP_CXX03_LANG
300 _LIBCPP_INLINE_VISIBILITY
301 void pop() {c.pop_front();}
303 _LIBCPP_INLINE_VISIBILITY
304 void swap(queue& __q)
305 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
311 template <class _T1, class _C1>
313 _LIBCPP_INLINE_VISIBILITY
315 operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
317 template <class _T1, class _C1>
319 _LIBCPP_INLINE_VISIBILITY
321 operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
324 template <class _Tp, class _Container>
325 inline _LIBCPP_INLINE_VISIBILITY
327 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
329 return __x.c == __y.c;
332 template <class _Tp, class _Container>
333 inline _LIBCPP_INLINE_VISIBILITY
335 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
337 return __x.c < __y.c;
340 template <class _Tp, class _Container>
341 inline _LIBCPP_INLINE_VISIBILITY
343 operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
345 return !(__x == __y);
348 template <class _Tp, class _Container>
349 inline _LIBCPP_INLINE_VISIBILITY
351 operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
356 template <class _Tp, class _Container>
357 inline _LIBCPP_INLINE_VISIBILITY
359 operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
364 template <class _Tp, class _Container>
365 inline _LIBCPP_INLINE_VISIBILITY
367 operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
372 template <class _Tp, class _Container>
373 inline _LIBCPP_INLINE_VISIBILITY
375 __is_swappable<_Container>::value,
378 swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
379 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
384 template <class _Tp, class _Container, class _Alloc>
385 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc>
386 : public uses_allocator<_Container, _Alloc>
390 template <class _Tp, class _Container = vector<_Tp>,
391 class _Compare = less<typename _Container::value_type> >
392 class _LIBCPP_TEMPLATE_VIS priority_queue
395 typedef _Container container_type;
396 typedef _Compare value_compare;
397 typedef typename container_type::value_type value_type;
398 typedef typename container_type::reference reference;
399 typedef typename container_type::const_reference const_reference;
400 typedef typename container_type::size_type size_type;
401 static_assert((is_same<_Tp, value_type>::value), "" );
408 _LIBCPP_INLINE_VISIBILITY
410 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
411 is_nothrow_default_constructible<value_compare>::value)
414 _LIBCPP_INLINE_VISIBILITY
415 priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
417 _LIBCPP_INLINE_VISIBILITY
418 priority_queue& operator=(const priority_queue& __q)
419 {c = __q.c; comp = __q.comp; return *this;}
421 #ifndef _LIBCPP_CXX03_LANG
422 _LIBCPP_INLINE_VISIBILITY
423 priority_queue(priority_queue&& __q)
424 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
425 is_nothrow_move_constructible<value_compare>::value)
426 : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
428 _LIBCPP_INLINE_VISIBILITY
429 priority_queue& operator=(priority_queue&& __q)
430 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
431 is_nothrow_move_assignable<value_compare>::value)
432 {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
433 #endif // _LIBCPP_CXX03_LANG
435 _LIBCPP_INLINE_VISIBILITY
436 explicit priority_queue(const value_compare& __comp)
437 : c(), comp(__comp) {}
438 _LIBCPP_INLINE_VISIBILITY
439 priority_queue(const value_compare& __comp, const container_type& __c);
440 #ifndef _LIBCPP_CXX03_LANG
441 _LIBCPP_INLINE_VISIBILITY
442 explicit priority_queue(const value_compare& __comp, container_type&& __c);
444 template <class _InputIter>
445 _LIBCPP_INLINE_VISIBILITY
446 priority_queue(_InputIter __f, _InputIter __l,
447 const value_compare& __comp = value_compare());
448 template <class _InputIter>
449 _LIBCPP_INLINE_VISIBILITY
450 priority_queue(_InputIter __f, _InputIter __l,
451 const value_compare& __comp, const container_type& __c);
452 #ifndef _LIBCPP_CXX03_LANG
453 template <class _InputIter>
454 _LIBCPP_INLINE_VISIBILITY
455 priority_queue(_InputIter __f, _InputIter __l,
456 const value_compare& __comp, container_type&& __c);
457 #endif // _LIBCPP_CXX03_LANG
458 template <class _Alloc>
459 _LIBCPP_INLINE_VISIBILITY
460 explicit priority_queue(const _Alloc& __a,
461 typename enable_if<uses_allocator<container_type,
462 _Alloc>::value>::type* = 0);
463 template <class _Alloc>
464 _LIBCPP_INLINE_VISIBILITY
465 priority_queue(const value_compare& __comp, const _Alloc& __a,
466 typename enable_if<uses_allocator<container_type,
467 _Alloc>::value>::type* = 0);
468 template <class _Alloc>
469 _LIBCPP_INLINE_VISIBILITY
470 priority_queue(const value_compare& __comp, const container_type& __c,
472 typename enable_if<uses_allocator<container_type,
473 _Alloc>::value>::type* = 0);
474 template <class _Alloc>
475 _LIBCPP_INLINE_VISIBILITY
476 priority_queue(const priority_queue& __q, const _Alloc& __a,
477 typename enable_if<uses_allocator<container_type,
478 _Alloc>::value>::type* = 0);
479 #ifndef _LIBCPP_CXX03_LANG
480 template <class _Alloc>
481 _LIBCPP_INLINE_VISIBILITY
482 priority_queue(const value_compare& __comp, container_type&& __c,
484 typename enable_if<uses_allocator<container_type,
485 _Alloc>::value>::type* = 0);
486 template <class _Alloc>
487 _LIBCPP_INLINE_VISIBILITY
488 priority_queue(priority_queue&& __q, const _Alloc& __a,
489 typename enable_if<uses_allocator<container_type,
490 _Alloc>::value>::type* = 0);
491 #endif // _LIBCPP_CXX03_LANG
493 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
494 bool empty() const {return c.empty();}
495 _LIBCPP_INLINE_VISIBILITY
496 size_type size() const {return c.size();}
497 _LIBCPP_INLINE_VISIBILITY
498 const_reference top() const {return c.front();}
500 _LIBCPP_INLINE_VISIBILITY
501 void push(const value_type& __v);
502 #ifndef _LIBCPP_CXX03_LANG
503 _LIBCPP_INLINE_VISIBILITY
504 void push(value_type&& __v);
505 template <class... _Args>
506 _LIBCPP_INLINE_VISIBILITY
507 void emplace(_Args&&... __args);
508 #endif // _LIBCPP_CXX03_LANG
509 _LIBCPP_INLINE_VISIBILITY
512 _LIBCPP_INLINE_VISIBILITY
513 void swap(priority_queue& __q)
514 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
515 __is_nothrow_swappable<value_compare>::value);
518 template <class _Tp, class _Container, class _Compare>
520 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
521 const container_type& __c)
525 _VSTD::make_heap(c.begin(), c.end(), comp);
528 #ifndef _LIBCPP_CXX03_LANG
530 template <class _Tp, class _Container, class _Compare>
532 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
533 container_type&& __c)
534 : c(_VSTD::move(__c)),
537 _VSTD::make_heap(c.begin(), c.end(), comp);
540 #endif // _LIBCPP_CXX03_LANG
542 template <class _Tp, class _Container, class _Compare>
543 template <class _InputIter>
545 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
546 const value_compare& __comp)
550 _VSTD::make_heap(c.begin(), c.end(), comp);
553 template <class _Tp, class _Container, class _Compare>
554 template <class _InputIter>
556 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
557 const value_compare& __comp,
558 const container_type& __c)
562 c.insert(c.end(), __f, __l);
563 _VSTD::make_heap(c.begin(), c.end(), comp);
566 #ifndef _LIBCPP_CXX03_LANG
568 template <class _Tp, class _Container, class _Compare>
569 template <class _InputIter>
571 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
572 const value_compare& __comp,
573 container_type&& __c)
574 : c(_VSTD::move(__c)),
577 c.insert(c.end(), __f, __l);
578 _VSTD::make_heap(c.begin(), c.end(), comp);
581 #endif // _LIBCPP_CXX03_LANG
583 template <class _Tp, class _Container, class _Compare>
584 template <class _Alloc>
586 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
587 typename enable_if<uses_allocator<container_type,
588 _Alloc>::value>::type*)
593 template <class _Tp, class _Container, class _Compare>
594 template <class _Alloc>
596 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
598 typename enable_if<uses_allocator<container_type,
599 _Alloc>::value>::type*)
605 template <class _Tp, class _Container, class _Compare>
606 template <class _Alloc>
608 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
609 const container_type& __c,
611 typename enable_if<uses_allocator<container_type,
612 _Alloc>::value>::type*)
616 _VSTD::make_heap(c.begin(), c.end(), comp);
619 template <class _Tp, class _Container, class _Compare>
620 template <class _Alloc>
622 priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
624 typename enable_if<uses_allocator<container_type,
625 _Alloc>::value>::type*)
629 _VSTD::make_heap(c.begin(), c.end(), comp);
632 #ifndef _LIBCPP_CXX03_LANG
634 template <class _Tp, class _Container, class _Compare>
635 template <class _Alloc>
637 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
638 container_type&& __c,
640 typename enable_if<uses_allocator<container_type,
641 _Alloc>::value>::type*)
642 : c(_VSTD::move(__c), __a),
645 _VSTD::make_heap(c.begin(), c.end(), comp);
648 template <class _Tp, class _Container, class _Compare>
649 template <class _Alloc>
651 priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
653 typename enable_if<uses_allocator<container_type,
654 _Alloc>::value>::type*)
655 : c(_VSTD::move(__q.c), __a),
656 comp(_VSTD::move(__q.comp))
658 _VSTD::make_heap(c.begin(), c.end(), comp);
661 #endif // _LIBCPP_CXX03_LANG
663 template <class _Tp, class _Container, class _Compare>
666 priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
669 _VSTD::push_heap(c.begin(), c.end(), comp);
672 #ifndef _LIBCPP_CXX03_LANG
674 template <class _Tp, class _Container, class _Compare>
677 priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
679 c.push_back(_VSTD::move(__v));
680 _VSTD::push_heap(c.begin(), c.end(), comp);
683 template <class _Tp, class _Container, class _Compare>
684 template <class... _Args>
687 priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
689 c.emplace_back(_VSTD::forward<_Args>(__args)...);
690 _VSTD::push_heap(c.begin(), c.end(), comp);
693 #endif // _LIBCPP_CXX03_LANG
695 template <class _Tp, class _Container, class _Compare>
698 priority_queue<_Tp, _Container, _Compare>::pop()
700 _VSTD::pop_heap(c.begin(), c.end(), comp);
704 template <class _Tp, class _Container, class _Compare>
707 priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
708 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
709 __is_nothrow_swappable<value_compare>::value)
713 swap(comp, __q.comp);
716 template <class _Tp, class _Container, class _Compare>
717 inline _LIBCPP_INLINE_VISIBILITY
719 __is_swappable<_Container>::value
720 && __is_swappable<_Compare>::value,
723 swap(priority_queue<_Tp, _Container, _Compare>& __x,
724 priority_queue<_Tp, _Container, _Compare>& __y)
725 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
730 template <class _Tp, class _Container, class _Compare, class _Alloc>
731 struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
732 : public uses_allocator<_Container, _Alloc>
736 _LIBCPP_END_NAMESPACE_STD
738 #endif // _LIBCPP_QUEUE