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 122 #if __cplusplus >= 201703L 127 "value_type must be the same as the underlying container");
132 typedef typename _Sequence::value_type value_type;
133 typedef typename _Sequence::reference reference;
134 typedef typename _Sequence::const_reference const_reference;
135 typedef typename _Sequence::size_type size_type;
136 typedef _Sequence container_type;
153 #if __cplusplus < 201103L 155 queue(
const _Sequence& __c = _Sequence())
158 template<
typename _Seq = _Sequence,
typename _Requires =
typename 164 queue(
const _Sequence& __c)
168 queue(_Sequence&& __c)
169 :
c(
std::move(__c)) { }
171 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
173 queue(
const _Alloc& __a)
176 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
177 queue(
const _Sequence& __c,
const _Alloc& __a)
180 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
181 queue(_Sequence&& __c,
const _Alloc& __a)
182 :
c(
std::move(__c), __a) { }
184 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
188 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
190 :
c(
std::move(__q.
c), __a) { }
196 _GLIBCXX_NODISCARD
bool 198 {
return c.empty(); }
212 __glibcxx_requires_nonempty();
223 __glibcxx_requires_nonempty();
234 __glibcxx_requires_nonempty();
245 __glibcxx_requires_nonempty();
260 {
c.push_back(__x); }
262 #if __cplusplus >= 201103L 264 push(value_type&& __x)
265 {
c.push_back(std::move(__x)); }
267 #if __cplusplus > 201402L 268 template<
typename... _Args>
270 emplace(_Args&&... __args)
271 {
return c.emplace_back(std::forward<_Args>(__args)...); }
273 template<
typename... _Args>
275 emplace(_Args&&... __args)
276 {
c.emplace_back(std::forward<_Args>(__args)...); }
294 __glibcxx_requires_nonempty();
298 #if __cplusplus >= 201103L 301 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 302 noexcept(__is_nothrow_swappable<_Sequence>::value)
304 noexcept(__is_nothrow_swappable<_Tp>::value)
310 #endif // __cplusplus >= 201103L 313 #if __cpp_deduction_guides >= 201606 314 template<
typename _Container,
315 typename = _RequireNotAllocator<_Container>>
316 queue(_Container) -> queue<typename _Container::value_type, _Container>;
318 template<
typename _Container,
typename _Allocator,
319 typename = _RequireNotAllocator<_Container>,
320 typename = _RequireAllocator<_Allocator>>
321 queue(_Container, _Allocator)
322 -> queue<typename _Container::value_type, _Container>;
336 template<
typename _Tp,
typename _Seq>
339 {
return __x.
c == __y.
c; }
354 template<
typename _Tp,
typename _Seq>
357 {
return __x.
c < __y.c; }
360 template<
typename _Tp,
typename _Seq>
363 {
return !(__x == __y); }
366 template<
typename _Tp,
typename _Seq>
369 {
return __y < __x; }
372 template<
typename _Tp,
typename _Seq>
375 {
return !(__y < __x); }
378 template<
typename _Tp,
typename _Seq>
381 {
return !(__x < __y); }
383 #if __cplusplus >= 201103L 384 template<
typename _Tp,
typename _Seq>
386 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 388 typename enable_if<__is_swappable<_Seq>::value>::type
392 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
393 noexcept(noexcept(__x.swap(__y)))
396 template<
typename _Tp,
typename _Seq,
typename _Alloc>
397 struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
398 :
public uses_allocator<_Seq, _Alloc>::type { };
399 #endif // __cplusplus >= 201103L 441 template<
typename _Tp,
typename _Sequence = vector<_Tp>,
442 typename _Compare = less<
typename _Sequence::value_type> >
445 #ifdef _GLIBCXX_CONCEPT_CHECKS 447 typedef typename _Sequence::value_type _Sequence_value_type;
448 # if __cplusplus < 201103L 449 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
451 __glibcxx_class_requires(_Sequence, _SequenceConcept)
452 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
453 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
454 __glibcxx_class_requires4(_Compare,
bool, _Tp, _Tp,
455 _BinaryFunctionConcept)
458 #if __cplusplus >= 201103L 459 template<
typename _Alloc>
460 using _Uses =
typename 463 #if __cplusplus >= 201703L 468 "value_type must be the same as the underlying container");
473 typedef typename _Sequence::value_type value_type;
474 typedef typename _Sequence::reference reference;
475 typedef typename _Sequence::const_reference const_reference;
476 typedef typename _Sequence::size_type size_type;
477 typedef _Sequence container_type;
480 typedef _Compare value_compare;
491 #if __cplusplus < 201103L 494 const _Sequence& __s = _Sequence())
498 template<
typename _Seq = _Sequence,
typename _Requires =
typename 510 priority_queue(
const _Compare& __x, _Sequence&& __s = _Sequence())
511 : c(
std::move(__s)), comp(__x)
512 { std::make_heap(c.begin(), c.end(), comp); }
514 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
519 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
521 : c(__a), comp(__x) { }
525 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
528 : c(__c, __a), comp(__x)
531 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
532 priority_queue(
const _Compare& __x, _Sequence&& __c,
const _Alloc& __a)
533 : c(
std::move(__c), __a), comp(__x)
536 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
538 : c(__q.c, __a), comp(__q.comp) { }
540 template<
typename _Alloc,
typename _Requires = _Uses<_Alloc>>
542 : c(
std::move(__q.c), __a), comp(
std::move(__q.comp)) { }
560 #if __cplusplus < 201103L 561 template<
typename _InputIterator>
563 const _Compare& __x = _Compare(),
564 const _Sequence& __s = _Sequence())
567 __glibcxx_requires_valid_range(__first, __last);
568 c.insert(c.end(), __first, __last);
572 template<
typename _InputIterator>
575 const _Sequence& __s)
578 __glibcxx_requires_valid_range(__first, __last);
579 c.insert(c.end(), __first, __last);
583 template<
typename _InputIterator>
585 const _Compare& __x = _Compare(),
586 _Sequence&& __s = _Sequence())
587 : c(
std::move(__s)), comp(__x)
589 __glibcxx_requires_valid_range(__first, __last);
590 c.insert(c.end(), __first, __last);
598 _GLIBCXX_NODISCARD
bool 600 {
return c.empty(); }
614 __glibcxx_requires_nonempty();
633 #if __cplusplus >= 201103L 635 push(value_type&& __x)
637 c.push_back(std::move(__x));
641 template<
typename... _Args>
643 emplace(_Args&&... __args)
645 c.emplace_back(std::forward<_Args>(__args)...);
646 std::push_heap(c.begin(), c.end(), comp);
664 __glibcxx_requires_nonempty();
669 #if __cplusplus >= 201103L 673 #
if __cplusplus > 201402L || !defined(__STRICT_ANSI__)
674 __is_nothrow_swappable<_Sequence>,
676 __is_nothrow_swappable<_Tp>,
678 __is_nothrow_swappable<_Compare>
683 swap(comp, __pq.comp);
685 #endif // __cplusplus >= 201103L 688 #if __cpp_deduction_guides >= 201606 689 template<
typename _Compare,
typename _Container,
690 typename = _RequireNotAllocator<_Compare>,
691 typename = _RequireNotAllocator<_Container>>
692 priority_queue(_Compare, _Container)
693 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
695 template<
typename _InputIterator,
typename _ValT
696 =
typename iterator_traits<_InputIterator>::value_type,
697 typename _Compare = less<_ValT>,
698 typename _Container = vector<_ValT>,
699 typename = _RequireInputIter<_InputIterator>,
700 typename = _RequireNotAllocator<_Compare>,
701 typename = _RequireNotAllocator<_Container>>
702 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
703 _Container = _Container())
704 -> priority_queue<_ValT, _Container, _Compare>;
706 template<
typename _Compare,
typename _Container,
typename _Allocator,
707 typename = _RequireNotAllocator<_Compare>,
708 typename = _RequireNotAllocator<_Container>,
709 typename = _RequireAllocator<_Allocator>>
710 priority_queue(_Compare, _Container, _Allocator)
711 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
716 #if __cplusplus >= 201103L 717 template<
typename _Tp,
typename _Sequence,
typename _Compare>
719 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 721 typename enable_if<__and_<__is_swappable<_Sequence>,
722 __is_swappable<_Compare>>::value>::type
726 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
727 priority_queue<_Tp, _Sequence, _Compare>& __y)
728 noexcept(noexcept(__x.swap(__y)))
731 template<
typename _Tp,
typename _Sequence,
typename _Compare,
733 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
734 :
public uses_allocator<_Sequence, _Alloc>::type { };
735 #endif // __cplusplus >= 201103L 737 _GLIBCXX_END_NAMESPACE_VERSION
_GLIBCXX_NODISCARD bool empty() const
ISO C++ entities toplevel namespace is std.
void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Push an element onto a heap using comparison functor.
priority_queue()
Default constructor creates no elements.
queue()
Default constructor creates no elements.
const_reference top() const
void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
void push(const value_type &__x)
Add data to the queue.
const_reference front() const
_Sequence c
c is the underlying container.
void pop()
Removes first element.
void pop()
Removes first element.
_GLIBCXX_NODISCARD bool empty() const
priority_queue(_InputIterator __first, _InputIterator __last, const _Compare &__x, const _Sequence &__s)
Builds a queue from a range.
A standard container giving FIFO behavior.
void push(const value_type &__x)
Add data to the end of the queue.
A standard container automatically sorting its contents.
void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Pop an element off a heap using comparison functor.
const_reference back() const
Define a member typedef type only if a boolean constant is true.