57 #define _STL_QUEUE_H 1 61 #if __cplusplus >= 201103L 62 # include <bits/uses_allocator.h> 65 namespace 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>>
198 #if __cplusplus > 202002L 199 #define __cpp_lib_adaptor_iterator_pair_constructor 202106L 201 template<
typename _InputIterator,
202 typename = _RequireInputIter<_InputIterator>>
203 queue(_InputIterator __first, _InputIterator __last)
204 :
c(__first, __last) { }
206 template<
typename _InputIterator,
typename _Alloc,
207 typename = _RequireInputIter<_InputIterator>,
208 typename = _Uses<_Alloc>>
209 queue(_InputIterator __first, _InputIterator __last,
const _Alloc& __a)
210 :
c(__first, __last, __a) { }
217 _GLIBCXX_NODISCARD
bool 219 {
return c.empty(); }
235 __glibcxx_requires_nonempty();
247 __glibcxx_requires_nonempty();
259 __glibcxx_requires_nonempty();
271 __glibcxx_requires_nonempty();
286 {
c.push_back(__x); }
288 #if __cplusplus >= 201103L 290 push(value_type&& __x)
293 #if __cplusplus > 201402L 294 template<
typename... _Args>
296 emplace(_Args&&... __args)
297 {
return c.emplace_back(std::forward<_Args>(__args)...); }
299 template<
typename... _Args>
301 emplace(_Args&&... __args)
302 {
c.emplace_back(std::forward<_Args>(__args)...); }
320 __glibcxx_requires_nonempty();
324 #if __cplusplus >= 201103L 327 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 328 noexcept(__is_nothrow_swappable<_Sequence>::value)
330 noexcept(__is_nothrow_swappable<_Tp>::value)
336 #endif // __cplusplus >= 201103L 339 #if __cpp_deduction_guides >= 201606 340 template<
typename _Container,
341 typename = _RequireNotAllocator<_Container>>
342 queue(_Container) -> queue<typename _Container::value_type, _Container>;
344 template<
typename _Container,
typename _Allocator,
345 typename = _RequireNotAllocator<_Container>>
346 queue(_Container, _Allocator)
347 -> queue<typename _Container::value_type, _Container>;
349 #ifdef __cpp_lib_adaptor_iterator_pair_constructor 350 template<
typename _InputIterator,
352 =
typename iterator_traits<_InputIterator>::value_type,
353 typename = _RequireInputIter<_InputIterator>>
354 queue(_InputIterator, _InputIterator) -> queue<_ValT>;
356 template<
typename _InputIterator,
typename _Allocator,
358 =
typename iterator_traits<_InputIterator>::value_type,
359 typename = _RequireInputIter<_InputIterator>,
360 typename = _RequireAllocator<_Allocator>>
361 queue(_InputIterator, _InputIterator, _Allocator)
362 -> queue<_ValT, deque<_ValT, _Allocator>>;
377 template<
typename _Tp,
typename _Seq>
381 {
return __x.
c == __y.
c; }
396 template<
typename _Tp,
typename _Seq>
400 {
return __x.
c < __y.c; }
403 template<
typename _Tp,
typename _Seq>
407 {
return !(__x == __y); }
410 template<
typename _Tp,
typename _Seq>
414 {
return __y < __x; }
417 template<
typename _Tp,
typename _Seq>
421 {
return !(__y < __x); }
424 template<
typename _Tp,
typename _Seq>
428 {
return !(__x < __y); }
430 #if __cpp_lib_three_way_comparison 431 template<
typename _Tp, three_way_comparable _Seq>
433 inline compare_three_way_result_t<_Seq>
434 operator<=>(
const queue<_Tp, _Seq>& __x,
const queue<_Tp, _Seq>& __y)
435 {
return __x.c <=> __y.c; }
438 #if __cplusplus >= 201103L 439 template<
typename _Tp,
typename _Seq>
441 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 443 typename enable_if<__is_swappable<_Seq>::value>::type
447 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
448 noexcept(noexcept(__x.swap(__y)))
451 template<
typename _Tp,
typename _Seq,
typename _Alloc>
452 struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
453 :
public uses_allocator<_Seq, _Alloc>::type { };
454 #endif // __cplusplus >= 201103L 496 template<
typename _Tp,
typename _Sequence = vector<_Tp>,
497 typename _Compare = less<
typename _Sequence::value_type> >
500 #ifdef _GLIBCXX_CONCEPT_CHECKS 502 typedef typename _Sequence::value_type _Sequence_value_type;
503 # if __cplusplus < 201103L 504 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
506 __glibcxx_class_requires(_Sequence, _SequenceConcept)
507 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
508 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
509 __glibcxx_class_requires4(_Compare,
bool, _Tp, _Tp,
510 _BinaryFunctionConcept)
513 #if __cplusplus >= 201103L 514 template<
typename _Alloc>
515 using _Uses =
typename 518 #if __cplusplus >= 201703L 523 "value_type must be the same as the underlying container");
528 typedef typename _Sequence::value_type value_type;
529 typedef typename _Sequence::reference reference;
530 typedef typename _Sequence::const_reference const_reference;
531 typedef typename _Sequence::size_type size_type;
532 typedef _Sequence container_type;
535 typedef _Compare value_compare;
546 #if __cplusplus < 201103L 549 const _Sequence& __s = _Sequence())
553 template<
typename _Seq = _Sequence,
typename _Requires =
typename 565 priority_queue(
const _Compare& __x, _Sequence&& __s = _Sequence())
567 { std::make_heap(c.begin(), c.end(), comp); }
569 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
574 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
576 : c(__a), comp(__x) { }
580 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
583 : c(__c, __a), comp(__x)
586 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
587 priority_queue(
const _Compare& __x, _Sequence&& __c,
const _Alloc& __a)
588 : c(
std::
move(__c), __a), comp(__x)
591 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
593 : c(__q.c, __a), comp(__q.comp) { }
595 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
615 #if __cplusplus < 201103L 616 template<
typename _InputIterator>
618 const _Compare& __x = _Compare(),
619 const _Sequence& __s = _Sequence())
622 __glibcxx_requires_valid_range(__first, __last);
623 c.insert(c.end(), __first, __last);
629 template<
typename _InputIterator,
630 typename = std::_RequireInputIter<_InputIterator>>
632 const _Compare& __x = _Compare())
633 : c(__first, __last), comp(__x)
638 template<
typename _InputIterator,
639 typename = std::_RequireInputIter<_InputIterator>>
641 const _Compare& __x,
const _Sequence& __s)
644 __glibcxx_requires_valid_range(__first, __last);
645 c.insert(c.end(), __first, __last);
649 template<
typename _InputIterator,
650 typename = std::_RequireInputIter<_InputIterator>>
652 const _Compare& __x, _Sequence&& __s)
655 __glibcxx_requires_valid_range(__first, __last);
656 c.insert(c.end(), __first, __last);
657 std::make_heap(c.begin(), c.end(), comp);
662 template<
typename _InputIterator,
typename _Alloc,
663 typename = std::_RequireInputIter<_InputIterator>,
664 typename _Requires = _Uses<_Alloc>>
666 const _Alloc& __alloc)
667 : c(__first, __last, __alloc), comp()
670 template<
typename _InputIterator,
typename _Alloc,
671 typename = std::_RequireInputIter<_InputIterator>,
672 typename _Requires = _Uses<_Alloc>>
674 const _Compare& __x,
const _Alloc& __alloc)
675 : c(__first, __last, __alloc), comp(__x)
678 template<
typename _InputIterator,
typename _Alloc,
679 typename = std::_RequireInputIter<_InputIterator>,
680 typename _Requires = _Uses<_Alloc>>
682 const _Compare& __x,
const _Sequence& __s,
683 const _Alloc& __alloc)
684 : c(__s, __alloc), comp(__x)
686 __glibcxx_requires_valid_range(__first, __last);
687 c.insert(c.end(), __first, __last);
691 template<
typename _InputIterator,
typename _Alloc,
692 typename _Requires = _Uses<_Alloc>>
694 const _Compare& __x, _Sequence&& __s,
695 const _Alloc& __alloc)
696 : c(
std::
move(__s), __alloc), comp(__x)
698 __glibcxx_requires_valid_range(__first, __last);
699 c.insert(c.end(), __first, __last);
707 _GLIBCXX_NODISCARD
bool 709 {
return c.empty(); }
725 __glibcxx_requires_nonempty();
744 #if __cplusplus >= 201103L 746 push(value_type&& __x)
752 template<
typename... _Args>
754 emplace(_Args&&... __args)
756 c.emplace_back(std::forward<_Args>(__args)...);
757 std::push_heap(c.begin(), c.end(), comp);
775 __glibcxx_requires_nonempty();
780 #if __cplusplus >= 201103L 784 #
if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
785 __is_nothrow_swappable<_Sequence>,
787 __is_nothrow_swappable<_Tp>,
789 __is_nothrow_swappable<_Compare>
794 swap(comp, __pq.comp);
796 #endif // __cplusplus >= 201103L 799 #if __cpp_deduction_guides >= 201606 800 template<
typename _Compare,
typename _Container,
801 typename = _RequireNotAllocator<_Compare>,
802 typename = _RequireNotAllocator<_Container>>
803 priority_queue(_Compare, _Container)
804 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
806 template<
typename _InputIterator,
typename _ValT
807 =
typename iterator_traits<_InputIterator>::value_type,
808 typename _Compare = less<_ValT>,
809 typename _Container = vector<_ValT>,
810 typename = _RequireInputIter<_InputIterator>,
811 typename = _RequireNotAllocator<_Compare>,
812 typename = _RequireNotAllocator<_Container>>
813 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
814 _Container = _Container())
815 -> priority_queue<_ValT, _Container, _Compare>;
817 template<
typename _Compare,
typename _Container,
typename _Allocator,
818 typename = _RequireNotAllocator<_Compare>,
819 typename = _RequireNotAllocator<_Container>>
820 priority_queue(_Compare, _Container, _Allocator)
821 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
826 #if __cplusplus >= 201103L 827 template<
typename _Tp,
typename _Sequence,
typename _Compare>
829 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 831 typename enable_if<__and_<__is_swappable<_Sequence>,
832 __is_swappable<_Compare>>::value>::type
836 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
837 priority_queue<_Tp, _Sequence, _Compare>& __y)
838 noexcept(noexcept(__x.swap(__y)))
841 template<
typename _Tp,
typename _Sequence,
typename _Compare,
843 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
844 :
public uses_allocator<_Sequence, _Alloc>::type { };
845 #endif // __cplusplus >= 201103L 847 _GLIBCXX_END_NAMESPACE_VERSION
void pop()
Removes first element.
priority_queue(_InputIterator __first, _InputIterator __last, const _Compare &__x=_Compare())
Builds a queue from a range.
void pop()
Removes first element.
typename __detail::__cmp3way_res_impl< _Tp, _Up >::type compare_three_way_result_t
[cmp.result], result of three-way comparison
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
A standard container giving FIFO behavior.
Define a member typedef type only if a boolean constant is true.
A standard container automatically sorting its contents.
ISO C++ entities toplevel namespace is std.
const_reference front() const
const_reference top() const
queue()
Default constructor creates no elements.
const_reference back() const
constexpr void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Pop an element off a heap using comparison functor.
constexpr void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Push an element onto a heap using comparison functor.
void push(const value_type &__x)
Add data to the end of the queue.
_Sequence c
c is the underlying container.
priority_queue()
Default constructor creates no elements.
void push(const value_type &__x)
Add data to the queue.