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