61#if __cplusplus >= 201103L
62# include <bits/uses_allocator.h>
65namespace std _GLIBCXX_VISIBILITY(default)
67_GLIBCXX_BEGIN_NAMESPACE_VERSION
95 template<
typename _Tp,
typename _Sequence = deque<_Tp> >
98#ifdef _GLIBCXX_CONCEPT_CHECKS
100 typedef typename _Sequence::value_type _Sequence_value_type;
101# if __cplusplus < 201103L
102 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
104 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
105 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
106 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
109 template<
typename _Tp1,
typename _Seq1>
113 template<
typename _Tp1,
typename _Seq1>
117#if __cpp_lib_three_way_comparison
118 template<
typename _Tp1, three_way_comparable _Seq1>
123#if __cplusplus >= 201103L
124 template<
typename _Alloc>
125 using _Uses =
typename
128#if __cplusplus >= 201703L
133 "value_type must be the same as the underlying container");
138 typedef typename _Sequence::value_type value_type;
139 typedef typename _Sequence::reference reference;
140 typedef typename _Sequence::const_reference const_reference;
141 typedef typename _Sequence::size_type size_type;
142 typedef _Sequence container_type;
159#if __cplusplus < 201103L
161 queue(
const _Sequence& __c = _Sequence())
164 template<
typename _Seq = _Sequence,
typename _Requires =
typename
170 queue(
const _Sequence& __c)
174 queue(_Sequence&& __c)
177 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
179 queue(
const _Alloc& __a)
182 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
183 queue(
const _Sequence& __c,
const _Alloc& __a)
186 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
187 queue(_Sequence&& __c,
const _Alloc& __a)
190 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
194 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
199#ifdef __glibcxx_adaptor_iterator_pair_constructor
200 template<
typename _InputIterator,
201 typename = _RequireInputIter<_InputIterator>>
202 queue(_InputIterator __first, _InputIterator __last)
203 :
c(__first, __last) { }
205 template<
typename _InputIterator,
typename _Alloc,
206 typename = _RequireInputIter<_InputIterator>,
207 typename = _Uses<_Alloc>>
208 queue(_InputIterator __first, _InputIterator __last,
const _Alloc& __a)
209 :
c(__first, __last, __a) { }
215 _GLIBCXX_NODISCARD
bool
217 {
return c.empty(); }
233 __glibcxx_requires_nonempty();
245 __glibcxx_requires_nonempty();
257 __glibcxx_requires_nonempty();
269 __glibcxx_requires_nonempty();
284 {
c.push_back(__x); }
286#if __cplusplus >= 201103L
288 push(value_type&& __x)
291#if __cplusplus > 201402L
292 template<
typename... _Args>
294 emplace(_Args&&... __args)
295 {
return c.emplace_back(std::forward<_Args>(__args)...); }
297 template<
typename... _Args>
299 emplace(_Args&&... __args)
300 {
c.emplace_back(std::forward<_Args>(__args)...); }
318 __glibcxx_requires_nonempty();
322#if __cplusplus >= 201103L
325#if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
326 noexcept(__is_nothrow_swappable<_Sequence>::value)
328 noexcept(__is_nothrow_swappable<_Tp>::value)
337#if __cpp_deduction_guides >= 201606
338 template<
typename _Container,
339 typename = _RequireNotAllocator<_Container>>
340 queue(_Container) -> queue<typename _Container::value_type, _Container>;
342 template<
typename _Container,
typename _Allocator,
343 typename = _RequireNotAllocator<_Container>>
344 queue(_Container, _Allocator)
345 -> queue<typename _Container::value_type, _Container>;
347#ifdef __glibcxx_adaptor_iterator_pair_constructor
348 template<
typename _InputIterator,
350 =
typename iterator_traits<_InputIterator>::value_type,
351 typename = _RequireInputIter<_InputIterator>>
352 queue(_InputIterator, _InputIterator) -> queue<_ValT>;
354 template<
typename _InputIterator,
typename _Allocator,
356 =
typename iterator_traits<_InputIterator>::value_type,
357 typename = _RequireInputIter<_InputIterator>,
358 typename = _RequireAllocator<_Allocator>>
359 queue(_InputIterator, _InputIterator, _Allocator)
360 -> queue<_ValT, deque<_ValT, _Allocator>>;
375 template<
typename _Tp,
typename _Seq>
379 {
return __x.
c == __y.
c; }
394 template<
typename _Tp,
typename _Seq>
398 {
return __x.
c < __y.
c; }
401 template<
typename _Tp,
typename _Seq>
405 {
return !(__x == __y); }
408 template<
typename _Tp,
typename _Seq>
412 {
return __y < __x; }
415 template<
typename _Tp,
typename _Seq>
419 {
return !(__y < __x); }
422 template<
typename _Tp,
typename _Seq>
426 {
return !(__x < __y); }
428#if __cpp_lib_three_way_comparison
429 template<
typename _Tp, three_way_comparable _Seq>
431 inline compare_three_way_result_t<_Seq>
432 operator<=>(
const queue<_Tp, _Seq>& __x,
const queue<_Tp, _Seq>& __y)
433 {
return __x.c <=> __y.c; }
436#if __cplusplus >= 201103L
437 template<
typename _Tp,
typename _Seq>
439#if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
441 typename enable_if<__is_swappable<_Seq>::value>::type
445 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
446 noexcept(
noexcept(__x.swap(__y)))
449 template<
typename _Tp,
typename _Seq,
typename _Alloc>
450 struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
451 :
public uses_allocator<_Seq, _Alloc>::type { };
494 template<
typename _Tp,
typename _Sequence = vector<_Tp>,
495 typename _Compare = less<
typename _Sequence::value_type> >
498#ifdef _GLIBCXX_CONCEPT_CHECKS
500 typedef typename _Sequence::value_type _Sequence_value_type;
501# if __cplusplus < 201103L
502 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
504 __glibcxx_class_requires(_Sequence, _SequenceConcept)
505 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
506 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
507 __glibcxx_class_requires4(_Compare,
bool, _Tp, _Tp,
508 _BinaryFunctionConcept)
511#if __cplusplus >= 201103L
512 template<
typename _Alloc>
513 using _Uses =
typename
516#if __cplusplus >= 201703L
521 "value_type must be the same as the underlying container");
526 typedef typename _Sequence::value_type value_type;
527 typedef typename _Sequence::reference reference;
528 typedef typename _Sequence::const_reference const_reference;
529 typedef typename _Sequence::size_type size_type;
530 typedef _Sequence container_type;
533 typedef _Compare value_compare;
544#if __cplusplus < 201103L
547 const _Sequence& __s = _Sequence())
549 { std::make_heap(c.begin(), c.end(), comp); }
551 template<
typename _Seq = _Sequence,
typename _Requires =
typename
560 { std::make_heap(c.begin(), c.end(), comp); }
563 priority_queue(
const _Compare& __x, _Sequence&& __s = _Sequence())
565 { std::make_heap(c.begin(), c.end(), comp); }
567 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
572 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
574 : c(__a), comp(__x) { }
578 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
581 : c(__c, __a), comp(__x)
582 { std::make_heap(c.begin(), c.end(), comp); }
584 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
585 priority_queue(
const _Compare& __x, _Sequence&& __c,
const _Alloc& __a)
586 : c(
std::
move(__c), __a), comp(__x)
587 { std::make_heap(c.begin(), c.end(), comp); }
589 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
591 : c(__q.c, __a), comp(__q.comp) { }
593 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
613#if __cplusplus < 201103L
614 template<
typename _InputIterator>
616 const _Compare& __x = _Compare(),
617 const _Sequence& __s = _Sequence())
620 __glibcxx_requires_valid_range(__first, __last);
621 c.insert(c.end(), __first, __last);
622 std::make_heap(c.begin(), c.end(), comp);
627 template<
typename _InputIterator,
628 typename = std::_RequireInputIter<_InputIterator>>
630 const _Compare& __x = _Compare())
631 : c(__first, __last), comp(__x)
632 { std::make_heap(c.begin(), c.end(), comp); }
636 template<
typename _InputIterator,
637 typename = std::_RequireInputIter<_InputIterator>>
639 const _Compare& __x,
const _Sequence& __s)
642 __glibcxx_requires_valid_range(__first, __last);
643 c.insert(c.end(), __first, __last);
644 std::make_heap(c.begin(), c.end(), comp);
647 template<
typename _InputIterator,
648 typename = std::_RequireInputIter<_InputIterator>>
650 const _Compare& __x, _Sequence&& __s)
653 __glibcxx_requires_valid_range(__first, __last);
654 c.insert(c.end(), __first, __last);
655 std::make_heap(c.begin(), c.end(), comp);
660 template<
typename _InputIterator,
typename _Alloc,
661 typename = std::_RequireInputIter<_InputIterator>,
662 typename _Requires = _Uses<_Alloc>>
664 const _Alloc& __alloc)
665 : c(__first, __last, __alloc), comp()
666 { std::make_heap(c.begin(), c.end(), comp); }
668 template<
typename _InputIterator,
typename _Alloc,
669 typename = std::_RequireInputIter<_InputIterator>,
670 typename _Requires = _Uses<_Alloc>>
672 const _Compare& __x,
const _Alloc& __alloc)
673 : c(__first, __last, __alloc), comp(__x)
674 { std::make_heap(c.begin(), c.end(), comp); }
676 template<
typename _InputIterator,
typename _Alloc,
677 typename = std::_RequireInputIter<_InputIterator>,
678 typename _Requires = _Uses<_Alloc>>
680 const _Compare& __x,
const _Sequence& __s,
681 const _Alloc& __alloc)
682 : c(__s, __alloc), comp(__x)
684 __glibcxx_requires_valid_range(__first, __last);
685 c.insert(c.end(), __first, __last);
686 std::make_heap(c.begin(), c.end(), comp);
689 template<
typename _InputIterator,
typename _Alloc,
690 typename _Requires = _Uses<_Alloc>>
692 const _Compare& __x, _Sequence&& __s,
693 const _Alloc& __alloc)
694 : c(
std::
move(__s), __alloc), comp(__x)
696 __glibcxx_requires_valid_range(__first, __last);
697 c.insert(c.end(), __first, __last);
698 std::make_heap(c.begin(), c.end(), comp);
705 _GLIBCXX_NODISCARD
bool
707 {
return c.empty(); }
723 __glibcxx_requires_nonempty();
739 std::push_heap(c.begin(), c.end(), comp);
742#if __cplusplus >= 201103L
744 push(value_type&& __x)
747 std::push_heap(c.begin(), c.end(), comp);
750 template<
typename... _Args>
752 emplace(_Args&&... __args)
754 c.emplace_back(std::forward<_Args>(__args)...);
755 std::push_heap(c.begin(), c.end(), comp);
773 __glibcxx_requires_nonempty();
774 std::pop_heap(c.begin(), c.end(), comp);
778#if __cplusplus >= 201103L
782#if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
783 __is_nothrow_swappable<_Sequence>,
785 __is_nothrow_swappable<_Tp>,
787 __is_nothrow_swappable<_Compare>
792 swap(comp, __pq.comp);
797#if __cpp_deduction_guides >= 201606
798 template<
typename _Compare,
typename _Container,
799 typename = _RequireNotAllocator<_Compare>,
800 typename = _RequireNotAllocator<_Container>>
801 priority_queue(_Compare, _Container)
802 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
804 template<
typename _InputIterator,
typename _ValT
805 =
typename iterator_traits<_InputIterator>::value_type,
806 typename _Compare = less<_ValT>,
807 typename _Container = vector<_ValT>,
808 typename = _RequireInputIter<_InputIterator>,
809 typename = _RequireNotAllocator<_Compare>,
810 typename = _RequireNotAllocator<_Container>>
811 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
812 _Container = _Container())
813 -> priority_queue<_ValT, _Container, _Compare>;
815 template<
typename _Compare,
typename _Container,
typename _Allocator,
816 typename = _RequireNotAllocator<_Compare>,
817 typename = _RequireNotAllocator<_Container>>
818 priority_queue(_Compare, _Container, _Allocator)
819 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
824#if __cplusplus >= 201103L
825 template<
typename _Tp,
typename _Sequence,
typename _Compare>
827#if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
829 typename enable_if<__and_<__is_swappable<_Sequence>,
830 __is_swappable<_Compare>>::value>::type
834 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
835 priority_queue<_Tp, _Sequence, _Compare>& __y)
836 noexcept(
noexcept(__x.swap(__y)))
839 template<
typename _Tp,
typename _Sequence,
typename _Compare,
841 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
842 :
public uses_allocator<_Sequence, _Alloc>::type { };
845_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
typename __detail::__cmp3way_res_impl< _Tp, _Up >::type compare_three_way_result_t
[cmp.result], result of three-way comparison
Define a member typedef type only if a boolean constant is true.
A standard container giving FIFO behavior.
void push(const value_type &__x)
Add data to the end of the queue.
_Sequence c
c is the underlying container.
const_reference back() const
void pop()
Removes first element.
queue()
Default constructor creates no elements.
const_reference front() const
A standard container automatically sorting its contents.
void pop()
Removes first element.
const_reference top() const
priority_queue(_InputIterator __first, _InputIterator __last, const _Compare &__x=_Compare())
Builds a queue from a range.
void push(const value_type &__x)
Add data to the queue.
priority_queue()
Default constructor creates no elements.