57 #define _STL_QUEUE_H 1
61 #if __cplusplus >= 201103L
62 # include <bits/uses_allocator.h>
64 #if __glibcxx_containers_ranges
69 namespace std _GLIBCXX_VISIBILITY(default)
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
73 #if __glibcxx_format_ranges
74 template<
typename,
typename>
class formatter;
103 template<
typename _Tp,
typename _Sequence = deque<_Tp> >
106 #ifdef _GLIBCXX_CONCEPT_CHECKS
108 typedef typename _Sequence::value_type _Sequence_value_type;
109 # if __cplusplus < 201103L
110 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
112 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
113 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
114 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
117 template<
typename _Tp1,
typename _Seq1>
121 template<
typename _Tp1,
typename _Seq1>
125 #if __cpp_lib_three_way_comparison
126 template<
typename _Tp1, three_way_comparable _Seq1>
131 #if __cplusplus >= 201103L
132 template<
typename _Alloc>
133 using _Uses =
typename
136 #if __cplusplus >= 201703L
141 "value_type must be the same as the underlying container");
146 typedef typename _Sequence::value_type value_type;
147 typedef typename _Sequence::reference reference;
148 typedef typename _Sequence::const_reference const_reference;
149 typedef typename _Sequence::size_type size_type;
150 typedef _Sequence container_type;
167 #if __cplusplus < 201103L
169 queue(
const _Sequence& __c = _Sequence())
172 template<
typename _Seq = _Sequence,
typename _Requires =
typename
178 queue(
const _Sequence& __c)
182 queue(_Sequence&& __c)
185 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
187 queue(
const _Alloc& __a)
190 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
191 queue(
const _Sequence& __c,
const _Alloc& __a)
194 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
195 queue(_Sequence&& __c,
const _Alloc& __a)
198 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
202 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
207 #ifdef __glibcxx_adaptor_iterator_pair_constructor
208 template<
typename _InputIterator,
209 typename = _RequireInputIter<_InputIterator>>
210 queue(_InputIterator __first, _InputIterator __last)
211 :
c(__first, __last) { }
213 template<
typename _InputIterator,
typename _Alloc,
214 typename = _RequireInputIter<_InputIterator>,
215 typename = _Uses<_Alloc>>
216 queue(_InputIterator __first, _InputIterator __last,
const _Alloc& __a)
217 :
c(__first, __last, __a) { }
220 #if __glibcxx_containers_ranges
225 template<__detail::__container_compatible_range<_Tp> _Rg>
226 queue(from_range_t, _Rg&& __rg)
227 :
c(ranges::to<_Sequence>(
std::
forward<_Rg>(__rg)))
234 template<__detail::__container_compatible_range<_Tp> _Rg,
236 queue(from_range_t, _Rg&& __rg,
const _Alloc& __a)
237 :
c(ranges::to<_Sequence>(
std::
forward<_Rg>(__rg), __a))
244 _GLIBCXX_NODISCARD
bool
246 {
return c.empty(); }
262 __glibcxx_requires_nonempty();
274 __glibcxx_requires_nonempty();
286 __glibcxx_requires_nonempty();
298 __glibcxx_requires_nonempty();
313 {
c.push_back(__x); }
315 #if __cplusplus >= 201103L
317 push(value_type&& __x)
320 #if __cplusplus > 201402L
321 template<
typename... _Args>
323 emplace(_Args&&... __args)
324 {
return c.emplace_back(std::forward<_Args>(__args)...); }
326 template<
typename... _Args>
328 emplace(_Args&&... __args)
329 {
c.emplace_back(std::forward<_Args>(__args)...); }
333 #if __glibcxx_containers_ranges
334 template<__detail::__container_compatible_range<_Tp> _Rg>
336 push_range(_Rg&& __rg)
338 if constexpr (requires {
c.append_range(std::forward<_Rg>(__rg)); })
339 c.append_range(std::forward<_Rg>(__rg));
359 __glibcxx_requires_nonempty();
363 #if __cplusplus >= 201103L
366 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
367 noexcept(__is_nothrow_swappable<_Sequence>::value)
369 noexcept(__is_nothrow_swappable<_Tp>::value)
377 #if __glibcxx_format_ranges
378 friend class formatter<
queue<_Tp, _Sequence>, char>;
379 friend class formatter<
queue<_Tp, _Sequence>, wchar_t>;
383 #if __cpp_deduction_guides >= 201606
384 template<
typename _Container,
385 typename = _RequireNotAllocator<_Container>>
386 queue(_Container) -> queue<typename _Container::value_type, _Container>;
388 template<
typename _Container,
typename _Allocator,
389 typename = _RequireNotAllocator<_Container>>
390 queue(_Container, _Allocator)
391 -> queue<typename _Container::value_type, _Container>;
393 #ifdef __glibcxx_adaptor_iterator_pair_constructor
394 template<
typename _InputIterator,
396 =
typename iterator_traits<_InputIterator>::value_type,
397 typename = _RequireInputIter<_InputIterator>>
398 queue(_InputIterator, _InputIterator) -> queue<_ValT>;
400 template<
typename _InputIterator,
typename _Allocator,
402 =
typename iterator_traits<_InputIterator>::value_type,
403 typename = _RequireInputIter<_InputIterator>,
404 typename = _RequireAllocator<_Allocator>>
405 queue(_InputIterator, _InputIterator, _Allocator)
406 -> queue<_ValT, deque<_ValT, _Allocator>>;
409 #if __glibcxx_containers_ranges
410 template<ranges::input_range _Rg>
411 queue(from_range_t, _Rg&&) -> queue<ranges::range_value_t<_Rg>>;
413 template<ranges::input_range _Rg, __allocator_like _Alloc>
414 queue(from_range_t, _Rg&&, _Alloc)
415 -> queue<ranges::range_value_t<_Rg>,
416 deque<ranges::range_value_t<_Rg>, _Alloc>>;
431 template<
typename _Tp,
typename _Seq>
435 {
return __x.
c == __y.
c; }
450 template<
typename _Tp,
typename _Seq>
454 {
return __x.
c < __y.
c; }
457 template<
typename _Tp,
typename _Seq>
461 {
return !(__x == __y); }
464 template<
typename _Tp,
typename _Seq>
468 {
return __y < __x; }
471 template<
typename _Tp,
typename _Seq>
475 {
return !(__y < __x); }
478 template<
typename _Tp,
typename _Seq>
482 {
return !(__x < __y); }
484 #if __cpp_lib_three_way_comparison
485 template<
typename _Tp, three_way_comparable _Seq>
487 inline compare_three_way_result_t<_Seq>
488 operator<=>(
const queue<_Tp, _Seq>& __x,
const queue<_Tp, _Seq>& __y)
489 {
return __x.c <=> __y.c; }
492 #if __cplusplus >= 201103L
493 template<
typename _Tp,
typename _Seq>
495 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
497 typename enable_if<__is_swappable<_Seq>::value>::type
501 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
502 noexcept(noexcept(__x.swap(__y)))
505 template<
typename _Tp,
typename _Seq,
typename _Alloc>
506 struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
507 :
public uses_allocator<_Seq, _Alloc>::type { };
550 template<
typename _Tp,
typename _Sequence = vector<_Tp>,
551 typename _Compare = less<
typename _Sequence::value_type> >
554 #ifdef _GLIBCXX_CONCEPT_CHECKS
556 typedef typename _Sequence::value_type _Sequence_value_type;
557 # if __cplusplus < 201103L
558 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
560 __glibcxx_class_requires(_Sequence, _SequenceConcept)
561 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
562 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
563 __glibcxx_class_requires4(_Compare,
bool, _Tp, _Tp,
564 _BinaryFunctionConcept)
567 #if __cplusplus >= 201103L
568 template<
typename _Alloc>
569 using _Uses =
typename
572 #if __cplusplus >= 201703L
577 "value_type must be the same as the underlying container");
582 typedef typename _Sequence::value_type value_type;
583 typedef typename _Sequence::reference reference;
584 typedef typename _Sequence::const_reference const_reference;
585 typedef typename _Sequence::size_type size_type;
586 typedef _Sequence container_type;
589 typedef _Compare value_compare;
600 #if __cplusplus < 201103L
603 const _Sequence& __s = _Sequence())
605 { std::make_heap(c.begin(), c.end(), comp); }
607 template<
typename _Seq = _Sequence,
typename _Requires =
typename
616 { std::make_heap(c.begin(), c.end(), comp); }
619 priority_queue(
const _Compare& __x, _Sequence&& __s = _Sequence())
621 { std::make_heap(c.begin(), c.end(), comp); }
627 noexcept(__and_<is_nothrow_move_constructible<_Sequence>,
628 is_nothrow_move_constructible<_Compare>>::value)
634 noexcept(__and_<is_nothrow_move_assignable<_Sequence>,
635 is_nothrow_move_assignable<_Compare>>::value)
643 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
648 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
650 : c(__a), comp(__x) { }
654 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
657 : c(__c, __a), comp(__x)
658 { std::make_heap(c.begin(), c.end(), comp); }
660 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
661 priority_queue(
const _Compare& __x, _Sequence&& __c,
const _Alloc& __a)
662 : c(
std::
move(__c), __a), comp(__x)
663 { std::make_heap(c.begin(), c.end(), comp); }
665 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
667 : c(__q.c, __a), comp(__q.comp) { }
669 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
689 #if __cplusplus < 201103L
690 template<
typename _InputIterator>
692 const _Compare& __x = _Compare(),
693 const _Sequence& __s = _Sequence())
696 __glibcxx_requires_valid_range(__first, __last);
697 c.insert(c.end(), __first, __last);
698 std::make_heap(c.begin(), c.end(), comp);
703 template<
typename _InputIterator,
704 typename = std::_RequireInputIter<_InputIterator>>
706 const _Compare& __x = _Compare())
707 : c(__first, __last), comp(__x)
708 { std::make_heap(c.begin(), c.end(), comp); }
712 template<
typename _InputIterator,
713 typename = std::_RequireInputIter<_InputIterator>>
715 const _Compare& __x,
const _Sequence& __s)
718 __glibcxx_requires_valid_range(__first, __last);
719 c.insert(c.end(), __first, __last);
720 std::make_heap(c.begin(), c.end(), comp);
723 template<
typename _InputIterator,
724 typename = std::_RequireInputIter<_InputIterator>>
726 const _Compare& __x, _Sequence&& __s)
729 __glibcxx_requires_valid_range(__first, __last);
730 c.insert(c.end(), __first, __last);
731 std::make_heap(c.begin(), c.end(), comp);
736 template<
typename _InputIterator,
typename _Alloc,
737 typename = std::_RequireInputIter<_InputIterator>,
738 typename _Requires = _Uses<_Alloc>>
740 const _Alloc& __alloc)
741 : c(__first, __last, __alloc), comp()
742 { std::make_heap(c.begin(), c.end(), comp); }
744 template<
typename _InputIterator,
typename _Alloc,
745 typename = std::_RequireInputIter<_InputIterator>,
746 typename _Requires = _Uses<_Alloc>>
748 const _Compare& __x,
const _Alloc& __alloc)
749 : c(__first, __last, __alloc), comp(__x)
750 { std::make_heap(c.begin(), c.end(), comp); }
752 template<
typename _InputIterator,
typename _Alloc,
753 typename = std::_RequireInputIter<_InputIterator>,
754 typename _Requires = _Uses<_Alloc>>
756 const _Compare& __x,
const _Sequence& __s,
757 const _Alloc& __alloc)
758 : c(__s, __alloc), comp(__x)
760 __glibcxx_requires_valid_range(__first, __last);
761 c.insert(c.end(), __first, __last);
762 std::make_heap(c.begin(), c.end(), comp);
765 template<
typename _InputIterator,
typename _Alloc,
766 typename _Requires = _Uses<_Alloc>>
768 const _Compare& __x, _Sequence&& __s,
769 const _Alloc& __alloc)
770 : c(
std::
move(__s), __alloc), comp(__x)
772 __glibcxx_requires_valid_range(__first, __last);
773 c.insert(c.end(), __first, __last);
774 std::make_heap(c.begin(), c.end(), comp);
778 #if __glibcxx_containers_ranges
785 template<__detail::__container_compatible_range<_Tp> _Rg>
787 const _Compare& __x = _Compare())
788 : c(ranges::to<_Sequence>(
std::
forward<_Rg>(__rg))), comp(__x)
789 { std::make_heap(c.begin(), c.end(), comp); }
791 template<__detail::__container_compatible_range<_Tp> _Rg,
typename _Alloc>
794 : c(ranges::to<_Sequence>(
std::
forward<_Rg>(__rg), __a)), comp(__x)
795 { std::make_heap(c.begin(), c.end(), comp); }
797 template<__detail::__container_compatible_range<_Tp> _Rg,
typename _Alloc>
799 : c(ranges::to<_Sequence>(
std::
forward<_Rg>(__rg), __a)), comp()
800 { std::make_heap(c.begin(), c.end(), comp); }
807 _GLIBCXX_NODISCARD
bool
809 {
return c.empty(); }
825 __glibcxx_requires_nonempty();
841 std::push_heap(c.begin(), c.end(), comp);
844 #if __cplusplus >= 201103L
846 push(value_type&& __x)
849 std::push_heap(c.begin(), c.end(), comp);
852 template<
typename... _Args>
854 emplace(_Args&&... __args)
856 c.emplace_back(std::forward<_Args>(__args)...);
857 std::push_heap(c.begin(), c.end(), comp);
861 #if __glibcxx_containers_ranges
862 template<__detail::__container_compatible_range<_Tp> _Rg>
864 push_range(_Rg&& __rg)
866 if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); })
867 c.append_range(std::forward<_Rg>(__rg));
870 std::make_heap(c.begin(), c.end(), comp);
888 __glibcxx_requires_nonempty();
889 std::pop_heap(c.begin(), c.end(), comp);
893 #if __cplusplus >= 201103L
897 #
if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
898 __is_nothrow_swappable<_Sequence>,
900 __is_nothrow_swappable<_Tp>,
902 __is_nothrow_swappable<_Compare>
907 swap(comp, __pq.comp);
911 #if __glibcxx_format_ranges
912 friend class formatter<
priority_queue<_Tp, _Sequence, _Compare>, char>;
913 friend class formatter<
priority_queue<_Tp, _Sequence, _Compare>, wchar_t>;
917 #if __cpp_deduction_guides >= 201606
918 template<
typename _Compare,
typename _Container,
919 typename = _RequireNotAllocator<_Compare>,
920 typename = _RequireNotAllocator<_Container>>
921 priority_queue(_Compare, _Container)
922 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
924 template<
typename _InputIterator,
typename _ValT
925 =
typename iterator_traits<_InputIterator>::value_type,
926 typename _Compare = less<_ValT>,
927 typename _Container = vector<_ValT>,
928 typename = _RequireInputIter<_InputIterator>,
929 typename = _RequireNotAllocator<_Compare>,
930 typename = _RequireNotAllocator<_Container>>
931 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
932 _Container = _Container())
933 -> priority_queue<_ValT, _Container, _Compare>;
935 template<
typename _Compare,
typename _Container,
typename _Allocator,
936 typename = _RequireNotAllocator<_Compare>,
937 typename = _RequireNotAllocator<_Container>>
938 priority_queue(_Compare, _Container, _Allocator)
939 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
941 #if __glibcxx_containers_ranges
942 template<ranges::input_range _Rg,
943 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
945 priority_queue(from_range_t, _Rg&&, _Compare = _Compare(),
947 -> priority_queue<ranges::range_value_t<_Rg>,
948 vector<ranges::range_value_t<_Rg>, _Alloc>,
951 template<ranges::input_range _Rg, __allocator_like _Alloc>
952 priority_queue(from_range_t, _Rg&&, _Alloc)
953 -> priority_queue<ranges::range_value_t<_Rg>,
954 vector<ranges::range_value_t<_Rg>, _Alloc>>;
960 #if __cplusplus >= 201103L
961 template<
typename _Tp,
typename _Sequence,
typename _Compare>
963 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
965 typename enable_if<__and_<__is_swappable<_Sequence>,
966 __is_swappable<_Compare>>::value>::type
970 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
971 priority_queue<_Tp, _Sequence, _Compare>& __y)
972 noexcept(noexcept(__x.swap(__y)))
975 template<
typename _Tp,
typename _Sequence,
typename _Compare,
977 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
978 :
public uses_allocator<_Sequence, _Alloc>::type { };
981 _GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr back_insert_iterator< _Container > back_inserter(_Container &__x)
ISO C++ entities toplevel namespace is std.
bool operator>(const queue< _Tp, _Seq > &__x, const queue< _Tp, _Seq > &__y)
Based on operator<.
bool operator==(const queue< _Tp, _Seq > &__x, const queue< _Tp, _Seq > &__y)
Queue equality comparison.
bool operator<(const queue< _Tp, _Seq > &__x, const queue< _Tp, _Seq > &__y)
Queue ordering relation.
bool operator<=(const queue< _Tp, _Seq > &__x, const queue< _Tp, _Seq > &__y)
Based on operator<.
bool operator!=(const queue< _Tp, _Seq > &__x, const queue< _Tp, _Seq > &__y)
Based on operator==.
bool operator>=(const queue< _Tp, _Seq > &__x, const queue< _Tp, _Seq > &__y)
Based on operator<.
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.
The standard allocator, as per C++03 [20.4.1].
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.