1 // Queue implementation -*- C++ -*-
2
3 // Copyright (C) 2001-2021 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51 /** @file bits/stl_queue.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{queue}
54 */
55
56 #ifndef _STL_QUEUE_H
57 #define _STL_QUEUE_H 1
58
59 #include <bits/concept_check.h>
60 #include <debug/debug.h>
61 #if __cplusplus >= 201103L
62 # include <bits/uses_allocator.h>
63 #endif
64
_GLIBCXX_VISIBILITY(default)65 namespace std _GLIBCXX_VISIBILITY(default)
66 {
67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
68
69 /**
70 * @brief A standard container giving FIFO behavior.
71 *
72 * @ingroup sequences
73 *
74 * @tparam _Tp Type of element.
75 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>.
76 *
77 * Meets many of the requirements of a
78 * <a href="tables.html#65">container</a>,
79 * but does not define anything to do with iterators. Very few of the
80 * other standard container interfaces are defined.
81 *
82 * This is not a true container, but an @e adaptor. It holds another
83 * container, and provides a wrapper interface to that container. The
84 * wrapper is what enforces strict first-in-first-out %queue behavior.
85 *
86 * The second template parameter defines the type of the underlying
87 * sequence/container. It defaults to std::deque, but it can be any type
88 * that supports @c front, @c back, @c push_back, and @c pop_front,
89 * such as std::list or an appropriate user-defined type.
90 *
91 * Members not found in @a normal containers are @c container_type,
92 * which is a typedef for the second Sequence parameter, and @c push and
93 * @c pop, which are standard %queue/FIFO operations.
94 */
95 template<typename _Tp, typename _Sequence = deque<_Tp> >
96 class queue
97 {
98 #ifdef _GLIBCXX_CONCEPT_CHECKS
99 // concept requirements
100 typedef typename _Sequence::value_type _Sequence_value_type;
101 # if __cplusplus < 201103L
102 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
103 # endif
104 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
105 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
106 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
107 #endif
108
109 template<typename _Tp1, typename _Seq1>
110 friend bool
111 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
112
113 template<typename _Tp1, typename _Seq1>
114 friend bool
115 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
116
117 #if __cpp_lib_three_way_comparison
118 template<typename _Tp1, three_way_comparable _Seq1>
119 friend compare_three_way_result_t<_Seq1>
120 operator<=>(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
121 #endif
122
123 #if __cplusplus >= 201103L
124 template<typename _Alloc>
125 using _Uses = typename
126 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
127
128 #if __cplusplus >= 201703L
129 // _GLIBCXX_RESOLVE_LIB_DEFECTS
130 // 2566. Requirements on the first template parameter of container
131 // adaptors
132 static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
133 "value_type must be the same as the underlying container");
134 #endif // C++17
135 #endif // C++11
136
137 public:
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;
143
144 protected:
145 /* Maintainers wondering why this isn't uglified as per style
146 * guidelines should note that this name is specified in the standard,
147 * C++98 [23.2.3.1].
148 * (Why? Presumably for the same reason that it's protected instead
149 * of private: to allow derivation. But none of the other
150 * containers allow for derivation. Odd.)
151 */
152 /// @c c is the underlying container.
153 _Sequence c;
154
155 public:
156 /**
157 * @brief Default constructor creates no elements.
158 */
159 #if __cplusplus < 201103L
160 explicit
161 queue(const _Sequence& __c = _Sequence())
162 : c(__c) { }
163 #else
164 template<typename _Seq = _Sequence, typename _Requires = typename
165 enable_if<is_default_constructible<_Seq>::value>::type>
166 queue()
167 : c() { }
168
169 explicit
170 queue(const _Sequence& __c)
171 : c(__c) { }
172
173 explicit
174 queue(_Sequence&& __c)
175 : c(std::move(__c)) { }
176
177 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
178 explicit
179 queue(const _Alloc& __a)
180 : c(__a) { }
181
182 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
183 queue(const _Sequence& __c, const _Alloc& __a)
184 : c(__c, __a) { }
185
186 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
187 queue(_Sequence&& __c, const _Alloc& __a)
188 : c(std::move(__c), __a) { }
189
190 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
191 queue(const queue& __q, const _Alloc& __a)
192 : c(__q.c, __a) { }
193
194 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
195 queue(queue&& __q, const _Alloc& __a)
196 : c(std::move(__q.c), __a) { }
197
198 #if __cplusplus > 202002L
199 #define __cpp_lib_adaptor_iterator_pair_constructor 202106L
200
201 template<typename _InputIterator,
202 typename = _RequireInputIter<_InputIterator>>
203 queue(_InputIterator __first, _InputIterator __last)
204 : c(__first, __last) { }
205
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) { }
211 #endif
212 #endif
213
214 /**
215 * Returns true if the %queue is empty.
216 */
217 _GLIBCXX_NODISCARD bool
218 empty() const
219 { return c.empty(); }
220
221 /** Returns the number of elements in the %queue. */
222 _GLIBCXX_NODISCARD
223 size_type
224 size() const
225 { return c.size(); }
226
227 /**
228 * Returns a read/write reference to the data at the first
229 * element of the %queue.
230 */
231 _GLIBCXX_NODISCARD
232 reference
233 front()
234 {
235 __glibcxx_requires_nonempty();
236 return c.front();
237 }
238
239 /**
240 * Returns a read-only (constant) reference to the data at the first
241 * element of the %queue.
242 */
243 _GLIBCXX_NODISCARD
244 const_reference
245 front() const
246 {
247 __glibcxx_requires_nonempty();
248 return c.front();
249 }
250
251 /**
252 * Returns a read/write reference to the data at the last
253 * element of the %queue.
254 */
255 _GLIBCXX_NODISCARD
256 reference
257 back()
258 {
259 __glibcxx_requires_nonempty();
260 return c.back();
261 }
262
263 /**
264 * Returns a read-only (constant) reference to the data at the last
265 * element of the %queue.
266 */
267 _GLIBCXX_NODISCARD
268 const_reference
269 back() const
270 {
271 __glibcxx_requires_nonempty();
272 return c.back();
273 }
274
275 /**
276 * @brief Add data to the end of the %queue.
277 * @param __x Data to be added.
278 *
279 * This is a typical %queue operation. The function creates an
280 * element at the end of the %queue and assigns the given data
281 * to it. The time complexity of the operation depends on the
282 * underlying sequence.
283 */
284 void
285 push(const value_type& __x)
286 { c.push_back(__x); }
287
288 #if __cplusplus >= 201103L
289 void
290 push(value_type&& __x)
291 { c.push_back(std::move(__x)); }
292
293 #if __cplusplus > 201402L
294 template<typename... _Args>
295 decltype(auto)
296 emplace(_Args&&... __args)
297 { return c.emplace_back(std::forward<_Args>(__args)...); }
298 #else
299 template<typename... _Args>
300 void
301 emplace(_Args&&... __args)
302 { c.emplace_back(std::forward<_Args>(__args)...); }
303 #endif
304 #endif
305
306 /**
307 * @brief Removes first element.
308 *
309 * This is a typical %queue operation. It shrinks the %queue by one.
310 * The time complexity of the operation depends on the underlying
311 * sequence.
312 *
313 * Note that no data is returned, and if the first element's
314 * data is needed, it should be retrieved before pop() is
315 * called.
316 */
317 void
318 pop()
319 {
320 __glibcxx_requires_nonempty();
321 c.pop_front();
322 }
323
324 #if __cplusplus >= 201103L
325 void
326 swap(queue& __q)
327 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
328 noexcept(__is_nothrow_swappable<_Sequence>::value)
329 #else
330 noexcept(__is_nothrow_swappable<_Tp>::value)
331 #endif
332 {
333 using std::swap;
334 swap(c, __q.c);
335 }
336 #endif // __cplusplus >= 201103L
337 };
338
339 #if __cpp_deduction_guides >= 201606
340 template<typename _Container,
341 typename = _RequireNotAllocator<_Container>>
342 queue(_Container) -> queue<typename _Container::value_type, _Container>;
343
344 template<typename _Container, typename _Allocator,
345 typename = _RequireNotAllocator<_Container>>
346 queue(_Container, _Allocator)
347 -> queue<typename _Container::value_type, _Container>;
348
349 #ifdef __cpp_lib_adaptor_iterator_pair_constructor
350 template<typename _InputIterator,
351 typename _ValT
352 = typename iterator_traits<_InputIterator>::value_type,
353 typename = _RequireInputIter<_InputIterator>>
354 queue(_InputIterator, _InputIterator) -> queue<_ValT>;
355
356 template<typename _InputIterator, typename _Allocator,
357 typename _ValT
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>>;
363 #endif
364 #endif
365
366 /**
367 * @brief Queue equality comparison.
368 * @param __x A %queue.
369 * @param __y A %queue of the same type as @a __x.
370 * @return True iff the size and elements of the queues are equal.
371 *
372 * This is an equivalence relation. Complexity and semantics depend on the
373 * underlying sequence type, but the expected rules are: this relation is
374 * linear in the size of the sequences, and queues are considered equivalent
375 * if their sequences compare equal.
376 */
377 template<typename _Tp, typename _Seq>
378 _GLIBCXX_NODISCARD
379 inline bool
380 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
381 { return __x.c == __y.c; }
382
383 /**
384 * @brief Queue ordering relation.
385 * @param __x A %queue.
386 * @param __y A %queue of the same type as @a x.
387 * @return True iff @a __x is lexicographically less than @a __y.
388 *
389 * This is an total ordering relation. Complexity and semantics
390 * depend on the underlying sequence type, but the expected rules
391 * are: this relation is linear in the size of the sequences, the
392 * elements must be comparable with @c <, and
393 * std::lexicographical_compare() is usually used to make the
394 * determination.
395 */
396 template<typename _Tp, typename _Seq>
397 _GLIBCXX_NODISCARD
398 inline bool
399 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
400 { return __x.c < __y.c; }
401
402 /// Based on operator==
403 template<typename _Tp, typename _Seq>
404 _GLIBCXX_NODISCARD
405 inline bool
406 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
407 { return !(__x == __y); }
408
409 /// Based on operator<
410 template<typename _Tp, typename _Seq>
411 _GLIBCXX_NODISCARD
412 inline bool
413 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
414 { return __y < __x; }
415
416 /// Based on operator<
417 template<typename _Tp, typename _Seq>
418 _GLIBCXX_NODISCARD
419 inline bool
420 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
421 { return !(__y < __x); }
422
423 /// Based on operator<
424 template<typename _Tp, typename _Seq>
425 _GLIBCXX_NODISCARD
426 inline bool
427 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
428 { return !(__x < __y); }
429
430 #if __cpp_lib_three_way_comparison
431 template<typename _Tp, three_way_comparable _Seq>
432 [[nodiscard]]
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; }
436 #endif
437
438 #if __cplusplus >= 201103L
439 template<typename _Tp, typename _Seq>
440 inline
441 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
442 // Constrained free swap overload, see p0185r1
443 typename enable_if<__is_swappable<_Seq>::value>::type
444 #else
445 void
446 #endif
447 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
448 noexcept(noexcept(__x.swap(__y)))
449 { __x.swap(__y); }
450
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
455
456 /**
457 * @brief A standard container automatically sorting its contents.
458 *
459 * @ingroup sequences
460 *
461 * @tparam _Tp Type of element.
462 * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>.
463 * @tparam _Compare Comparison function object type, defaults to
464 * less<_Sequence::value_type>.
465 *
466 * This is not a true container, but an @e adaptor. It holds
467 * another container, and provides a wrapper interface to that
468 * container. The wrapper is what enforces priority-based sorting
469 * and %queue behavior. Very few of the standard container/sequence
470 * interface requirements are met (e.g., iterators).
471 *
472 * The second template parameter defines the type of the underlying
473 * sequence/container. It defaults to std::vector, but it can be
474 * any type that supports @c front(), @c push_back, @c pop_back,
475 * and random-access iterators, such as std::deque or an
476 * appropriate user-defined type.
477 *
478 * The third template parameter supplies the means of making
479 * priority comparisons. It defaults to @c less<value_type> but
480 * can be anything defining a strict weak ordering.
481 *
482 * Members not found in @a normal containers are @c container_type,
483 * which is a typedef for the second Sequence parameter, and @c
484 * push, @c pop, and @c top, which are standard %queue operations.
485 *
486 * @note No equality/comparison operators are provided for
487 * %priority_queue.
488 *
489 * @note Sorting of the elements takes place as they are added to,
490 * and removed from, the %priority_queue using the
491 * %priority_queue's member functions. If you access the elements
492 * by other means, and change their data such that the sorting
493 * order would be different, the %priority_queue will not re-sort
494 * the elements for you. (How could it know to do so?)
495 */
496 template<typename _Tp, typename _Sequence = vector<_Tp>,
497 typename _Compare = less<typename _Sequence::value_type> >
498 class priority_queue
499 {
500 #ifdef _GLIBCXX_CONCEPT_CHECKS
501 // concept requirements
502 typedef typename _Sequence::value_type _Sequence_value_type;
503 # if __cplusplus < 201103L
504 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
505 # endif
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)
511 #endif
512
513 #if __cplusplus >= 201103L
514 template<typename _Alloc>
515 using _Uses = typename
516 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
517
518 #if __cplusplus >= 201703L
519 // _GLIBCXX_RESOLVE_LIB_DEFECTS
520 // 2566. Requirements on the first template parameter of container
521 // adaptors
522 static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
523 "value_type must be the same as the underlying container");
524 #endif // C++17
525 #endif // C++11
526
527 public:
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;
533 // _GLIBCXX_RESOLVE_LIB_DEFECTS
534 // DR 2684. priority_queue lacking comparator typedef
535 typedef _Compare value_compare;
536
537 protected:
538 // See queue::c for notes on these names.
539 _Sequence c;
540 _Compare comp;
541
542 public:
543 /**
544 * @brief Default constructor creates no elements.
545 */
546 #if __cplusplus < 201103L
547 explicit
548 priority_queue(const _Compare& __x = _Compare(),
549 const _Sequence& __s = _Sequence())
550 : c(__s), comp(__x)
551 { std::make_heap(c.begin(), c.end(), comp); }
552 #else
553 template<typename _Seq = _Sequence, typename _Requires = typename
554 enable_if<__and_<is_default_constructible<_Compare>,
555 is_default_constructible<_Seq>>::value>::type>
556 priority_queue()
557 : c(), comp() { }
558
559 explicit
560 priority_queue(const _Compare& __x, const _Sequence& __s)
561 : c(__s), comp(__x)
562 { std::make_heap(c.begin(), c.end(), comp); }
563
564 explicit
565 priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
566 : c(std::move(__s)), comp(__x)
567 { std::make_heap(c.begin(), c.end(), comp); }
568
569 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
570 explicit
571 priority_queue(const _Alloc& __a)
572 : c(__a), comp() { }
573
574 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
575 priority_queue(const _Compare& __x, const _Alloc& __a)
576 : c(__a), comp(__x) { }
577
578 // _GLIBCXX_RESOLVE_LIB_DEFECTS
579 // 2537. Constructors [...] taking allocators should call make_heap
580 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
581 priority_queue(const _Compare& __x, const _Sequence& __c,
582 const _Alloc& __a)
583 : c(__c, __a), comp(__x)
584 { std::make_heap(c.begin(), c.end(), comp); }
585
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)
589 { std::make_heap(c.begin(), c.end(), comp); }
590
591 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
592 priority_queue(const priority_queue& __q, const _Alloc& __a)
593 : c(__q.c, __a), comp(__q.comp) { }
594
595 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
596 priority_queue(priority_queue&& __q, const _Alloc& __a)
597 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
598 #endif
599
600 /**
601 * @brief Builds a %queue from a range.
602 * @param __first An input iterator.
603 * @param __last An input iterator.
604 * @param __x A comparison functor describing a strict weak ordering.
605 * @param __s An initial sequence with which to start.
606 *
607 * Begins by copying @a __s, inserting a copy of the elements
608 * from @a [first,last) into the copy of @a __s, then ordering
609 * the copy according to @a __x.
610 *
611 * For more information on function objects, see the
612 * documentation on @link functors functor base
613 * classes@endlink.
614 */
615 #if __cplusplus < 201103L
616 template<typename _InputIterator>
617 priority_queue(_InputIterator __first, _InputIterator __last,
618 const _Compare& __x = _Compare(),
619 const _Sequence& __s = _Sequence())
620 : c(__s), comp(__x)
621 {
622 __glibcxx_requires_valid_range(__first, __last);
623 c.insert(c.end(), __first, __last);
624 std::make_heap(c.begin(), c.end(), comp);
625 }
626 #else
627 // _GLIBCXX_RESOLVE_LIB_DEFECTS
628 // 3529. priority_queue(first, last) should construct c with (first, last)
629 template<typename _InputIterator,
630 typename = std::_RequireInputIter<_InputIterator>>
631 priority_queue(_InputIterator __first, _InputIterator __last,
632 const _Compare& __x = _Compare())
633 : c(__first, __last), comp(__x)
634 { std::make_heap(c.begin(), c.end(), comp); }
635
636 // _GLIBCXX_RESOLVE_LIB_DEFECTS
637 // 3522. Missing requirement on InputIterator template parameter
638 template<typename _InputIterator,
639 typename = std::_RequireInputIter<_InputIterator>>
640 priority_queue(_InputIterator __first, _InputIterator __last,
641 const _Compare& __x, const _Sequence& __s)
642 : c(__s), comp(__x)
643 {
644 __glibcxx_requires_valid_range(__first, __last);
645 c.insert(c.end(), __first, __last);
646 std::make_heap(c.begin(), c.end(), comp);
647 }
648
649 template<typename _InputIterator,
650 typename = std::_RequireInputIter<_InputIterator>>
651 priority_queue(_InputIterator __first, _InputIterator __last,
652 const _Compare& __x, _Sequence&& __s)
653 : c(std::move(__s)), comp(__x)
654 {
655 __glibcxx_requires_valid_range(__first, __last);
656 c.insert(c.end(), __first, __last);
657 std::make_heap(c.begin(), c.end(), comp);
658 }
659
660 // _GLIBCXX_RESOLVE_LIB_DEFECTS
661 // 3506. Missing allocator-extended constructors for priority_queue
662 template<typename _InputIterator, typename _Alloc,
663 typename = std::_RequireInputIter<_InputIterator>,
664 typename _Requires = _Uses<_Alloc>>
665 priority_queue(_InputIterator __first, _InputIterator __last,
666 const _Alloc& __alloc)
667 : c(__first, __last, __alloc), comp()
668 { std::make_heap(c.begin(), c.end(), comp); }
669
670 template<typename _InputIterator, typename _Alloc,
671 typename = std::_RequireInputIter<_InputIterator>,
672 typename _Requires = _Uses<_Alloc>>
673 priority_queue(_InputIterator __first, _InputIterator __last,
674 const _Compare& __x, const _Alloc& __alloc)
675 : c(__first, __last, __alloc), comp(__x)
676 { std::make_heap(c.begin(), c.end(), comp); }
677
678 template<typename _InputIterator, typename _Alloc,
679 typename = std::_RequireInputIter<_InputIterator>,
680 typename _Requires = _Uses<_Alloc>>
681 priority_queue(_InputIterator __first, _InputIterator __last,
682 const _Compare& __x, const _Sequence& __s,
683 const _Alloc& __alloc)
684 : c(__s, __alloc), comp(__x)
685 {
686 __glibcxx_requires_valid_range(__first, __last);
687 c.insert(c.end(), __first, __last);
688 std::make_heap(c.begin(), c.end(), comp);
689 }
690
691 template<typename _InputIterator, typename _Alloc,
692 typename _Requires = _Uses<_Alloc>>
693 priority_queue(_InputIterator __first, _InputIterator __last,
694 const _Compare& __x, _Sequence&& __s,
695 const _Alloc& __alloc)
696 : c(std::move(__s), __alloc), comp(__x)
697 {
698 __glibcxx_requires_valid_range(__first, __last);
699 c.insert(c.end(), __first, __last);
700 std::make_heap(c.begin(), c.end(), comp);
701 }
702 #endif
703
704 /**
705 * Returns true if the %queue is empty.
706 */
707 _GLIBCXX_NODISCARD bool
708 empty() const
709 { return c.empty(); }
710
711 /** Returns the number of elements in the %queue. */
712 _GLIBCXX_NODISCARD
713 size_type
714 size() const
715 { return c.size(); }
716
717 /**
718 * Returns a read-only (constant) reference to the data at the first
719 * element of the %queue.
720 */
721 _GLIBCXX_NODISCARD
722 const_reference
723 top() const
724 {
725 __glibcxx_requires_nonempty();
726 return c.front();
727 }
728
729 /**
730 * @brief Add data to the %queue.
731 * @param __x Data to be added.
732 *
733 * This is a typical %queue operation.
734 * The time complexity of the operation depends on the underlying
735 * sequence.
736 */
737 void
738 push(const value_type& __x)
739 {
740 c.push_back(__x);
741 std::push_heap(c.begin(), c.end(), comp);
742 }
743
744 #if __cplusplus >= 201103L
745 void
746 push(value_type&& __x)
747 {
748 c.push_back(std::move(__x));
749 std::push_heap(c.begin(), c.end(), comp);
750 }
751
752 template<typename... _Args>
753 void
754 emplace(_Args&&... __args)
755 {
756 c.emplace_back(std::forward<_Args>(__args)...);
757 std::push_heap(c.begin(), c.end(), comp);
758 }
759 #endif
760
761 /**
762 * @brief Removes first element.
763 *
764 * This is a typical %queue operation. It shrinks the %queue
765 * by one. The time complexity of the operation depends on the
766 * underlying sequence.
767 *
768 * Note that no data is returned, and if the first element's
769 * data is needed, it should be retrieved before pop() is
770 * called.
771 */
772 void
773 pop()
774 {
775 __glibcxx_requires_nonempty();
776 std::pop_heap(c.begin(), c.end(), comp);
777 c.pop_back();
778 }
779
780 #if __cplusplus >= 201103L
781 void
782 swap(priority_queue& __pq)
783 noexcept(__and_<
784 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
785 __is_nothrow_swappable<_Sequence>,
786 #else
787 __is_nothrow_swappable<_Tp>,
788 #endif
789 __is_nothrow_swappable<_Compare>
790 >::value)
791 {
792 using std::swap;
793 swap(c, __pq.c);
794 swap(comp, __pq.comp);
795 }
796 #endif // __cplusplus >= 201103L
797 };
798
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>;
805
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>;
816
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>;
822 #endif
823
824 // No equality/comparison operators are provided for priority_queue.
825
826 #if __cplusplus >= 201103L
827 template<typename _Tp, typename _Sequence, typename _Compare>
828 inline
829 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
830 // Constrained free swap overload, see p0185r1
831 typename enable_if<__and_<__is_swappable<_Sequence>,
832 __is_swappable<_Compare>>::value>::type
833 #else
834 void
835 #endif
836 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
837 priority_queue<_Tp, _Sequence, _Compare>& __y)
838 noexcept(noexcept(__x.swap(__y)))
839 { __x.swap(__y); }
840
841 template<typename _Tp, typename _Sequence, typename _Compare,
842 typename _Alloc>
843 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
844 : public uses_allocator<_Sequence, _Alloc>::type { };
845 #endif // __cplusplus >= 201103L
846
847 _GLIBCXX_END_NAMESPACE_VERSION
848 } // namespace
849
850 #endif /* _STL_QUEUE_H */
851