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>>
199 #ifdef __glibcxx_adaptor_iterator_pair_constructor // C++ >= 23 && HOSTED 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__) // c++1z or gnu++11 326 noexcept(__is_nothrow_swappable<_Sequence>::value)
328 noexcept(__is_nothrow_swappable<_Tp>::value)
334 #endif // __cplusplus >= 201103L 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__) // c++1z or gnu++11 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 { };
452 #endif // __cplusplus >= 201103L 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())
551 template<
typename _Seq = _Sequence,
typename _Requires =
typename 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)
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)
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);
627 template<
typename _InputIterator,
628 typename = std::_RequireInputIter<_InputIterator>>
630 const _Compare& __x = _Compare())
631 : c(__first, __last), comp(__x)
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);
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()
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)
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);
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);
705 _GLIBCXX_NODISCARD
bool 707 {
return c.empty(); }
723 __glibcxx_requires_nonempty();
742 #if __cplusplus >= 201103L 744 push(value_type&& __x)
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();
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);
794 #endif // __cplusplus >= 201103L 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__) // c++1z or gnu++11 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 { };
843 #endif // __cplusplus >= 201103L 845 _GLIBCXX_END_NAMESPACE_VERSION
ISO C++ entities toplevel namespace is std.
void push(const value_type &__x)
Add data to the queue.
void pop()
Removes first element.
constexpr void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Push an element onto a heap using comparison functor.
constexpr void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Pop an element off a heap using comparison functor.
priority_queue()
Default constructor creates no elements.
_Sequence c
c is the underlying container.
A standard container giving FIFO behavior.
A standard container automatically sorting its contents.
queue()
Default constructor creates no elements.
const_reference front() const
const_reference back() const
void push(const value_type &__x)
Add data to the end of the queue.
priority_queue(_InputIterator __first, _InputIterator __last, const _Compare &__x=_Compare())
Builds a queue from a range.
Define a member typedef type only if a boolean constant is true.
const_reference top() const
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
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 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.