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#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) 258# include <__cxx03/queue> 259#else 260# 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 includes 281 282// [queue.syn] 283# include <compare> 284# include <initializer_list> 285 286# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 287# pragma GCC system_header 288# endif 289 290_LIBCPP_PUSH_MACROS 291# include <__undef_macros> 292 293_LIBCPP_BEGIN_NAMESPACE_STD 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> 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 _LIBCPP_TEMPLATE_VIS 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 >= 23 320 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# endif 340 341 _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) { 342 c = __q.c; 343 return *this; 344 } 345 346# ifndef _LIBCPP_CXX03_LANG 347 _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_LANG 355 356 _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {} 357# ifndef _LIBCPP_CXX03_LANG 358 _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {} 359# endif // _LIBCPP_CXX03_LANG 360 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_LANG 371 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_LANG 377 378 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); } 379 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); } 380 381 _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); } 382 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); } 383 _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); } 384 _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_LANG 388 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); } 389 390# if _LIBCPP_STD_VER >= 23 391 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# endif 400 401 template <class... _Args> 402 _LIBCPP_HIDE_FROM_ABI 403# if _LIBCPP_STD_VER >= 17 404 decltype(auto) 405 emplace(_Args&&... __args) { 406 return c.emplace_back(std::forward<_Args>(__args)...); 407 } 408# else 409 void 410 emplace(_Args&&... __args) { 411 c.emplace_back(std::forward<_Args>(__args)...); 412 } 413# endif 414# endif // _LIBCPP_CXX03_LANG 415 _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 bool 426 operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y); 427 428 template <class _T1, class _OtherContainer> 429 friend _LIBCPP_HIDE_FROM_ABI bool 430 operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y); 431}; 432 433# if _LIBCPP_STD_VER >= 17 434template <class _Container, class = enable_if_t<!__is_allocator<_Container>::value> > 435queue(_Container) -> queue<typename _Container::value_type, _Container>; 436 437template <class _Container, 438 class _Alloc, 439 class = enable_if_t<!__is_allocator<_Container>::value>, 440 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> > 441queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>; 442# endif 443 444# if _LIBCPP_STD_VER >= 23 445template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0> 446queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>; 447 448template <ranges::input_range _Range> 449queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>; 450 451template <class _InputIterator, 452 class _Alloc, 453 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0, 454 __enable_if_t<__is_allocator<_Alloc>::value, int> = 0> 455queue(_InputIterator, 456 _InputIterator, 457 _Alloc) -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>; 458 459template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator<_Alloc>::value, int> = 0> 460queue(from_range_t, 461 _Range&&, 462 _Alloc) -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>; 463# endif 464 465template <class _Tp, class _Container> 466inline _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) { 467 return __x.c == __y.c; 468} 469 470template <class _Tp, class _Container> 471inline _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) { 472 return __x.c < __y.c; 473} 474 475template <class _Tp, class _Container> 476inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) { 477 return !(__x == __y); 478} 479 480template <class _Tp, class _Container> 481inline _LIBCPP_HIDE_FROM_ABI bool operator>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) { 482 return __y < __x; 483} 484 485template <class _Tp, class _Container> 486inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) { 487 return !(__x < __y); 488} 489 490template <class _Tp, class _Container> 491inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) { 492 return !(__y < __x); 493} 494 495# if _LIBCPP_STD_VER >= 20 496 497template <class _Tp, three_way_comparable _Container> 498_LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container> 499operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) { 500 // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors 501 return __x.__get_container() <=> __y.__get_container(); 502} 503 504# endif 505 506template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0> 507inline _LIBCPP_HIDE_FROM_ABI void swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y) 508 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 509 __x.swap(__y); 510} 511 512template <class _Tp, class _Container, class _Alloc> 513struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> { 514}; 515 516template <class _Tp, class _Container, class _Compare> 517class _LIBCPP_TEMPLATE_VIS priority_queue { 518public: 519 typedef _Container container_type; 520 typedef _Compare value_compare; 521 typedef typename container_type::value_type value_type; 522 typedef typename container_type::reference reference; 523 typedef typename container_type::const_reference const_reference; 524 typedef typename container_type::size_type size_type; 525 static_assert(is_same<_Tp, value_type>::value, ""); 526 527protected: 528 container_type c; 529 value_compare comp; 530 531public: 532 _LIBCPP_HIDE_FROM_ABI priority_queue() _NOEXCEPT_( 533 is_nothrow_default_constructible<container_type>::value&& is_nothrow_default_constructible<value_compare>::value) 534 : c(), comp() {} 535 536 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {} 537 538 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(const priority_queue& __q) { 539 c = __q.c; 540 comp = __q.comp; 541 return *this; 542 } 543 544# ifndef _LIBCPP_CXX03_LANG 545 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q) noexcept( 546 is_nothrow_move_constructible<container_type>::value && is_nothrow_move_constructible<value_compare>::value) 547 : c(std::move(__q.c)), comp(std::move(__q.comp)) {} 548 549 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(priority_queue&& __q) noexcept( 550 is_nothrow_move_assignable<container_type>::value && is_nothrow_move_assignable<value_compare>::value) { 551 c = std::move(__q.c); 552 comp = std::move(__q.comp); 553 return *this; 554 } 555# endif // _LIBCPP_CXX03_LANG 556 557 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const value_compare& __comp) : c(), comp(__comp) {} 558 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c); 559# ifndef _LIBCPP_CXX03_LANG 560 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c); 561# endif 562 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0> 563 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare()); 564 565 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0> 566 _LIBCPP_HIDE_FROM_ABI 567 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c); 568 569# ifndef _LIBCPP_CXX03_LANG 570 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0> 571 _LIBCPP_HIDE_FROM_ABI 572 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c); 573# endif // _LIBCPP_CXX03_LANG 574 575# if _LIBCPP_STD_VER >= 23 576 template <_ContainerCompatibleRange<_Tp> _Range> 577 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare()) 578 : c(from_range, std::forward<_Range>(__range)), comp(__comp) { 579 std::make_heap(c.begin(), c.end(), comp); 580 } 581# endif 582 583 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0> 584 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(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 _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 value_compare& __comp, const container_type& __c, const _Alloc& __a); 591 592 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0> 593 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q, const _Alloc& __a); 594 595# ifndef _LIBCPP_CXX03_LANG 596 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0> 597 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c, const _Alloc& __a); 598 599 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0> 600 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q, const _Alloc& __a); 601# endif // _LIBCPP_CXX03_LANG 602 603 template < 604 class _InputIter, 605 class _Alloc, 606 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value, 607 int> = 0> 608 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a); 609 610 template < 611 class _InputIter, 612 class _Alloc, 613 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value, 614 int> = 0> 615 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a); 616 617 template < 618 class _InputIter, 619 class _Alloc, 620 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value, 621 int> = 0> 622 _LIBCPP_HIDE_FROM_ABI priority_queue( 623 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a); 624 625# ifndef _LIBCPP_CXX03_LANG 626 template < 627 class _InputIter, 628 class _Alloc, 629 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value, 630 int> = 0> 631 _LIBCPP_HIDE_FROM_ABI 632 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a); 633# endif // _LIBCPP_CXX03_LANG 634 635# if _LIBCPP_STD_VER >= 23 636 637 template <_ContainerCompatibleRange<_Tp> _Range, 638 class _Alloc, 639 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>> 640 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a) 641 : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) { 642 std::make_heap(c.begin(), c.end(), comp); 643 } 644 645 template <_ContainerCompatibleRange<_Tp> _Range, 646 class _Alloc, 647 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>> 648 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a) 649 : c(from_range, std::forward<_Range>(__range), __a), comp() { 650 std::make_heap(c.begin(), c.end(), comp); 651 } 652 653# endif 654 655 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); } 656 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); } 657 _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.front(); } 658 659 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v); 660# ifndef _LIBCPP_CXX03_LANG 661 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v); 662 663# if _LIBCPP_STD_VER >= 23 664 template <_ContainerCompatibleRange<_Tp> _Range> 665 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) { 666 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) { 667 c.append_range(std::forward<_Range>(__range)); 668 } else { 669 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c)); 670 } 671 672 std::make_heap(c.begin(), c.end(), comp); 673 } 674# endif 675 676 template <class... _Args> 677 _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args); 678# endif // _LIBCPP_CXX03_LANG 679 _LIBCPP_HIDE_FROM_ABI void pop(); 680 681 _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q) 682 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>); 683 684 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; } 685}; 686 687# if _LIBCPP_STD_VER >= 17 688template <class _Compare, 689 class _Container, 690 class = enable_if_t<!__is_allocator<_Compare>::value>, 691 class = enable_if_t<!__is_allocator<_Container>::value> > 692priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>; 693 694template <class _InputIterator, 695 class _Compare = less<__iter_value_type<_InputIterator>>, 696 class _Container = vector<__iter_value_type<_InputIterator>>, 697 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 698 class = enable_if_t<!__is_allocator<_Compare>::value>, 699 class = enable_if_t<!__is_allocator<_Container>::value> > 700priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container()) 701 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>; 702 703template <class _Compare, 704 class _Container, 705 class _Alloc, 706 class = enable_if_t<!__is_allocator<_Compare>::value>, 707 class = enable_if_t<!__is_allocator<_Container>::value>, 708 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> > 709priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>; 710 711template <class _InputIterator, 712 class _Allocator, 713 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 714 class = enable_if_t<__is_allocator<_Allocator>::value> > 715priority_queue(_InputIterator, _InputIterator, _Allocator) 716 -> priority_queue<__iter_value_type<_InputIterator>, 717 vector<__iter_value_type<_InputIterator>, _Allocator>, 718 less<__iter_value_type<_InputIterator>>>; 719 720template <class _InputIterator, 721 class _Compare, 722 class _Allocator, 723 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 724 class = enable_if_t<!__is_allocator<_Compare>::value>, 725 class = enable_if_t<__is_allocator<_Allocator>::value> > 726priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator) 727 -> priority_queue<__iter_value_type<_InputIterator>, 728 vector<__iter_value_type<_InputIterator>, _Allocator>, 729 _Compare>; 730 731template <class _InputIterator, 732 class _Compare, 733 class _Container, 734 class _Alloc, 735 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 736 class = enable_if_t<!__is_allocator<_Compare>::value>, 737 class = enable_if_t<!__is_allocator<_Container>::value>, 738 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> > 739priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc) 740 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 741# endif 742 743# if _LIBCPP_STD_VER >= 23 744 745template <ranges::input_range _Range, 746 class _Compare = less<ranges::range_value_t<_Range>>, 747 class = enable_if_t<!__is_allocator<_Compare>::value>> 748priority_queue(from_range_t, _Range&&, _Compare = _Compare()) 749 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>; 750 751template <ranges::input_range _Range, 752 class _Compare, 753 class _Alloc, 754 class = enable_if_t<!__is_allocator<_Compare>::value>, 755 class = enable_if_t<__is_allocator<_Alloc>::value>> 756priority_queue(from_range_t, _Range&&, _Compare, _Alloc) 757 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>; 758 759template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator<_Alloc>::value>> 760priority_queue(from_range_t, _Range&&, _Alloc) 761 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>; 762 763# endif 764 765template <class _Tp, class _Container, class _Compare> 766inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, const container_type& __c) 767 : c(__c), comp(__comp) { 768 std::make_heap(c.begin(), c.end(), comp); 769} 770 771# ifndef _LIBCPP_CXX03_LANG 772 773template <class _Tp, class _Container, class _Compare> 774inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, container_type&& __c) 775 : c(std::move(__c)), comp(__comp) { 776 std::make_heap(c.begin(), c.end(), comp); 777} 778 779# endif // _LIBCPP_CXX03_LANG 780 781template <class _Tp, class _Container, class _Compare> 782template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> > 783inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 784 _InputIter __f, _InputIter __l, const value_compare& __comp) 785 : c(__f, __l), comp(__comp) { 786 std::make_heap(c.begin(), c.end(), comp); 787} 788 789template <class _Tp, class _Container, class _Compare> 790template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> > 791inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 792 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c) 793 : c(__c), comp(__comp) { 794 c.insert(c.end(), __f, __l); 795 std::make_heap(c.begin(), c.end(), comp); 796} 797 798# ifndef _LIBCPP_CXX03_LANG 799 800template <class _Tp, class _Container, class _Compare> 801template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> > 802inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 803 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c) 804 : c(std::move(__c)), comp(__comp) { 805 c.insert(c.end(), __f, __l); 806 std::make_heap(c.begin(), c.end(), comp); 807} 808 809# endif // _LIBCPP_CXX03_LANG 810 811template <class _Tp, class _Container, class _Compare> 812template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> > 813inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a) : c(__a) {} 814 815template <class _Tp, class _Container, class _Compare> 816template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> > 817inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, const _Alloc& __a) 818 : c(__a), comp(__comp) {} 819 820template <class _Tp, class _Container, class _Compare> 821template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> > 822inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 823 const value_compare& __comp, const container_type& __c, const _Alloc& __a) 824 : c(__c, __a), comp(__comp) { 825 std::make_heap(c.begin(), c.end(), comp); 826} 827 828template <class _Tp, class _Container, class _Compare> 829template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> > 830inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, const _Alloc& __a) 831 : c(__q.c, __a), comp(__q.comp) {} 832 833# ifndef _LIBCPP_CXX03_LANG 834 835template <class _Tp, class _Container, class _Compare> 836template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> > 837inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 838 const value_compare& __comp, container_type&& __c, const _Alloc& __a) 839 : c(std::move(__c), __a), comp(__comp) { 840 std::make_heap(c.begin(), c.end(), comp); 841} 842 843template <class _Tp, class _Container, class _Compare> 844template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> > 845inline priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, const _Alloc& __a) 846 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {} 847 848# endif // _LIBCPP_CXX03_LANG 849 850template <class _Tp, class _Container, class _Compare> 851template < 852 class _InputIter, 853 class _Alloc, 854 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> > 855inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a) 856 : c(__f, __l, __a), comp() { 857 std::make_heap(c.begin(), c.end(), comp); 858} 859 860template <class _Tp, class _Container, class _Compare> 861template < 862 class _InputIter, 863 class _Alloc, 864 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> > 865inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 866 _InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a) 867 : c(__f, __l, __a), comp(__comp) { 868 std::make_heap(c.begin(), c.end(), comp); 869} 870 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> > 876inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 877 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a) 878 : c(__c, __a), comp(__comp) { 879 c.insert(c.end(), __f, __l); 880 std::make_heap(c.begin(), c.end(), comp); 881} 882 883# ifndef _LIBCPP_CXX03_LANG 884template <class _Tp, class _Container, class _Compare> 885template < 886 class _InputIter, 887 class _Alloc, 888 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> > 889inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 890 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a) 891 : c(std::move(__c), __a), comp(__comp) { 892 c.insert(c.end(), __f, __l); 893 std::make_heap(c.begin(), c.end(), comp); 894} 895# endif // _LIBCPP_CXX03_LANG 896 897template <class _Tp, class _Container, class _Compare> 898inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) { 899 c.push_back(__v); 900 std::push_heap(c.begin(), c.end(), comp); 901} 902 903# ifndef _LIBCPP_CXX03_LANG 904 905template <class _Tp, class _Container, class _Compare> 906inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) { 907 c.push_back(std::move(__v)); 908 std::push_heap(c.begin(), c.end(), comp); 909} 910 911template <class _Tp, class _Container, class _Compare> 912template <class... _Args> 913inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) { 914 c.emplace_back(std::forward<_Args>(__args)...); 915 std::push_heap(c.begin(), c.end(), comp); 916} 917 918# endif // _LIBCPP_CXX03_LANG 919 920template <class _Tp, class _Container, class _Compare> 921inline void priority_queue<_Tp, _Container, _Compare>::pop() { 922 std::pop_heap(c.begin(), c.end(), comp); 923 c.pop_back(); 924} 925 926template <class _Tp, class _Container, class _Compare> 927inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q) 928 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>) { 929 using std::swap; 930 swap(c, __q.c); 931 swap(comp, __q.comp); 932} 933 934template <class _Tp, 935 class _Container, 936 class _Compare, 937 __enable_if_t<__is_swappable_v<_Container> && __is_swappable_v<_Compare>, int> = 0> 938inline _LIBCPP_HIDE_FROM_ABI void 939swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y) 940 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 941 __x.swap(__y); 942} 943 944template <class _Tp, class _Container, class _Compare, class _Alloc> 945struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> 946 : public uses_allocator<_Container, _Alloc> {}; 947 948_LIBCPP_END_NAMESPACE_STD 949 950_LIBCPP_POP_MACROS 951 952# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 953# include <concepts> 954# include <cstdlib> 955# include <functional> 956# include <type_traits> 957# endif 958#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) 959 960#endif // _LIBCPP_QUEUE 961