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