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 __cplusplus >= 201103L
118 template<
typename _Alloc>
119 using _Uses =
typename
124 typedef typename _Sequence::value_type value_type;
125 typedef typename _Sequence::reference reference;
126 typedef typename _Sequence::const_reference const_reference;
127 typedef typename _Sequence::size_type size_type;
128 typedef _Sequence container_type;
145 #if __cplusplus < 201103L
147 queue(
const _Sequence& __c = _Sequence())
150 template<
typename _Seq = _Sequence,
typename _Requires =
typename
156 queue(
const _Sequence& __c)
160 queue(_Sequence&& __c)
161 :
c(std::move(__c)) { }
163 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
165 queue(
const _Alloc& __a)
168 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
169 queue(
const _Sequence& __c,
const _Alloc& __a)
172 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
173 queue(_Sequence&& __c,
const _Alloc& __a)
174 :
c(std::move(__c), __a) { }
176 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
180 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
182 :
c(std::move(__q.
c), __a) { }
190 {
return c.empty(); }
204 __glibcxx_requires_nonempty();
215 __glibcxx_requires_nonempty();
226 __glibcxx_requires_nonempty();
237 __glibcxx_requires_nonempty();
252 {
c.push_back(__x); }
254 #if __cplusplus >= 201103L
256 push(value_type&& __x)
257 {
c.push_back(std::move(__x)); }
259 #if __cplusplus > 201402L
260 template<
typename... _Args>
262 emplace(_Args&&... __args)
263 {
return c.emplace_back(std::forward<_Args>(__args)...); }
265 template<
typename... _Args>
267 emplace(_Args&&... __args)
268 {
c.emplace_back(std::forward<_Args>(__args)...); }
286 __glibcxx_requires_nonempty();
290 #if __cplusplus >= 201103L
293 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
294 noexcept(__is_nothrow_swappable<_Sequence>::value)
296 noexcept(__is_nothrow_swappable<_Tp>::value)
302 #endif // __cplusplus >= 201103L
305 #if __cpp_deduction_guides >= 201606
306 template<
typename _Container,
307 typename = enable_if_t<!__is_allocator<_Container>::value>>
308 queue(_Container) -> queue<typename _Container::value_type, _Container>;
310 template<
typename _Container,
typename _Allocator,
311 typename = enable_if_t<!__is_allocator<_Container>::value>,
312 typename = enable_if_t<__is_allocator<_Allocator>::value>>
313 queue(_Container, _Allocator)
314 -> queue<typename _Container::value_type, _Container>;
328 template<
typename _Tp,
typename _Seq>
331 {
return __x.
c == __y.
c; }
346 template<
typename _Tp,
typename _Seq>
349 {
return __x.c < __y.c; }
352 template<
typename _Tp,
typename _Seq>
355 {
return !(__x == __y); }
358 template<
typename _Tp,
typename _Seq>
361 {
return __y < __x; }
364 template<
typename _Tp,
typename _Seq>
367 {
return !(__y < __x); }
370 template<
typename _Tp,
typename _Seq>
373 {
return !(__x < __y); }
375 #if __cplusplus >= 201103L
376 template<
typename _Tp,
typename _Seq>
378 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
380 typename enable_if<__is_swappable<_Seq>::value>::type
384 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
388 template<
typename _Tp,
typename _Seq,
typename _Alloc>
389 struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
390 :
public uses_allocator<_Seq, _Alloc>::type { };
391 #endif // __cplusplus >= 201103L
433 template<
typename _Tp,
typename _Sequence = vector<_Tp>,
434 typename _Compare = less<
typename _Sequence::value_type> >
437 #ifdef _GLIBCXX_CONCEPT_CHECKS
439 typedef typename _Sequence::value_type _Sequence_value_type;
440 # if __cplusplus < 201103L
441 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
443 __glibcxx_class_requires(_Sequence, _SequenceConcept)
444 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
445 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
446 __glibcxx_class_requires4(_Compare,
bool, _Tp, _Tp,
447 _BinaryFunctionConcept)
450 #if __cplusplus >= 201103L
451 template<
typename _Alloc>
452 using _Uses =
typename
457 typedef typename _Sequence::value_type value_type;
458 typedef typename _Sequence::reference reference;
459 typedef typename _Sequence::const_reference const_reference;
460 typedef typename _Sequence::size_type size_type;
461 typedef _Sequence container_type;
464 typedef _Compare value_compare;
475 #if __cplusplus < 201103L
478 const _Sequence& __s = _Sequence())
482 template<
typename _Seq = _Sequence,
typename _Requires =
typename
494 priority_queue(
const _Compare& __x, _Sequence&& __s = _Sequence())
495 : c(std::move(__s)), comp(__x)
496 { std::make_heap(c.begin(), c.end(), comp); }
498 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
503 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
505 : c(__a), comp(__x) { }
507 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
510 : c(__c, __a), comp(__x) { }
512 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
513 priority_queue(
const _Compare& __x, _Sequence&& __c,
const _Alloc& __a)
514 : c(std::move(__c), __a), comp(__x) { }
516 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
518 : c(__q.c, __a), comp(__q.comp) { }
520 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
522 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
540 #if __cplusplus < 201103L
541 template<
typename _InputIterator>
543 const _Compare& __x = _Compare(),
544 const _Sequence& __s = _Sequence())
547 __glibcxx_requires_valid_range(__first, __last);
548 c.insert(c.end(), __first, __last);
552 template<
typename _InputIterator>
555 const _Sequence& __s)
558 __glibcxx_requires_valid_range(__first, __last);
559 c.insert(c.end(), __first, __last);
563 template<
typename _InputIterator>
565 const _Compare& __x = _Compare(),
566 _Sequence&& __s = _Sequence())
567 : c(std::move(__s)), comp(__x)
569 __glibcxx_requires_valid_range(__first, __last);
570 c.insert(c.end(), __first, __last);
580 {
return c.empty(); }
594 __glibcxx_requires_nonempty();
613 #if __cplusplus >= 201103L
615 push(value_type&& __x)
617 c.push_back(std::move(__x));
621 template<
typename... _Args>
623 emplace(_Args&&... __args)
625 c.emplace_back(std::forward<_Args>(__args)...);
626 std::push_heap(c.begin(), c.end(), comp);
644 __glibcxx_requires_nonempty();
649 #if __cplusplus >= 201103L
653 #
if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
654 __is_nothrow_swappable<_Sequence>,
656 __is_nothrow_swappable<_Tp>,
658 __is_nothrow_swappable<_Compare>
663 swap(comp, __pq.comp);
665 #endif // __cplusplus >= 201103L
668 #if __cpp_deduction_guides >= 201606
669 template<
typename _Compare,
typename _Container,
670 typename = enable_if_t<!__is_allocator<_Compare>::value>,
671 typename = enable_if_t<!__is_allocator<_Container>::value>>
672 priority_queue(_Compare, _Container)
673 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
675 template<
typename _InputIterator,
typename _ValT
676 =
typename iterator_traits<_InputIterator>::value_type,
677 typename _Compare = less<_ValT>,
678 typename _Container = vector<_ValT>,
679 typename = _RequireInputIter<_InputIterator>,
680 typename = enable_if_t<!__is_allocator<_Compare>::value>,
681 typename = enable_if_t<!__is_allocator<_Container>::value>>
682 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
683 _Container = _Container())
684 -> priority_queue<_ValT, _Container, _Compare>;
686 template<
typename _Compare,
typename _Container,
typename _Allocator,
687 typename = enable_if_t<!__is_allocator<_Compare>::value>,
688 typename = enable_if_t<!__is_allocator<_Container>::value>,
689 typename = enable_if_t<__is_allocator<_Allocator>::value>>
690 priority_queue(_Compare, _Container, _Allocator)
691 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
696 #if __cplusplus >= 201103L
697 template<
typename _Tp,
typename _Sequence,
typename _Compare>
699 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
701 typename enable_if<__and_<__is_swappable<_Sequence>,
702 __is_swappable<_Compare>>::value>::type
706 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
707 priority_queue<_Tp, _Sequence, _Compare>& __y)
711 template<
typename _Tp,
typename _Sequence,
typename _Compare,
713 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
714 :
public uses_allocator<_Sequence, _Alloc>::type { };
715 #endif // __cplusplus >= 201103L
717 _GLIBCXX_END_NAMESPACE_VERSION
void push(const value_type &__x)
Add data to the queue.
priority_queue(_InputIterator __first, _InputIterator __last, const _Compare &__x, const _Sequence &__s)
Builds a queue from a range.
const_reference back() const
void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Pop an element off a heap using comparison functor.
enable_if< ::__array_traits< _Tp, _Nm >::_Is_swappable::value >::type noexcept(noexcept(__one.swap(__two)))
swap
A standard container giving FIFO behavior.
Define a member typedef type only if a boolean constant is true.
_Sequence c
c is the underlying container.
A standard container automatically sorting its contents.
void pop()
Removes first element.
priority_queue()
Default constructor creates no elements.
void push(const value_type &__x)
Add data to the end of the queue.
void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Push an element onto a heap using comparison functor.
void pop()
Removes first element.
void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
const_reference top() const
queue()
Default constructor creates no elements.
const_reference front() const