libstdc++
stl_queue.h
Go to the documentation of this file.
1// Queue implementation -*- C++ -*-
2
3// Copyright (C) 2001-2025 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#if __glibcxx_ranges_to_container // C++ >= 23
65# include <ranges> // ranges::to
66# include <bits/ranges_algobase.h> // ranges::copy
67#endif
68
69namespace std _GLIBCXX_VISIBILITY(default)
70{
71_GLIBCXX_BEGIN_NAMESPACE_VERSION
72
73 /**
74 * @brief A standard container giving FIFO behavior.
75 *
76 * @ingroup sequences
77 *
78 * @tparam _Tp Type of element.
79 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>.
80 *
81 * Meets many of the requirements of a
82 * <a href="tables.html#65">container</a>,
83 * but does not define anything to do with iterators. Very few of the
84 * other standard container interfaces are defined.
85 *
86 * This is not a true container, but an @e adaptor. It holds another
87 * container, and provides a wrapper interface to that container. The
88 * wrapper is what enforces strict first-in-first-out %queue behavior.
89 *
90 * The second template parameter defines the type of the underlying
91 * sequence/container. It defaults to std::deque, but it can be any type
92 * that supports @c front, @c back, @c push_back, and @c pop_front,
93 * such as std::list or an appropriate user-defined type.
94 *
95 * Members not found in @a normal containers are @c container_type,
96 * which is a typedef for the second Sequence parameter, and @c push and
97 * @c pop, which are standard %queue/FIFO operations.
98 */
99 template<typename _Tp, typename _Sequence = deque<_Tp> >
100 class queue
101 {
102#ifdef _GLIBCXX_CONCEPT_CHECKS
103 // concept requirements
104 typedef typename _Sequence::value_type _Sequence_value_type;
105# if __cplusplus < 201103L
106 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
107# endif
108 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
109 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
110 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
111#endif
112
113 template<typename _Tp1, typename _Seq1>
114 friend bool
115 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
116
117 template<typename _Tp1, typename _Seq1>
118 friend bool
119 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
120
121#if __cpp_lib_three_way_comparison
122 template<typename _Tp1, three_way_comparable _Seq1>
124 operator<=>(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
125#endif
126
127#if __cplusplus >= 201103L
128 template<typename _Alloc>
129 using _Uses = typename
131
132#if __cplusplus >= 201703L
133 // _GLIBCXX_RESOLVE_LIB_DEFECTS
134 // 2566. Requirements on the first template parameter of container
135 // adaptors
137 "value_type must be the same as the underlying container");
138#endif // C++17
139#endif // C++11
140
141 public:
142 typedef typename _Sequence::value_type value_type;
143 typedef typename _Sequence::reference reference;
144 typedef typename _Sequence::const_reference const_reference;
145 typedef typename _Sequence::size_type size_type;
146 typedef _Sequence container_type;
147
148 protected:
149 /* Maintainers wondering why this isn't uglified as per style
150 * guidelines should note that this name is specified in the standard,
151 * C++98 [23.2.3.1].
152 * (Why? Presumably for the same reason that it's protected instead
153 * of private: to allow derivation. But none of the other
154 * containers allow for derivation. Odd.)
155 */
156 /// @c c is the underlying container.
157 _Sequence c;
158
159 public:
160 /**
161 * @brief Default constructor creates no elements.
162 */
163#if __cplusplus < 201103L
164 explicit
165 queue(const _Sequence& __c = _Sequence())
166 : c(__c) { }
167#else
168 template<typename _Seq = _Sequence, typename _Requires = typename
171 : c() { }
172
173 explicit
174 queue(const _Sequence& __c)
175 : c(__c) { }
176
177 explicit
178 queue(_Sequence&& __c)
179 : c(std::move(__c)) { }
180
181 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
182 explicit
183 queue(const _Alloc& __a)
184 : c(__a) { }
185
186 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
187 queue(const _Sequence& __c, const _Alloc& __a)
188 : c(__c, __a) { }
189
190 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
191 queue(_Sequence&& __c, const _Alloc& __a)
192 : c(std::move(__c), __a) { }
193
194 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
195 queue(const queue& __q, const _Alloc& __a)
196 : c(__q.c, __a) { }
197
198 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
199 queue(queue&& __q, const _Alloc& __a)
200 : c(std::move(__q.c), __a) { }
201#endif
202
203#ifdef __glibcxx_adaptor_iterator_pair_constructor // C++ >= 23 && HOSTED
204 template<typename _InputIterator,
205 typename = _RequireInputIter<_InputIterator>>
206 queue(_InputIterator __first, _InputIterator __last)
207 : c(__first, __last) { }
208
209 template<typename _InputIterator, typename _Alloc,
210 typename = _RequireInputIter<_InputIterator>,
211 typename = _Uses<_Alloc>>
212 queue(_InputIterator __first, _InputIterator __last, const _Alloc& __a)
213 : c(__first, __last, __a) { }
214#endif
215
216#if __glibcxx_ranges_to_container // C++ >= 23
217 /**
218 * @brief Construct a queue from a range.
219 * @since C++23
220 */
221 template<__detail::__container_compatible_range<_Tp> _Rg>
222 queue(from_range_t, _Rg&& __rg)
223 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg)))
224 { }
225
226 /**
227 * @brief Construct a queue from a range.
228 * @since C++23
229 */
230 template<__detail::__container_compatible_range<_Tp> _Rg,
231 typename _Alloc>
232 queue(from_range_t, _Rg&& __rg, const _Alloc& __a)
233 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a))
234 { }
235#endif
236
237 /**
238 * Returns true if the %queue is empty.
239 */
240 _GLIBCXX_NODISCARD bool
241 empty() const
242 { return c.empty(); }
243
244 /** Returns the number of elements in the %queue. */
245 _GLIBCXX_NODISCARD
246 size_type
247 size() const
248 { return c.size(); }
249
250 /**
251 * Returns a read/write reference to the data at the first
252 * element of the %queue.
253 */
254 _GLIBCXX_NODISCARD
255 reference
257 {
258 __glibcxx_requires_nonempty();
259 return c.front();
260 }
261
262 /**
263 * Returns a read-only (constant) reference to the data at the first
264 * element of the %queue.
265 */
266 _GLIBCXX_NODISCARD
267 const_reference
268 front() const
269 {
270 __glibcxx_requires_nonempty();
271 return c.front();
272 }
273
274 /**
275 * Returns a read/write reference to the data at the last
276 * element of the %queue.
277 */
278 _GLIBCXX_NODISCARD
279 reference
281 {
282 __glibcxx_requires_nonempty();
283 return c.back();
284 }
285
286 /**
287 * Returns a read-only (constant) reference to the data at the last
288 * element of the %queue.
289 */
290 _GLIBCXX_NODISCARD
291 const_reference
292 back() const
293 {
294 __glibcxx_requires_nonempty();
295 return c.back();
296 }
297
298 /**
299 * @brief Add data to the end of the %queue.
300 * @param __x Data to be added.
301 *
302 * This is a typical %queue operation. The function creates an
303 * element at the end of the %queue and assigns the given data
304 * to it. The time complexity of the operation depends on the
305 * underlying sequence.
306 */
307 void
308 push(const value_type& __x)
309 { c.push_back(__x); }
310
311#if __cplusplus >= 201103L
312 void
313 push(value_type&& __x)
314 { c.push_back(std::move(__x)); }
315
316#if __cplusplus > 201402L
317 template<typename... _Args>
318 decltype(auto)
319 emplace(_Args&&... __args)
320 { return c.emplace_back(std::forward<_Args>(__args)...); }
321#else
322 template<typename... _Args>
323 void
324 emplace(_Args&&... __args)
325 { c.emplace_back(std::forward<_Args>(__args)...); }
326#endif
327#endif
328
329#if __glibcxx_ranges_to_container // C++ >= 23
330 template<__detail::__container_compatible_range<_Tp> _Rg>
331 void
332 push_range(_Rg&& __rg)
333 {
334 if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); })
335 c.append_range(std::forward<_Rg>(__rg));
336 else
337 ranges::copy(__rg, std::back_inserter(c));
338 }
339#endif
340
341 /**
342 * @brief Removes first element.
343 *
344 * This is a typical %queue operation. It shrinks the %queue by one.
345 * The time complexity of the operation depends on the underlying
346 * sequence.
347 *
348 * Note that no data is returned, and if the first element's
349 * data is needed, it should be retrieved before pop() is
350 * called.
351 */
352 void
354 {
355 __glibcxx_requires_nonempty();
356 c.pop_front();
357 }
358
359#if __cplusplus >= 201103L
360 void
361 swap(queue& __q)
362#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
363 noexcept(__is_nothrow_swappable<_Sequence>::value)
364#else
365 noexcept(__is_nothrow_swappable<_Tp>::value)
366#endif
367 {
368 using std::swap;
369 swap(c, __q.c);
370 }
371#endif // __cplusplus >= 201103L
372 };
373
374#if __cpp_deduction_guides >= 201606
375 template<typename _Container,
376 typename = _RequireNotAllocator<_Container>>
377 queue(_Container) -> queue<typename _Container::value_type, _Container>;
378
379 template<typename _Container, typename _Allocator,
380 typename = _RequireNotAllocator<_Container>>
381 queue(_Container, _Allocator)
382 -> queue<typename _Container::value_type, _Container>;
383
384#ifdef __glibcxx_adaptor_iterator_pair_constructor
385 template<typename _InputIterator,
386 typename _ValT
387 = typename iterator_traits<_InputIterator>::value_type,
388 typename = _RequireInputIter<_InputIterator>>
389 queue(_InputIterator, _InputIterator) -> queue<_ValT>;
390
391 template<typename _InputIterator, typename _Allocator,
392 typename _ValT
393 = typename iterator_traits<_InputIterator>::value_type,
394 typename = _RequireInputIter<_InputIterator>,
395 typename = _RequireAllocator<_Allocator>>
396 queue(_InputIterator, _InputIterator, _Allocator)
397 -> queue<_ValT, deque<_ValT, _Allocator>>;
398#endif
399
400#if __glibcxx_ranges_to_container // C++ >= 23
401 template<ranges::input_range _Rg>
402 queue(from_range_t, _Rg&&) -> queue<ranges::range_value_t<_Rg>>;
403
404 template<ranges::input_range _Rg, __allocator_like _Alloc>
405 queue(from_range_t, _Rg&&, _Alloc)
406 -> queue<ranges::range_value_t<_Rg>,
407 deque<ranges::range_value_t<_Rg>, _Alloc>>;
408#endif
409#endif
410
411 /**
412 * @brief Queue equality comparison.
413 * @param __x A %queue.
414 * @param __y A %queue of the same type as @a __x.
415 * @return True iff the size and elements of the queues are equal.
416 *
417 * This is an equivalence relation. Complexity and semantics depend on the
418 * underlying sequence type, but the expected rules are: this relation is
419 * linear in the size of the sequences, and queues are considered equivalent
420 * if their sequences compare equal.
421 */
422 template<typename _Tp, typename _Seq>
423 _GLIBCXX_NODISCARD
424 inline bool
425 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
426 { return __x.c == __y.c; }
427
428 /**
429 * @brief Queue ordering relation.
430 * @param __x A %queue.
431 * @param __y A %queue of the same type as @a x.
432 * @return True iff @a __x is lexicographically less than @a __y.
433 *
434 * This is an total ordering relation. Complexity and semantics
435 * depend on the underlying sequence type, but the expected rules
436 * are: this relation is linear in the size of the sequences, the
437 * elements must be comparable with @c <, and
438 * std::lexicographical_compare() is usually used to make the
439 * determination.
440 */
441 template<typename _Tp, typename _Seq>
442 _GLIBCXX_NODISCARD
443 inline bool
444 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
445 { return __x.c < __y.c; }
446
447 /// Based on operator==
448 template<typename _Tp, typename _Seq>
449 _GLIBCXX_NODISCARD
450 inline bool
451 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
452 { return !(__x == __y); }
453
454 /// Based on operator<
455 template<typename _Tp, typename _Seq>
456 _GLIBCXX_NODISCARD
457 inline bool
458 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
459 { return __y < __x; }
460
461 /// Based on operator<
462 template<typename _Tp, typename _Seq>
463 _GLIBCXX_NODISCARD
464 inline bool
465 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
466 { return !(__y < __x); }
467
468 /// Based on operator<
469 template<typename _Tp, typename _Seq>
470 _GLIBCXX_NODISCARD
471 inline bool
472 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
473 { return !(__x < __y); }
474
475#if __cpp_lib_three_way_comparison
476 template<typename _Tp, three_way_comparable _Seq>
477 [[nodiscard]]
478 inline compare_three_way_result_t<_Seq>
479 operator<=>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
480 { return __x.c <=> __y.c; }
481#endif
482
483#if __cplusplus >= 201103L
484 template<typename _Tp, typename _Seq>
485 inline
486#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
487 // Constrained free swap overload, see p0185r1
488 typename enable_if<__is_swappable<_Seq>::value>::type
489#else
490 void
491#endif
492 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
493 noexcept(noexcept(__x.swap(__y)))
494 { __x.swap(__y); }
495
496 template<typename _Tp, typename _Seq, typename _Alloc>
497 struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
498 : public uses_allocator<_Seq, _Alloc>::type { };
499#endif // __cplusplus >= 201103L
500
501 /**
502 * @brief A standard container automatically sorting its contents.
503 *
504 * @ingroup sequences
505 *
506 * @tparam _Tp Type of element.
507 * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>.
508 * @tparam _Compare Comparison function object type, defaults to
509 * less<_Sequence::value_type>.
510 *
511 * This is not a true container, but an @e adaptor. It holds
512 * another container, and provides a wrapper interface to that
513 * container. The wrapper is what enforces priority-based sorting
514 * and %queue behavior. Very few of the standard container/sequence
515 * interface requirements are met (e.g., iterators).
516 *
517 * The second template parameter defines the type of the underlying
518 * sequence/container. It defaults to std::vector, but it can be
519 * any type that supports @c front(), @c push_back, @c pop_back,
520 * and random-access iterators, such as std::deque or an
521 * appropriate user-defined type.
522 *
523 * The third template parameter supplies the means of making
524 * priority comparisons. It defaults to @c less<value_type> but
525 * can be anything defining a strict weak ordering.
526 *
527 * Members not found in @a normal containers are @c container_type,
528 * which is a typedef for the second Sequence parameter, and @c
529 * push, @c pop, and @c top, which are standard %queue operations.
530 *
531 * @note No equality/comparison operators are provided for
532 * %priority_queue.
533 *
534 * @note Sorting of the elements takes place as they are added to,
535 * and removed from, the %priority_queue using the
536 * %priority_queue's member functions. If you access the elements
537 * by other means, and change their data such that the sorting
538 * order would be different, the %priority_queue will not re-sort
539 * the elements for you. (How could it know to do so?)
540 */
541 template<typename _Tp, typename _Sequence = vector<_Tp>,
542 typename _Compare = less<typename _Sequence::value_type> >
544 {
545#ifdef _GLIBCXX_CONCEPT_CHECKS
546 // concept requirements
547 typedef typename _Sequence::value_type _Sequence_value_type;
548# if __cplusplus < 201103L
549 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
550# endif
551 __glibcxx_class_requires(_Sequence, _SequenceConcept)
552 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
553 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
554 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
555 _BinaryFunctionConcept)
556#endif
557
558#if __cplusplus >= 201103L
559 template<typename _Alloc>
560 using _Uses = typename
562
563#if __cplusplus >= 201703L
564 // _GLIBCXX_RESOLVE_LIB_DEFECTS
565 // 2566. Requirements on the first template parameter of container
566 // adaptors
568 "value_type must be the same as the underlying container");
569#endif // C++17
570#endif // C++11
571
572 public:
573 typedef typename _Sequence::value_type value_type;
574 typedef typename _Sequence::reference reference;
575 typedef typename _Sequence::const_reference const_reference;
576 typedef typename _Sequence::size_type size_type;
577 typedef _Sequence container_type;
578 // _GLIBCXX_RESOLVE_LIB_DEFECTS
579 // DR 2684. priority_queue lacking comparator typedef
580 typedef _Compare value_compare;
581
582 protected:
583 // See queue::c for notes on these names.
584 _Sequence c;
585 _Compare comp;
586
587 public:
588 /**
589 * @brief Default constructor creates no elements.
590 */
591#if __cplusplus < 201103L
592 explicit
593 priority_queue(const _Compare& __x = _Compare(),
594 const _Sequence& __s = _Sequence())
595 : c(__s), comp(__x)
596 { std::make_heap(c.begin(), c.end(), comp); }
597#else
598 template<typename _Seq = _Sequence, typename _Requires = typename
600 is_default_constructible<_Seq>>::value>::type>
602 : c(), comp() { }
603
604 explicit
605 priority_queue(const _Compare& __x, const _Sequence& __s)
606 : c(__s), comp(__x)
607 { std::make_heap(c.begin(), c.end(), comp); }
608
609 explicit
610 priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
611 : c(std::move(__s)), comp(__x)
612 { std::make_heap(c.begin(), c.end(), comp); }
613
614 priority_queue(const priority_queue&) = default;
615 priority_queue& operator=(const priority_queue&) = default;
616
618 noexcept(__and_<is_nothrow_move_constructible<_Sequence>,
619 is_nothrow_move_constructible<_Compare>>::value)
620 : c(std::move(__q.c)), comp(std::move(__q.comp))
621 { __q.c.clear(); }
622
624 operator=(priority_queue&& __q)
625 noexcept(__and_<is_nothrow_move_assignable<_Sequence>,
626 is_nothrow_move_assignable<_Compare>>::value)
627 {
628 c = std::move(__q.c);
629 __q.c.clear();
630 comp = std::move(__q.comp);
631 return *this;
632 }
633
634 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
635 explicit
636 priority_queue(const _Alloc& __a)
637 : c(__a), comp() { }
638
639 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
640 priority_queue(const _Compare& __x, const _Alloc& __a)
641 : c(__a), comp(__x) { }
642
643 // _GLIBCXX_RESOLVE_LIB_DEFECTS
644 // 2537. Constructors [...] taking allocators should call make_heap
645 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
646 priority_queue(const _Compare& __x, const _Sequence& __c,
647 const _Alloc& __a)
648 : c(__c, __a), comp(__x)
649 { std::make_heap(c.begin(), c.end(), comp); }
650
651 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
652 priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
653 : c(std::move(__c), __a), comp(__x)
654 { std::make_heap(c.begin(), c.end(), comp); }
655
656 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
657 priority_queue(const priority_queue& __q, const _Alloc& __a)
658 : c(__q.c, __a), comp(__q.comp) { }
659
660 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
661 priority_queue(priority_queue&& __q, const _Alloc& __a)
662 : c(std::move(__q.c), __a), comp(std::move(__q.comp))
663 { __q.c.clear(); }
664#endif
665
666 /**
667 * @brief Builds a %queue from a range.
668 * @param __first An input iterator.
669 * @param __last An input iterator.
670 * @param __x A comparison functor describing a strict weak ordering.
671 * @param __s An initial sequence with which to start.
672 *
673 * Begins by copying @a __s, inserting a copy of the elements
674 * from @a [first,last) into the copy of @a __s, then ordering
675 * the copy according to @a __x.
676 *
677 * For more information on function objects, see the
678 * documentation on @link functors functor base classes@endlink.
679 */
680#if __cplusplus < 201103L
681 template<typename _InputIterator>
682 priority_queue(_InputIterator __first, _InputIterator __last,
683 const _Compare& __x = _Compare(),
684 const _Sequence& __s = _Sequence())
685 : c(__s), comp(__x)
686 {
687 __glibcxx_requires_valid_range(__first, __last);
688 c.insert(c.end(), __first, __last);
689 std::make_heap(c.begin(), c.end(), comp);
690 }
691#else
692 // _GLIBCXX_RESOLVE_LIB_DEFECTS
693 // 3529. priority_queue(first, last) should construct c with (first, last)
694 template<typename _InputIterator,
695 typename = std::_RequireInputIter<_InputIterator>>
696 priority_queue(_InputIterator __first, _InputIterator __last,
697 const _Compare& __x = _Compare())
698 : c(__first, __last), comp(__x)
699 { std::make_heap(c.begin(), c.end(), comp); }
700
701 // _GLIBCXX_RESOLVE_LIB_DEFECTS
702 // 3522. Missing requirement on InputIterator template parameter
703 template<typename _InputIterator,
704 typename = std::_RequireInputIter<_InputIterator>>
705 priority_queue(_InputIterator __first, _InputIterator __last,
706 const _Compare& __x, const _Sequence& __s)
707 : c(__s), comp(__x)
708 {
709 __glibcxx_requires_valid_range(__first, __last);
710 c.insert(c.end(), __first, __last);
711 std::make_heap(c.begin(), c.end(), comp);
712 }
713
714 template<typename _InputIterator,
715 typename = std::_RequireInputIter<_InputIterator>>
716 priority_queue(_InputIterator __first, _InputIterator __last,
717 const _Compare& __x, _Sequence&& __s)
718 : c(std::move(__s)), comp(__x)
719 {
720 __glibcxx_requires_valid_range(__first, __last);
721 c.insert(c.end(), __first, __last);
722 std::make_heap(c.begin(), c.end(), comp);
723 }
724
725 // _GLIBCXX_RESOLVE_LIB_DEFECTS
726 // 3506. Missing allocator-extended constructors for priority_queue
727 template<typename _InputIterator, typename _Alloc,
728 typename = std::_RequireInputIter<_InputIterator>,
729 typename _Requires = _Uses<_Alloc>>
730 priority_queue(_InputIterator __first, _InputIterator __last,
731 const _Alloc& __alloc)
732 : c(__first, __last, __alloc), comp()
733 { std::make_heap(c.begin(), c.end(), comp); }
734
735 template<typename _InputIterator, typename _Alloc,
736 typename = std::_RequireInputIter<_InputIterator>,
737 typename _Requires = _Uses<_Alloc>>
738 priority_queue(_InputIterator __first, _InputIterator __last,
739 const _Compare& __x, const _Alloc& __alloc)
740 : c(__first, __last, __alloc), comp(__x)
741 { std::make_heap(c.begin(), c.end(), comp); }
742
743 template<typename _InputIterator, typename _Alloc,
744 typename = std::_RequireInputIter<_InputIterator>,
745 typename _Requires = _Uses<_Alloc>>
746 priority_queue(_InputIterator __first, _InputIterator __last,
747 const _Compare& __x, const _Sequence& __s,
748 const _Alloc& __alloc)
749 : c(__s, __alloc), comp(__x)
750 {
751 __glibcxx_requires_valid_range(__first, __last);
752 c.insert(c.end(), __first, __last);
753 std::make_heap(c.begin(), c.end(), comp);
754 }
755
756 template<typename _InputIterator, typename _Alloc,
757 typename _Requires = _Uses<_Alloc>>
758 priority_queue(_InputIterator __first, _InputIterator __last,
759 const _Compare& __x, _Sequence&& __s,
760 const _Alloc& __alloc)
761 : c(std::move(__s), __alloc), comp(__x)
762 {
763 __glibcxx_requires_valid_range(__first, __last);
764 c.insert(c.end(), __first, __last);
765 std::make_heap(c.begin(), c.end(), comp);
766 }
767#endif
768
769#if __glibcxx_ranges_to_container // C++ >= 23
770 /**
771 * @brief Construct a priority_queue from a range.
772 * @since C++23
773 *
774 * @{
775 */
776 template<__detail::__container_compatible_range<_Tp> _Rg>
777 priority_queue(from_range_t, _Rg&& __rg,
778 const _Compare& __x = _Compare())
779 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg))), comp(__x)
780 { std::make_heap(c.begin(), c.end(), comp); }
781
782 template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc>
783 priority_queue(from_range_t, _Rg&& __rg, const _Compare& __x,
784 const _Alloc& __a)
785 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp(__x)
786 { std::make_heap(c.begin(), c.end(), comp); }
787
788 template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc>
789 priority_queue(from_range_t, _Rg&& __rg, const _Alloc& __a)
790 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp()
791 { std::make_heap(c.begin(), c.end(), comp); }
792 /// @}
793#endif
794
795 /**
796 * Returns true if the %queue is empty.
797 */
798 _GLIBCXX_NODISCARD bool
799 empty() const
800 { return c.empty(); }
801
802 /** Returns the number of elements in the %queue. */
803 _GLIBCXX_NODISCARD
804 size_type
805 size() const
806 { return c.size(); }
807
808 /**
809 * Returns a read-only (constant) reference to the data at the first
810 * element of the %queue.
811 */
812 _GLIBCXX_NODISCARD
813 const_reference
814 top() const
815 {
816 __glibcxx_requires_nonempty();
817 return c.front();
818 }
819
820 /**
821 * @brief Add data to the %queue.
822 * @param __x Data to be added.
823 *
824 * This is a typical %queue operation.
825 * The time complexity of the operation depends on the underlying
826 * sequence.
827 */
828 void
829 push(const value_type& __x)
830 {
831 c.push_back(__x);
832 std::push_heap(c.begin(), c.end(), comp);
833 }
834
835#if __cplusplus >= 201103L
836 void
837 push(value_type&& __x)
838 {
839 c.push_back(std::move(__x));
840 std::push_heap(c.begin(), c.end(), comp);
841 }
842
843 template<typename... _Args>
844 void
845 emplace(_Args&&... __args)
846 {
847 c.emplace_back(std::forward<_Args>(__args)...);
848 std::push_heap(c.begin(), c.end(), comp);
849 }
850#endif
851
852#if __glibcxx_ranges_to_container // C++ >= 23
853 template<__detail::__container_compatible_range<_Tp> _Rg>
854 void
855 push_range(_Rg&& __rg)
856 {
857 if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); })
858 c.append_range(std::forward<_Rg>(__rg));
859 else
860 ranges::copy(__rg, std::back_inserter(c));
861 std::make_heap(c.begin(), c.end(), comp);
862 }
863#endif
864
865 /**
866 * @brief Removes first element.
867 *
868 * This is a typical %queue operation. It shrinks the %queue
869 * by one. The time complexity of the operation depends on the
870 * underlying sequence.
871 *
872 * Note that no data is returned, and if the first element's
873 * data is needed, it should be retrieved before pop() is
874 * called.
875 */
876 void
878 {
879 __glibcxx_requires_nonempty();
880 std::pop_heap(c.begin(), c.end(), comp);
881 c.pop_back();
882 }
883
884#if __cplusplus >= 201103L
885 void
886 swap(priority_queue& __pq)
887 noexcept(__and_<
888#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
889 __is_nothrow_swappable<_Sequence>,
890#else
891 __is_nothrow_swappable<_Tp>,
892#endif
893 __is_nothrow_swappable<_Compare>
894 >::value)
895 {
896 using std::swap;
897 swap(c, __pq.c);
898 swap(comp, __pq.comp);
899 }
900#endif // __cplusplus >= 201103L
901 };
902
903#if __cpp_deduction_guides >= 201606
904 template<typename _Compare, typename _Container,
905 typename = _RequireNotAllocator<_Compare>,
906 typename = _RequireNotAllocator<_Container>>
907 priority_queue(_Compare, _Container)
908 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
909
910 template<typename _InputIterator, typename _ValT
911 = typename iterator_traits<_InputIterator>::value_type,
912 typename _Compare = less<_ValT>,
913 typename _Container = vector<_ValT>,
914 typename = _RequireInputIter<_InputIterator>,
915 typename = _RequireNotAllocator<_Compare>,
916 typename = _RequireNotAllocator<_Container>>
917 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
918 _Container = _Container())
919 -> priority_queue<_ValT, _Container, _Compare>;
920
921 template<typename _Compare, typename _Container, typename _Allocator,
922 typename = _RequireNotAllocator<_Compare>,
923 typename = _RequireNotAllocator<_Container>>
924 priority_queue(_Compare, _Container, _Allocator)
925 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
926
927#if __glibcxx_ranges_to_container // C++ >= 23
928 template<ranges::input_range _Rg,
929 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
930 __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>>
931 priority_queue(from_range_t, _Rg&&, _Compare = _Compare(),
932 _Alloc = _Alloc())
933 -> priority_queue<ranges::range_value_t<_Rg>,
934 vector<ranges::range_value_t<_Rg>, _Alloc>,
935 _Compare>;
936
937 template<ranges::input_range _Rg, __allocator_like _Alloc>
938 priority_queue(from_range_t, _Rg&&, _Alloc)
939 -> priority_queue<ranges::range_value_t<_Rg>,
940 vector<ranges::range_value_t<_Rg>, _Alloc>>;
941#endif
942#endif
943
944 // No equality/comparison operators are provided for priority_queue.
945
946#if __cplusplus >= 201103L
947 template<typename _Tp, typename _Sequence, typename _Compare>
948 inline
949#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
950 // Constrained free swap overload, see p0185r1
951 typename enable_if<__and_<__is_swappable<_Sequence>,
952 __is_swappable<_Compare>>::value>::type
953#else
954 void
955#endif
956 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
957 priority_queue<_Tp, _Sequence, _Compare>& __y)
958 noexcept(noexcept(__x.swap(__y)))
959 { __x.swap(__y); }
960
961 template<typename _Tp, typename _Sequence, typename _Compare,
962 typename _Alloc>
963 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
964 : public uses_allocator<_Sequence, _Alloc>::type { };
965#endif // __cplusplus >= 201103L
966
967_GLIBCXX_END_NAMESPACE_VERSION
968} // namespace
969
970#endif /* _STL_QUEUE_H */
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
constexpr back_insert_iterator< _Container > back_inserter(_Container &__x)
ISO C++ entities toplevel namespace is std.
typename __detail::__cmp3way_res_impl< _Tp, _Up >::type compare_three_way_result_t
[cmp.result], result of three-way comparison
Definition compare:526
Define a member typedef type only if a boolean constant is true.
Definition type_traits:134
is_default_constructible
Definition type_traits:1167
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
A standard container giving FIFO behavior.
Definition stl_queue.h:101
void push(const value_type &__x)
Add data to the end of the queue.
Definition stl_queue.h:308
_Sequence c
c is the underlying container.
Definition stl_queue.h:157
size_type size() const
Definition stl_queue.h:247
reference front()
Definition stl_queue.h:256
const_reference back() const
Definition stl_queue.h:292
void pop()
Removes first element.
Definition stl_queue.h:353
queue()
Default constructor creates no elements.
Definition stl_queue.h:170
const_reference front() const
Definition stl_queue.h:268
bool empty() const
Definition stl_queue.h:241
reference back()
Definition stl_queue.h:280
A standard container automatically sorting its contents.
Definition stl_queue.h:544
size_type size() const
Definition stl_queue.h:805
bool empty() const
Definition stl_queue.h:799
void pop()
Removes first element.
Definition stl_queue.h:877
const_reference top() const
Definition stl_queue.h:814
priority_queue(_InputIterator __first, _InputIterator __last, const _Compare &__x=_Compare())
Builds a queue from a range.
Definition stl_queue.h:696
void push(const value_type &__x)
Add data to the queue.
Definition stl_queue.h:829
priority_queue()
Default constructor creates no elements.
Definition stl_queue.h:601