982 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP_QUEUE11#define _LIBCPP_QUEUE12 13/*14 queue synopsis15 16namespace std17{18 19template <class T, class Container = deque<T>>20class queue21{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++2346 template<container-compatible-range<T> R> queue(from_range_t, R&& rg); // since C++2347 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++2359 template<container-compatible-range<T> R, class Alloc>60 queue(from_range_t, R&& rg, const Alloc&); // since C++2361 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++2374 template <class... Args> reference emplace(Args&&... args); // reference in C++1775 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++1782 83template<class InputIterator>84 queue(InputIterator, InputIterator) -> queue<iter-value-type<InputIterator>>; // since C++2385 86template<ranges::input_range R>87 queue(from_range_t, R&&) -> queue<ranges::range_value_t<R>>; // since C++2388 89template<class Container, class Allocator>90 queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++1791 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++2396 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++23100 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++20122 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_queue130{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++20144 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++20147 priority_queue(const Compare& x, Container&&); // C++20148 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++23159 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++23183 template <container-compatible-range<T> R, class Alloc>184 priority_queue(from_range_t, R&& rg, const Alloc&); // since C++23185 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++23198 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++17209 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++17215 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++23219 220template<class Compare, class Container, class Allocator>221priority_queue(Compare, Container, Allocator)222 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17223 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++17229 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++17234 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++17238 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++23243 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++23247 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} // std254 255*/256 257#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)258# include <__cxx03/queue>259#else260# include <__algorithm/make_heap.h>261# include <__algorithm/pop_heap.h>262# include <__algorithm/push_heap.h>263# include <__algorithm/ranges_copy.h>264# include <__config>265# include <__functional/operations.h>266# include <__fwd/deque.h>267# include <__fwd/queue.h>268# include <__iterator/back_insert_iterator.h>269# include <__iterator/iterator_traits.h>270# include <__memory/uses_allocator.h>271# include <__ranges/access.h>272# include <__ranges/concepts.h>273# include <__ranges/container_compatible_range.h>274# include <__ranges/from_range.h>275# include <__utility/forward.h>276# include <deque>277# include <vector>278# include <version>279 280// standard-mandated includes281 282// [queue.syn]283# include <compare>284# include <initializer_list>285 286# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)287# pragma GCC system_header288# endif289 290_LIBCPP_PUSH_MACROS291# include <__undef_macros>292 293_LIBCPP_BEGIN_NAMESPACE_STD294 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>299_LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);300 301template <class _Tp, class _Container /*= deque<_Tp>*/>302class queue {303public:304 typedef _Container container_type;305 typedef typename container_type::value_type value_type;306 typedef typename container_type::reference reference;307 typedef typename container_type::const_reference const_reference;308 typedef typename container_type::size_type size_type;309 static_assert(is_same<_Tp, value_type>::value, "");310 311protected:312 container_type c;313 314public:315 _LIBCPP_HIDE_FROM_ABI queue() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {}316 317 _LIBCPP_HIDE_FROM_ABI queue(const queue& __q) : c(__q.c) {}318 319# if _LIBCPP_STD_VER >= 23320 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>321 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}322 323 template <_ContainerCompatibleRange<_Tp> _Range>324 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}325 326 template <class _InputIterator,327 class _Alloc,328 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,329 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>330 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc)331 : c(__first, __second, __alloc) {}332 333 template <_ContainerCompatibleRange<_Tp> _Range,334 class _Alloc,335 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>336 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range, const _Alloc& __alloc)337 : c(from_range, std::forward<_Range>(__range), __alloc) {}338 339# endif340 341 _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) {342 c = __q.c;343 return *this;344 }345 346# ifndef _LIBCPP_CXX03_LANG347 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q) noexcept(is_nothrow_move_constructible<container_type>::value)348 : c(std::move(__q.c)) {}349 350 _LIBCPP_HIDE_FROM_ABI queue& operator=(queue&& __q) noexcept(is_nothrow_move_assignable<container_type>::value) {351 c = std::move(__q.c);352 return *this;353 }354# endif // _LIBCPP_CXX03_LANG355 356 _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {}357# ifndef _LIBCPP_CXX03_LANG358 _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {}359# endif // _LIBCPP_CXX03_LANG360 361 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>362 _LIBCPP_HIDE_FROM_ABI explicit queue(const _Alloc& __a) : 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 queue& __q, const _Alloc& __a) : c(__q.c, __a) {}366 367 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>368 _LIBCPP_HIDE_FROM_ABI queue(const container_type& __c, const _Alloc& __a) : c(__c, __a) {}369 370# ifndef _LIBCPP_CXX03_LANG371 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>372 _LIBCPP_HIDE_FROM_ABI queue(container_type&& __c, const _Alloc& __a) : c(std::move(__c), __a) {}373 374 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>375 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q, const _Alloc& __a) : c(std::move(__q.c), __a) {}376# endif // _LIBCPP_CXX03_LANG377 378 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }379 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }380 381 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); }382 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); }383 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); }384 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reference back() const { return c.back(); }385 386 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); }387# ifndef _LIBCPP_CXX03_LANG388 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); }389 390# if _LIBCPP_STD_VER >= 23391 template <_ContainerCompatibleRange<_Tp> _Range>392 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {393 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {394 c.append_range(std::forward<_Range>(__range));395 } else {396 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));397 }398 }399# endif400 401 template <class... _Args>402 _LIBCPP_HIDE_FROM_ABI403# if _LIBCPP_STD_VER >= 17404 decltype(auto)405 emplace(_Args&&... __args) {406 return c.emplace_back(std::forward<_Args>(__args)...);407 }408# else409 void410 emplace(_Args&&... __args) {411 c.emplace_back(std::forward<_Args>(__args)...);412 }413# endif414# endif // _LIBCPP_CXX03_LANG415 _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_front(); }416 417 _LIBCPP_HIDE_FROM_ABI void swap(queue& __q) _NOEXCEPT_(__is_nothrow_swappable_v<container_type>) {418 using std::swap;419 swap(c, __q.c);420 }421 422 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }423 424 template <class _T1, class _OtherContainer>425 friend _LIBCPP_HIDE_FROM_ABI bool426 operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);427 428 template <class _T1, class _OtherContainer>429 friend _LIBCPP_HIDE_FROM_ABI bool430 operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);431 432# if _LIBCPP_STD_VER >= 20433 template <class _T1, three_way_comparable _OtherContainer>434 friend _LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_OtherContainer>435 operator<=>(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);436# endif437};438 439# if _LIBCPP_STD_VER >= 17440template <class _Container, class = enable_if_t<!__is_allocator_v<_Container>>>441queue(_Container) -> queue<typename _Container::value_type, _Container>;442 443template <class _Container,444 class _Alloc,445 class = enable_if_t<!__is_allocator_v<_Container>>,446 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >447queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>;448# endif449 450# if _LIBCPP_STD_VER >= 23451template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>452queue(_InputIterator, _InputIterator) -> queue<__iterator_value_type<_InputIterator>>;453 454template <ranges::input_range _Range>455queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>;456 457template <class _InputIterator,458 class _Alloc,459 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,460 __enable_if_t<__is_allocator_v<_Alloc>, int> = 0>461queue(_InputIterator, _InputIterator, _Alloc)462 -> queue<__iterator_value_type<_InputIterator>, deque<__iterator_value_type<_InputIterator>, _Alloc>>;463 464template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator_v<_Alloc>, int> = 0>465queue(from_range_t, _Range&&, _Alloc)466 -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;467# endif468 469template <class _Tp, class _Container>470inline _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {471 return __x.c == __y.c;472}473 474template <class _Tp, class _Container>475inline _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {476 return __x.c < __y.c;477}478 479template <class _Tp, class _Container>480inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {481 return !(__x == __y);482}483 484template <class _Tp, class _Container>485inline _LIBCPP_HIDE_FROM_ABI bool operator>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {486 return __y < __x;487}488 489template <class _Tp, class _Container>490inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {491 return !(__x < __y);492}493 494template <class _Tp, class _Container>495inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {496 return !(__y < __x);497}498 499# if _LIBCPP_STD_VER >= 20500 501template <class _Tp, three_way_comparable _Container>502_LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>503operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {504 return __x.c <=> __y.c;505}506 507# endif508 509template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0>510inline _LIBCPP_HIDE_FROM_ABI void swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)511 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {512 __x.swap(__y);513}514 515template <class _Tp, class _Container, class _Alloc>516struct uses_allocator<queue<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> {};517 518template <class _Tp, class _Container, class _Compare>519class priority_queue {520public:521 typedef _Container container_type;522 typedef _Compare value_compare;523 typedef typename container_type::value_type value_type;524 typedef typename container_type::reference reference;525 typedef typename container_type::const_reference const_reference;526 typedef typename container_type::size_type size_type;527 static_assert(is_same<_Tp, value_type>::value, "");528 529protected:530 container_type c;531 value_compare comp;532 533public:534 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue() _NOEXCEPT_(535 is_nothrow_default_constructible<container_type>::value&& is_nothrow_default_constructible<value_compare>::value)536 : c(), comp() {}537 538 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q)539 : c(__q.c), comp(__q.comp) {}540 541 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(const priority_queue& __q) {542 c = __q.c;543 comp = __q.comp;544 return *this;545 }546 547# ifndef _LIBCPP_CXX03_LANG548 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q) noexcept(549 is_nothrow_move_constructible<container_type>::value && is_nothrow_move_constructible<value_compare>::value)550 : c(std::move(__q.c)), comp(std::move(__q.comp)) {}551 552 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(priority_queue&& __q) noexcept(553 is_nothrow_move_assignable<container_type>::value && is_nothrow_move_assignable<value_compare>::value) {554 c = std::move(__q.c);555 comp = std::move(__q.comp);556 return *this;557 }558# endif // _LIBCPP_CXX03_LANG559 560 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const value_compare& __comp)561 : c(), comp(__comp) {}562 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI563 priority_queue(const value_compare& __comp, const container_type& __c);564# ifndef _LIBCPP_CXX03_LANG565 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c);566# endif567 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>568 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI569 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare());570 571 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>572 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI573 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c);574 575# ifndef _LIBCPP_CXX03_LANG576 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>577 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI578 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c);579# endif // _LIBCPP_CXX03_LANG580 581# if _LIBCPP_STD_VER >= 23582 template <_ContainerCompatibleRange<_Tp> _Range>583 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI584 priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare())585 : c(from_range, std::forward<_Range>(__range)), comp(__comp) {586 std::make_heap(c.begin(), c.end(), comp);587 }588# endif589 590 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>591 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const _Alloc& __a);592 593 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>594 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const _Alloc& __a);595 596 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>597 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI598 priority_queue(const value_compare& __comp, const container_type& __c, const _Alloc& __a);599 600 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>601 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q, const _Alloc& __a);602 603# ifndef _LIBCPP_CXX03_LANG604 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>605 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI606 priority_queue(const value_compare& __comp, container_type&& __c, const _Alloc& __a);607 608 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>609 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q, const _Alloc& __a);610# endif // _LIBCPP_CXX03_LANG611 612 template <613 class _InputIter,614 class _Alloc,615 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,616 int> = 0>617 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a);618 619 template <620 class _InputIter,621 class _Alloc,622 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,623 int> = 0>624 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI625 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a);626 627 template <628 class _InputIter,629 class _Alloc,630 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,631 int> = 0>632 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(633 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a);634 635# ifndef _LIBCPP_CXX03_LANG636 template <637 class _InputIter,638 class _Alloc,639 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,640 int> = 0>641 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI642 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a);643# endif // _LIBCPP_CXX03_LANG644 645# if _LIBCPP_STD_VER >= 23646 647 template <_ContainerCompatibleRange<_Tp> _Range,648 class _Alloc,649 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>650 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI651 priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a)652 : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) {653 std::make_heap(c.begin(), c.end(), comp);654 }655 656 template <_ContainerCompatibleRange<_Tp> _Range,657 class _Alloc,658 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>659 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a)660 : c(from_range, std::forward<_Range>(__range), __a), comp() {661 std::make_heap(c.begin(), c.end(), comp);662 }663 664# endif665 666 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }667 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }668 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const_reference top() const {669 return c.front();670 }671 672 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v);673# ifndef _LIBCPP_CXX03_LANG674 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v);675 676# if _LIBCPP_STD_VER >= 23677 template <_ContainerCompatibleRange<_Tp> _Range>678 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {679 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {680 c.append_range(std::forward<_Range>(__range));681 } else {682 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));683 }684 685 std::make_heap(c.begin(), c.end(), comp);686 }687# endif688 689 template <class... _Args>690 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args);691# endif // _LIBCPP_CXX03_LANG692 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void pop();693 694 _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q)695 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>);696 697 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX26 _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const {698 return c;699 }700};701 702# if _LIBCPP_STD_VER >= 17703template <class _Compare,704 class _Container,705 class = enable_if_t<!__is_allocator_v<_Compare>>,706 class = enable_if_t<!__is_allocator_v<_Container>>>707priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>;708 709template <class _InputIterator,710 class _Compare = less<__iterator_value_type<_InputIterator>>,711 class _Container = vector<__iterator_value_type<_InputIterator>>,712 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,713 class = enable_if_t<!__is_allocator_v<_Compare>>,714 class = enable_if_t<!__is_allocator_v<_Container>>>715priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())716 -> priority_queue<__iterator_value_type<_InputIterator>, _Container, _Compare>;717 718template <class _Compare,719 class _Container,720 class _Alloc,721 class = enable_if_t<!__is_allocator_v<_Compare>>,722 class = enable_if_t<!__is_allocator_v<_Container>>,723 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>724priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>;725 726template <class _InputIterator,727 class _Allocator,728 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,729 class = enable_if_t<__is_allocator_v<_Allocator>>>730priority_queue(_InputIterator, _InputIterator, _Allocator)731 -> priority_queue<__iterator_value_type<_InputIterator>,732 vector<__iterator_value_type<_InputIterator>, _Allocator>,733 less<__iterator_value_type<_InputIterator>>>;734 735template <class _InputIterator,736 class _Compare,737 class _Allocator,738 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,739 class = enable_if_t<!__is_allocator_v<_Compare>>,740 class = enable_if_t<__is_allocator_v<_Allocator>>>741priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)742 -> priority_queue<__iterator_value_type<_InputIterator>,743 vector<__iterator_value_type<_InputIterator>, _Allocator>,744 _Compare>;745 746template <class _InputIterator,747 class _Compare,748 class _Container,749 class _Alloc,750 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,751 class = enable_if_t<!__is_allocator_v<_Compare>>,752 class = enable_if_t<!__is_allocator_v<_Container>>,753 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >754priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)755 -> priority_queue<typename _Container::value_type, _Container, _Compare>;756# endif757 758# if _LIBCPP_STD_VER >= 23759 760template <ranges::input_range _Range,761 class _Compare = less<ranges::range_value_t<_Range>>,762 class = enable_if_t<!__is_allocator_v<_Compare>>>763priority_queue(from_range_t, _Range&&, _Compare = _Compare())764 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>;765 766template <ranges::input_range _Range,767 class _Compare,768 class _Alloc,769 class = enable_if_t<!__is_allocator_v<_Compare>>,770 class = enable_if_t<__is_allocator_v<_Alloc>>>771priority_queue(from_range_t, _Range&&, _Compare, _Alloc)772 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>;773 774template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator_v<_Alloc>>>775priority_queue(from_range_t, _Range&&, _Alloc)776 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>;777 778# endif779 780template <class _Tp, class _Container, class _Compare>781_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(782 const _Compare& __comp, const container_type& __c)783 : c(__c), comp(__comp) {784 std::make_heap(c.begin(), c.end(), comp);785}786 787# ifndef _LIBCPP_CXX03_LANG788 789template <class _Tp, class _Container, class _Compare>790_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(791 const value_compare& __comp, container_type&& __c)792 : c(std::move(__c)), comp(__comp) {793 std::make_heap(c.begin(), c.end(), comp);794}795 796# endif // _LIBCPP_CXX03_LANG797 798template <class _Tp, class _Container, class _Compare>799template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >800_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(801 _InputIter __f, _InputIter __l, const value_compare& __comp)802 : c(__f, __l), comp(__comp) {803 std::make_heap(c.begin(), c.end(), comp);804}805 806template <class _Tp, class _Container, class _Compare>807template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >808_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(809 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c)810 : c(__c), comp(__comp) {811 c.insert(c.end(), __f, __l);812 std::make_heap(c.begin(), c.end(), comp);813}814 815# ifndef _LIBCPP_CXX03_LANG816 817template <class _Tp, class _Container, class _Compare>818template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >819_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(820 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c)821 : c(std::move(__c)), comp(__comp) {822 c.insert(c.end(), __f, __l);823 std::make_heap(c.begin(), c.end(), comp);824}825 826# endif // _LIBCPP_CXX03_LANG827 828template <class _Tp, class _Container, class _Compare>829template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >830_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a)831 : c(__a) {}832 833template <class _Tp, class _Container, class _Compare>834template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >835_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(836 const value_compare& __comp, const _Alloc& __a)837 : c(__a), comp(__comp) {}838 839template <class _Tp, class _Container, class _Compare>840template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >841_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(842 const value_compare& __comp, const container_type& __c, const _Alloc& __a)843 : c(__c, __a), comp(__comp) {844 std::make_heap(c.begin(), c.end(), comp);845}846 847template <class _Tp, class _Container, class _Compare>848template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >849_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(850 const priority_queue& __q, const _Alloc& __a)851 : c(__q.c, __a), comp(__q.comp) {}852 853# ifndef _LIBCPP_CXX03_LANG854 855template <class _Tp, class _Container, class _Compare>856template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >857_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(858 const value_compare& __comp, container_type&& __c, const _Alloc& __a)859 : c(std::move(__c), __a), comp(__comp) {860 std::make_heap(c.begin(), c.end(), comp);861}862 863template <class _Tp, class _Container, class _Compare>864template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >865_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(866 priority_queue&& __q, const _Alloc& __a)867 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {}868 869# endif // _LIBCPP_CXX03_LANG870 871template <class _Tp, class _Container, class _Compare>872template <873 class _InputIter,874 class _Alloc,875 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >876_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(877 _InputIter __f, _InputIter __l, const _Alloc& __a)878 : c(__f, __l, __a), comp() {879 std::make_heap(c.begin(), c.end(), comp);880}881 882template <class _Tp, class _Container, class _Compare>883template <884 class _InputIter,885 class _Alloc,886 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >887_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(888 _InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a)889 : c(__f, __l, __a), comp(__comp) {890 std::make_heap(c.begin(), c.end(), comp);891}892 893template <class _Tp, class _Container, class _Compare>894template <895 class _InputIter,896 class _Alloc,897 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >898_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(899 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a)900 : c(__c, __a), comp(__comp) {901 c.insert(c.end(), __f, __l);902 std::make_heap(c.begin(), c.end(), comp);903}904 905# ifndef _LIBCPP_CXX03_LANG906template <class _Tp, class _Container, class _Compare>907template <908 class _InputIter,909 class _Alloc,910 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >911_LIBCPP_CONSTEXPR_SINCE_CXX26 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(912 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a)913 : c(std::move(__c), __a), comp(__comp) {914 c.insert(c.end(), __f, __l);915 std::make_heap(c.begin(), c.end(), comp);916}917# endif // _LIBCPP_CXX03_LANG918 919template <class _Tp, class _Container, class _Compare>920_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) {921 c.push_back(__v);922 std::push_heap(c.begin(), c.end(), comp);923}924 925# ifndef _LIBCPP_CXX03_LANG926 927template <class _Tp, class _Container, class _Compare>928_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) {929 c.push_back(std::move(__v));930 std::push_heap(c.begin(), c.end(), comp);931}932 933template <class _Tp, class _Container, class _Compare>934template <class... _Args>935_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) {936 c.emplace_back(std::forward<_Args>(__args)...);937 std::push_heap(c.begin(), c.end(), comp);938}939 940# endif // _LIBCPP_CXX03_LANG941 942template <class _Tp, class _Container, class _Compare>943_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void priority_queue<_Tp, _Container, _Compare>::pop() {944 std::pop_heap(c.begin(), c.end(), comp);945 c.pop_back();946}947 948template <class _Tp, class _Container, class _Compare>949_LIBCPP_CONSTEXPR_SINCE_CXX26 inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)950 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>) {951 using std::swap;952 swap(c, __q.c);953 swap(comp, __q.comp);954}955 956template <class _Tp,957 class _Container,958 class _Compare,959 __enable_if_t<__is_swappable_v<_Container> && __is_swappable_v<_Compare>, int> = 0>960_LIBCPP_CONSTEXPR_SINCE_CXX26 inline _LIBCPP_HIDE_FROM_ABI void961swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y)962 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {963 __x.swap(__y);964}965 966template <class _Tp, class _Container, class _Compare, class _Alloc>967struct uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> : public uses_allocator<_Container, _Alloc> {};968 969_LIBCPP_END_NAMESPACE_STD970 971_LIBCPP_POP_MACROS972 973# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20974# include <concepts>975# include <cstdlib>976# include <functional>977# include <type_traits>978# endif979#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)980 981#endif // _LIBCPP_QUEUE982