1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_QUEUE
11#define _LIBCPP_QUEUE
12
13/*
14 queue synopsis
15
16namespace std
17{
18
19template <class T, class Container = deque<T>>
20class queue
21{
22public:
23 typedef Container container_type;
24 typedef typename container_type::value_type value_type;
25 typedef typename container_type::reference reference;
26 typedef typename container_type::const_reference const_reference;
27 typedef typename container_type::size_type size_type;
28
29protected:
30 container_type c;
31
32public:
33 queue() = default;
34 ~queue() = default;
35
36 queue(const queue& q) = default;
37 queue(queue&& q) = default;
38
39 queue& operator=(const queue& q) = default;
40 queue& operator=(queue&& q) = default;
41
42 explicit queue(const container_type& c);
43 explicit queue(container_type&& c)
44 template<class InputIterator>
45 queue(InputIterator first, InputIterator last); // since C++23
46 template<container-compatible-range<T> R> queue(from_range_t, R&& rg); // since C++23
47 template <class Alloc>
48 explicit queue(const Alloc& a);
49 template <class Alloc>
50 queue(const container_type& c, const Alloc& a);
51 template <class Alloc>
52 queue(container_type&& c, const Alloc& a);
53 template <class Alloc>
54 queue(const queue& q, const Alloc& a);
55 template <class Alloc>
56 queue(queue&& q, const Alloc& a);
57 template <class InputIterator, class Alloc>
58 queue(InputIterator first, InputIterator last, const Alloc&); // since C++23
59 template<container-compatible-range<T> R, class Alloc>
60 queue(from_range_t, R&& rg, const Alloc&); // since C++23
61
62 bool empty() const;
63 size_type size() const;
64
65 reference front();
66 const_reference front() const;
67 reference back();
68 const_reference back() const;
69
70 void push(const value_type& v);
71 void push(value_type&& v);
72 template<container-compatible-range<T> R>
73 void push_range(R&& rg); // C++23
74 template <class... Args> reference emplace(Args&&... args); // reference in C++17
75 void pop();
76
77 void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
78};
79
80template<class Container>
81 queue(Container) -> queue<typename Container::value_type, Container>; // C++17
82
83template<class InputIterator>
84 queue(InputIterator, InputIterator) -> queue<iter-value-type<InputIterator>>; // since C++23
85
86template<ranges::input_range R>
87 queue(from_range_t, R&&) -> queue<ranges::range_value_t<R>>; // since C++23
88
89template<class Container, class Allocator>
90 queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17
91
92template<class InputIterator, class Allocator>
93 queue(InputIterator, InputIterator, Allocator)
94 -> queue<iter-value-type<InputIterator>,
95 deque<iter-value-type<InputIterator>, Allocator>>; // since C++23
96
97template<ranges::input_range R, class Allocator>
98 queue(from_range_t, R&&, Allocator)
99 -> queue<ranges::range_value_t<R>, deque<ranges::range_value_t<R>, Allocator>>; // since C++23
100
101template <class T, class Container>
102 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
103
104template <class T, class Container>
105 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
106
107template <class T, class Container>
108 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
109
110template <class T, class Container>
111 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
112
113template <class T, class Container>
114 bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
115
116template <class T, class Container>
117 bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
118
119template<class T, three_way_comparable Container>
120 compare_three_way_result_t<Container>
121 operator<=>(const queue<T, Container>& x, const queue<T, Container>& y); // since C++20
122
123template <class T, class Container>
124 void swap(queue<T, Container>& x, queue<T, Container>& y)
125 noexcept(noexcept(x.swap(y)));
126
127template <class T, class Container = vector<T>,
128 class Compare = less<typename Container::value_type>>
129class priority_queue
130{
131public:
132 typedef Container container_type;
133 typedef typename container_type::value_type value_type;
134 typedef typename container_type::reference reference;
135 typedef typename container_type::const_reference const_reference;
136 typedef typename container_type::size_type size_type;
137
138protected:
139 container_type c;
140 Compare comp;
141
142public:
143 priority_queue() : priority_queue(Compare()) {} // C++20
144 explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
145 priority_queue(const Compare& x, const Container&);
146 explicit priority_queue(const Compare& x = Compare(), Container&& = Container()); // before C++20
147 priority_queue(const Compare& x, Container&&); // C++20
148 template <class InputIterator>
149 priority_queue(InputIterator first, InputIterator last,
150 const Compare& comp = Compare());
151 template <class InputIterator>
152 priority_queue(InputIterator first, InputIterator last,
153 const Compare& comp, const Container& c);
154 template <class InputIterator>
155 priority_queue(InputIterator first, InputIterator last,
156 const Compare& comp, Container&& c);
157 template <container-compatible-range<T> R>
158 priority_queue(from_range_t, R&& rg, const Compare& x = Compare()); // since C++23
159 template <class Alloc>
160 explicit priority_queue(const Alloc& a);
161 template <class Alloc>
162 priority_queue(const Compare& comp, const Alloc& a);
163 template <class Alloc>
164 priority_queue(const Compare& comp, const Container& c,
165 const Alloc& a);
166 template <class Alloc>
167 priority_queue(const Compare& comp, Container&& c,
168 const Alloc& a);
169 template <class InputIterator>
170 priority_queue(InputIterator first, InputIterator last,
171 const Alloc& a);
172 template <class InputIterator>
173 priority_queue(InputIterator first, InputIterator last,
174 const Compare& comp, const Alloc& a);
175 template <class InputIterator>
176 priority_queue(InputIterator first, InputIterator last,
177 const Compare& comp, const Container& c, const Alloc& a);
178 template <class InputIterator>
179 priority_queue(InputIterator first, InputIterator last,
180 const Compare& comp, Container&& c, const Alloc& a);
181 template <container-compatible-range<T> R, class Alloc>
182 priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&); // since C++23
183 template <container-compatible-range<T> R, class Alloc>
184 priority_queue(from_range_t, R&& rg, const Alloc&); // since C++23
185 template <class Alloc>
186 priority_queue(const priority_queue& q, const Alloc& a);
187 template <class Alloc>
188 priority_queue(priority_queue&& q, const Alloc& a);
189
190 bool empty() const;
191 size_type size() const;
192 const_reference top() const;
193
194 void push(const value_type& v);
195 void push(value_type&& v);
196 template<container-compatible-range<T> R>
197 void push_range(R&& rg); // C++23
198 template <class... Args> void emplace(Args&&... args);
199 void pop();
200
201 void swap(priority_queue& q)
202 noexcept(is_nothrow_swappable_v<Container> &&
203 is_nothrow_swappable_v<Comp>)
204};
205
206template <class Compare, class Container>
207priority_queue(Compare, Container)
208 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
209
210template<class InputIterator,
211 class Compare = less<iter-value-type<InputIterator>>,
212 class Container = vector<iter-value-type<InputIterator>>>
213priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
214 -> priority_queue<iter-value-type<InputIterator>, Container, Compare>; // C++17
215
216template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>>
217 priority_queue(from_range_t, R&&, Compare = Compare())
218 -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>>, Compare>; // C++23
219
220template<class Compare, class Container, class Allocator>
221priority_queue(Compare, Container, Allocator)
222 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
223
224template<class InputIterator, class Allocator>
225priority_queue(InputIterator, InputIterator, Allocator)
226 -> priority_queue<iter-value-type<InputIterator>,
227 vector<iter-value-type<InputIterator>, Allocator>,
228 less<iter-value-type<InputIterator>>>; // C++17
229
230template<class InputIterator, class Compare, class Allocator>
231priority_queue(InputIterator, InputIterator, Compare, Allocator)
232 -> priority_queue<iter-value-type<InputIterator>,
233 vector<iter-value-type<InputIterator>, Allocator>, Compare>; // C++17
234
235template<class InputIterator, class Compare, class Container, class Allocator>
236priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
237 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
238
239template<ranges::input_range R, class Compare, class Allocator>
240 priority_queue(from_range_t, R&&, Compare, Allocator)
241 -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>,
242 Compare>; // C++23
243
244template<ranges::input_range R, class Allocator>
245 priority_queue(from_range_t, R&&, Allocator)
246 -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>>; // C++23
247
248template <class T, class Container, class Compare>
249 void swap(priority_queue<T, Container, Compare>& x,
250 priority_queue<T, Container, Compare>& y)
251 noexcept(noexcept(x.swap(y)));
252
253} // std
254
255*/
256
257#include <__algorithm/make_heap.h>
258#include <__algorithm/pop_heap.h>
259#include <__algorithm/push_heap.h>
260#include <__algorithm/ranges_copy.h>
261#include <__config>
262#include <__functional/operations.h>
263#include <__fwd/deque.h>
264#include <__fwd/queue.h>
265#include <__iterator/back_insert_iterator.h>
266#include <__iterator/iterator_traits.h>
267#include <__memory/uses_allocator.h>
268#include <__ranges/access.h>
269#include <__ranges/concepts.h>
270#include <__ranges/container_compatible_range.h>
271#include <__ranges/from_range.h>
272#include <__utility/forward.h>
273#include <deque>
274#include <vector>
275#include <version>
276
277// standard-mandated includes
278
279// [queue.syn]
280#include <compare>
281#include <initializer_list>
282
283#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
284# pragma GCC system_header
285#endif
286
287_LIBCPP_PUSH_MACROS
288#include <__undef_macros>
289
290_LIBCPP_BEGIN_NAMESPACE_STD
291
292template <class _Tp, class _Container>
293_LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
294
295template <class _Tp, class _Container>
296_LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
297
298template <class _Tp, class _Container /*= deque<_Tp>*/>
299class _LIBCPP_TEMPLATE_VIS queue {
300public:
301 typedef _Container container_type;
302 typedef typename container_type::value_type value_type;
303 typedef typename container_type::reference reference;
304 typedef typename container_type::const_reference const_reference;
305 typedef typename container_type::size_type size_type;
306 static_assert(is_same<_Tp, value_type>::value, "");
307
308protected:
309 container_type c;
310
311public:
312 _LIBCPP_HIDE_FROM_ABI queue() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {}
313
314 _LIBCPP_HIDE_FROM_ABI queue(const queue& __q) : c(__q.c) {}
315
316#if _LIBCPP_STD_VER >= 23
317 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
318 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
319
320 template <_ContainerCompatibleRange<_Tp> _Range>
321 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}
322
323 template <class _InputIterator,
324 class _Alloc,
325 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
326 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
327 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc)
328 : c(__first, __second, __alloc) {}
329
330 template <_ContainerCompatibleRange<_Tp> _Range,
331 class _Alloc,
332 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
333 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range, const _Alloc& __alloc)
334 : c(from_range, std::forward<_Range>(__range), __alloc) {}
335
336#endif
337
338 _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) {
339 c = __q.c;
340 return *this;
341 }
342
343#ifndef _LIBCPP_CXX03_LANG
344 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q) noexcept(is_nothrow_move_constructible<container_type>::value)
345 : c(std::move(__q.c)) {}
346
347 _LIBCPP_HIDE_FROM_ABI queue& operator=(queue&& __q) noexcept(is_nothrow_move_assignable<container_type>::value) {
348 c = std::move(__q.c);
349 return *this;
350 }
351#endif // _LIBCPP_CXX03_LANG
352
353 _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {}
354#ifndef _LIBCPP_CXX03_LANG
355 _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {}
356#endif // _LIBCPP_CXX03_LANG
357
358 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
359 _LIBCPP_HIDE_FROM_ABI explicit queue(const _Alloc& __a) : c(__a) {}
360
361 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
362 _LIBCPP_HIDE_FROM_ABI queue(const queue& __q, const _Alloc& __a) : c(__q.c, __a) {}
363
364 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
365 _LIBCPP_HIDE_FROM_ABI queue(const container_type& __c, const _Alloc& __a) : c(__c, __a) {}
366
367#ifndef _LIBCPP_CXX03_LANG
368 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
369 _LIBCPP_HIDE_FROM_ABI queue(container_type&& __c, const _Alloc& __a) : c(std::move(__c), __a) {}
370
371 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
372 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q, const _Alloc& __a) : c(std::move(__q.c), __a) {}
373#endif // _LIBCPP_CXX03_LANG
374
375 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
376 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
377
378 _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); }
379 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); }
380 _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); }
381 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return c.back(); }
382
383 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); }
384#ifndef _LIBCPP_CXX03_LANG
385 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); }
386
387# if _LIBCPP_STD_VER >= 23
388 template <_ContainerCompatibleRange<_Tp> _Range>
389 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
390 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
391 c.append_range(std::forward<_Range>(__range));
392 } else {
393 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
394 }
395 }
396# endif
397
398 template <class... _Args>
399 _LIBCPP_HIDE_FROM_ABI
400# if _LIBCPP_STD_VER >= 17
401 decltype(auto)
402 emplace(_Args&&... __args) {
403 return c.emplace_back(std::forward<_Args>(__args)...);
404 }
405# else
406 void
407 emplace(_Args&&... __args) {
408 c.emplace_back(std::forward<_Args>(__args)...);
409 }
410# endif
411#endif // _LIBCPP_CXX03_LANG
412 _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_front(); }
413
414 _LIBCPP_HIDE_FROM_ABI void swap(queue& __q) _NOEXCEPT_(__is_nothrow_swappable_v<container_type>) {
415 using std::swap;
416 swap(c, __q.c);
417 }
418
419 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
420
421 template <class _T1, class _OtherContainer>
422 friend _LIBCPP_HIDE_FROM_ABI bool
423 operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
424
425 template <class _T1, class _OtherContainer>
426 friend _LIBCPP_HIDE_FROM_ABI bool
427 operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
428};
429
430#if _LIBCPP_STD_VER >= 17
431template <class _Container, class = enable_if_t<!__is_allocator<_Container>::value> >
432queue(_Container) -> queue<typename _Container::value_type, _Container>;
433
434template <class _Container,
435 class _Alloc,
436 class = enable_if_t<!__is_allocator<_Container>::value>,
437 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
438queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>;
439#endif
440
441#if _LIBCPP_STD_VER >= 23
442template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
443queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>;
444
445template <ranges::input_range _Range>
446queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>;
447
448template <class _InputIterator,
449 class _Alloc,
450 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
451 __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
452queue(_InputIterator,
453 _InputIterator,
454 _Alloc) -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
455
456template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
457queue(from_range_t,
458 _Range&&,
459 _Alloc) -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;
460#endif
461
462template <class _Tp, class _Container>
463inline _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
464 return __x.c == __y.c;
465}
466
467template <class _Tp, class _Container>
468inline _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
469 return __x.c < __y.c;
470}
471
472template <class _Tp, class _Container>
473inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
474 return !(__x == __y);
475}
476
477template <class _Tp, class _Container>
478inline _LIBCPP_HIDE_FROM_ABI bool operator>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
479 return __y < __x;
480}
481
482template <class _Tp, class _Container>
483inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
484 return !(__x < __y);
485}
486
487template <class _Tp, class _Container>
488inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
489 return !(__y < __x);
490}
491
492#if _LIBCPP_STD_VER >= 20
493
494template <class _Tp, three_way_comparable _Container>
495_LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>
496operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
497 // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors
498 return __x.__get_container() <=> __y.__get_container();
499}
500
501#endif
502
503template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0>
504inline _LIBCPP_HIDE_FROM_ABI void swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
505 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
506 __x.swap(__y);
507}
508
509template <class _Tp, class _Container, class _Alloc>
510struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> {
511};
512
513template <class _Tp, class _Container, class _Compare>
514class _LIBCPP_TEMPLATE_VIS priority_queue {
515public:
516 typedef _Container container_type;
517 typedef _Compare value_compare;
518 typedef typename container_type::value_type value_type;
519 typedef typename container_type::reference reference;
520 typedef typename container_type::const_reference const_reference;
521 typedef typename container_type::size_type size_type;
522 static_assert(is_same<_Tp, value_type>::value, "");
523
524protected:
525 container_type c;
526 value_compare comp;
527
528public:
529 _LIBCPP_HIDE_FROM_ABI priority_queue() _NOEXCEPT_(
530 is_nothrow_default_constructible<container_type>::value&& is_nothrow_default_constructible<value_compare>::value)
531 : c(), comp() {}
532
533 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
534
535 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(const priority_queue& __q) {
536 c = __q.c;
537 comp = __q.comp;
538 return *this;
539 }
540
541#ifndef _LIBCPP_CXX03_LANG
542 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q) noexcept(
543 is_nothrow_move_constructible<container_type>::value && is_nothrow_move_constructible<value_compare>::value)
544 : c(std::move(__q.c)), comp(std::move(__q.comp)) {}
545
546 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(priority_queue&& __q) noexcept(
547 is_nothrow_move_assignable<container_type>::value && is_nothrow_move_assignable<value_compare>::value) {
548 c = std::move(__q.c);
549 comp = std::move(__q.comp);
550 return *this;
551 }
552#endif // _LIBCPP_CXX03_LANG
553
554 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const value_compare& __comp) : c(), comp(__comp) {}
555 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c);
556#ifndef _LIBCPP_CXX03_LANG
557 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c);
558#endif
559 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
560 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare());
561
562 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
563 _LIBCPP_HIDE_FROM_ABI
564 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c);
565
566#ifndef _LIBCPP_CXX03_LANG
567 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
568 _LIBCPP_HIDE_FROM_ABI
569 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c);
570#endif // _LIBCPP_CXX03_LANG
571
572#if _LIBCPP_STD_VER >= 23
573 template <_ContainerCompatibleRange<_Tp> _Range>
574 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare())
575 : c(from_range, std::forward<_Range>(__range)), comp(__comp) {
576 std::make_heap(c.begin(), c.end(), comp);
577 }
578#endif
579
580 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
581 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const _Alloc& __a);
582
583 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
584 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const _Alloc& __a);
585
586 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
587 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c, const _Alloc& __a);
588
589 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
590 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q, const _Alloc& __a);
591
592#ifndef _LIBCPP_CXX03_LANG
593 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
594 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c, const _Alloc& __a);
595
596 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
597 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q, const _Alloc& __a);
598#endif // _LIBCPP_CXX03_LANG
599
600 template <
601 class _InputIter,
602 class _Alloc,
603 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
604 int> = 0>
605 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a);
606
607 template <
608 class _InputIter,
609 class _Alloc,
610 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
611 int> = 0>
612 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a);
613
614 template <
615 class _InputIter,
616 class _Alloc,
617 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
618 int> = 0>
619 _LIBCPP_HIDE_FROM_ABI priority_queue(
620 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a);
621
622#ifndef _LIBCPP_CXX03_LANG
623 template <
624 class _InputIter,
625 class _Alloc,
626 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
627 int> = 0>
628 _LIBCPP_HIDE_FROM_ABI
629 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a);
630#endif // _LIBCPP_CXX03_LANG
631
632#if _LIBCPP_STD_VER >= 23
633
634 template <_ContainerCompatibleRange<_Tp> _Range,
635 class _Alloc,
636 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
637 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a)
638 : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) {
639 std::make_heap(c.begin(), c.end(), comp);
640 }
641
642 template <_ContainerCompatibleRange<_Tp> _Range,
643 class _Alloc,
644 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
645 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a)
646 : c(from_range, std::forward<_Range>(__range), __a), comp() {
647 std::make_heap(c.begin(), c.end(), comp);
648 }
649
650#endif
651
652 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
653 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
654 _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.front(); }
655
656 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v);
657#ifndef _LIBCPP_CXX03_LANG
658 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v);
659
660# if _LIBCPP_STD_VER >= 23
661 template <_ContainerCompatibleRange<_Tp> _Range>
662 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
663 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
664 c.append_range(std::forward<_Range>(__range));
665 } else {
666 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
667 }
668
669 std::make_heap(c.begin(), c.end(), comp);
670 }
671# endif
672
673 template <class... _Args>
674 _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args);
675#endif // _LIBCPP_CXX03_LANG
676 _LIBCPP_HIDE_FROM_ABI void pop();
677
678 _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q)
679 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>);
680
681 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
682};
683
684#if _LIBCPP_STD_VER >= 17
685template <class _Compare,
686 class _Container,
687 class = enable_if_t<!__is_allocator<_Compare>::value>,
688 class = enable_if_t<!__is_allocator<_Container>::value> >
689priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
690
691template <class _InputIterator,
692 class _Compare = less<__iter_value_type<_InputIterator>>,
693 class _Container = vector<__iter_value_type<_InputIterator>>,
694 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
695 class = enable_if_t<!__is_allocator<_Compare>::value>,
696 class = enable_if_t<!__is_allocator<_Container>::value> >
697priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
698 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
699
700template <class _Compare,
701 class _Container,
702 class _Alloc,
703 class = enable_if_t<!__is_allocator<_Compare>::value>,
704 class = enable_if_t<!__is_allocator<_Container>::value>,
705 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
706priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
707
708template <class _InputIterator,
709 class _Allocator,
710 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
711 class = enable_if_t<__is_allocator<_Allocator>::value> >
712priority_queue(_InputIterator, _InputIterator, _Allocator)
713 -> priority_queue<__iter_value_type<_InputIterator>,
714 vector<__iter_value_type<_InputIterator>, _Allocator>,
715 less<__iter_value_type<_InputIterator>>>;
716
717template <class _InputIterator,
718 class _Compare,
719 class _Allocator,
720 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
721 class = enable_if_t<!__is_allocator<_Compare>::value>,
722 class = enable_if_t<__is_allocator<_Allocator>::value> >
723priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
724 -> priority_queue<__iter_value_type<_InputIterator>,
725 vector<__iter_value_type<_InputIterator>, _Allocator>,
726 _Compare>;
727
728template <class _InputIterator,
729 class _Compare,
730 class _Container,
731 class _Alloc,
732 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
733 class = enable_if_t<!__is_allocator<_Compare>::value>,
734 class = enable_if_t<!__is_allocator<_Container>::value>,
735 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
736priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
737 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
738#endif
739
740#if _LIBCPP_STD_VER >= 23
741
742template <ranges::input_range _Range,
743 class _Compare = less<ranges::range_value_t<_Range>>,
744 class = enable_if_t<!__is_allocator<_Compare>::value>>
745priority_queue(from_range_t, _Range&&, _Compare = _Compare())
746 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>;
747
748template <ranges::input_range _Range,
749 class _Compare,
750 class _Alloc,
751 class = enable_if_t<!__is_allocator<_Compare>::value>,
752 class = enable_if_t<__is_allocator<_Alloc>::value>>
753priority_queue(from_range_t, _Range&&, _Compare, _Alloc)
754 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>;
755
756template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator<_Alloc>::value>>
757priority_queue(from_range_t, _Range&&, _Alloc)
758 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>;
759
760#endif
761
762template <class _Tp, class _Container, class _Compare>
763inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, const container_type& __c)
764 : c(__c), comp(__comp) {
765 std::make_heap(c.begin(), c.end(), comp);
766}
767
768#ifndef _LIBCPP_CXX03_LANG
769
770template <class _Tp, class _Container, class _Compare>
771inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, container_type&& __c)
772 : c(std::move(__c)), comp(__comp) {
773 std::make_heap(c.begin(), c.end(), comp);
774}
775
776#endif // _LIBCPP_CXX03_LANG
777
778template <class _Tp, class _Container, class _Compare>
779template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
780inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
781 _InputIter __f, _InputIter __l, const value_compare& __comp)
782 : c(__f, __l), comp(__comp) {
783 std::make_heap(c.begin(), c.end(), comp);
784}
785
786template <class _Tp, class _Container, class _Compare>
787template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
788inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
789 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c)
790 : c(__c), comp(__comp) {
791 c.insert(c.end(), __f, __l);
792 std::make_heap(c.begin(), c.end(), comp);
793}
794
795#ifndef _LIBCPP_CXX03_LANG
796
797template <class _Tp, class _Container, class _Compare>
798template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
799inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
800 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c)
801 : c(std::move(__c)), comp(__comp) {
802 c.insert(c.end(), __f, __l);
803 std::make_heap(c.begin(), c.end(), comp);
804}
805
806#endif // _LIBCPP_CXX03_LANG
807
808template <class _Tp, class _Container, class _Compare>
809template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
810inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a) : c(__a) {}
811
812template <class _Tp, class _Container, class _Compare>
813template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
814inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, const _Alloc& __a)
815 : c(__a), comp(__comp) {}
816
817template <class _Tp, class _Container, class _Compare>
818template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
819inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
820 const value_compare& __comp, const container_type& __c, const _Alloc& __a)
821 : c(__c, __a), comp(__comp) {
822 std::make_heap(c.begin(), c.end(), comp);
823}
824
825template <class _Tp, class _Container, class _Compare>
826template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
827inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, const _Alloc& __a)
828 : c(__q.c, __a), comp(__q.comp) {}
829
830#ifndef _LIBCPP_CXX03_LANG
831
832template <class _Tp, class _Container, class _Compare>
833template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
834inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
835 const value_compare& __comp, container_type&& __c, const _Alloc& __a)
836 : c(std::move(__c), __a), comp(__comp) {
837 std::make_heap(c.begin(), c.end(), comp);
838}
839
840template <class _Tp, class _Container, class _Compare>
841template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
842inline priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, const _Alloc& __a)
843 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {}
844
845#endif // _LIBCPP_CXX03_LANG
846
847template <class _Tp, class _Container, class _Compare>
848template <
849 class _InputIter,
850 class _Alloc,
851 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
852inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a)
853 : c(__f, __l, __a), comp() {
854 std::make_heap(c.begin(), c.end(), comp);
855}
856
857template <class _Tp, class _Container, class _Compare>
858template <
859 class _InputIter,
860 class _Alloc,
861 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
862inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
863 _InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a)
864 : c(__f, __l, __a), comp(__comp) {
865 std::make_heap(c.begin(), c.end(), comp);
866}
867
868template <class _Tp, class _Container, class _Compare>
869template <
870 class _InputIter,
871 class _Alloc,
872 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
873inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
874 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a)
875 : c(__c, __a), comp(__comp) {
876 c.insert(c.end(), __f, __l);
877 std::make_heap(c.begin(), c.end(), comp);
878}
879
880#ifndef _LIBCPP_CXX03_LANG
881template <class _Tp, class _Container, class _Compare>
882template <
883 class _InputIter,
884 class _Alloc,
885 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
886inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
887 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a)
888 : c(std::move(__c), __a), comp(__comp) {
889 c.insert(c.end(), __f, __l);
890 std::make_heap(c.begin(), c.end(), comp);
891}
892#endif // _LIBCPP_CXX03_LANG
893
894template <class _Tp, class _Container, class _Compare>
895inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) {
896 c.push_back(__v);
897 std::push_heap(c.begin(), c.end(), comp);
898}
899
900#ifndef _LIBCPP_CXX03_LANG
901
902template <class _Tp, class _Container, class _Compare>
903inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) {
904 c.push_back(std::move(__v));
905 std::push_heap(c.begin(), c.end(), comp);
906}
907
908template <class _Tp, class _Container, class _Compare>
909template <class... _Args>
910inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) {
911 c.emplace_back(std::forward<_Args>(__args)...);
912 std::push_heap(c.begin(), c.end(), comp);
913}
914
915#endif // _LIBCPP_CXX03_LANG
916
917template <class _Tp, class _Container, class _Compare>
918inline void priority_queue<_Tp, _Container, _Compare>::pop() {
919 std::pop_heap(c.begin(), c.end(), comp);
920 c.pop_back();
921}
922
923template <class _Tp, class _Container, class _Compare>
924inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
925 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>) {
926 using std::swap;
927 swap(c, __q.c);
928 swap(comp, __q.comp);
929}
930
931template <class _Tp,
932 class _Container,
933 class _Compare,
934 __enable_if_t<__is_swappable_v<_Container> && __is_swappable_v<_Compare>, int> = 0>
935inline _LIBCPP_HIDE_FROM_ABI void
936swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y)
937 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
938 __x.swap(__y);
939}
940
941template <class _Tp, class _Container, class _Compare, class _Alloc>
942struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
943 : public uses_allocator<_Container, _Alloc> {};
944
945_LIBCPP_END_NAMESPACE_STD
946
947_LIBCPP_POP_MACROS
948
949#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
950# include <concepts>
951# include <cstdlib>
952# include <functional>
953# include <type_traits>
954#endif
955
956#endif // _LIBCPP_QUEUE
957