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 <__assert> // all public C++ headers provide the assertion handler 262#include <__config> 263#include <__functional/operations.h> 264#include <__iterator/back_insert_iterator.h> 265#include <__iterator/iterator_traits.h> 266#include <__memory/uses_allocator.h> 267#include <__ranges/access.h> 268#include <__ranges/concepts.h> 269#include <__ranges/container_compatible_range.h> 270#include <__ranges/from_range.h> 271#include <__utility/forward.h> 272#include <deque> 273#include <vector> 274#include <version> 275 276// standard-mandated includes 277 278// [queue.syn] 279#include <compare> 280#include <initializer_list> 281 282#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 283# pragma GCC system_header 284#endif 285 286_LIBCPP_BEGIN_NAMESPACE_STD 287 288template <class _Tp, class _Container = deque<_Tp> > 289class _LIBCPP_TEMPLATE_VIS queue; 290 291template <class _Tp, class _Container> 292_LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y); 293 294template <class _Tp, class _Container> 295_LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y); 296 297template <class _Tp, class _Container /*= deque<_Tp>*/> 298class _LIBCPP_TEMPLATE_VIS queue { 299public: 300 typedef _Container container_type; 301 typedef typename container_type::value_type value_type; 302 typedef typename container_type::reference reference; 303 typedef typename container_type::const_reference const_reference; 304 typedef typename container_type::size_type size_type; 305 static_assert((is_same<_Tp, value_type>::value), ""); 306 307protected: 308 container_type c; 309 310public: 311 _LIBCPP_HIDE_FROM_ABI queue() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {} 312 313 _LIBCPP_HIDE_FROM_ABI queue(const queue& __q) : c(__q.c) {} 314 315#if _LIBCPP_STD_VER >= 23 316 template <class _InputIterator, class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>> 317 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {} 318 319 template <_ContainerCompatibleRange<_Tp> _Range> 320 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {} 321 322 template <class _InputIterator, 323 class _Alloc, 324 class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 325 class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>> 326 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc) 327 : c(__first, __second, __alloc) {} 328 329 template <_ContainerCompatibleRange<_Tp> _Range, 330 class _Alloc, 331 class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>> 332 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range, const _Alloc& __alloc) 333 : c(from_range, std::forward<_Range>(__range), __alloc) {} 334 335#endif 336 337 _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) { 338 c = __q.c; 339 return *this; 340 } 341 342#ifndef _LIBCPP_CXX03_LANG 343 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q) _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value) 344 : c(std::move(__q.c)) {} 345 346 _LIBCPP_HIDE_FROM_ABI queue& operator=(queue&& __q) _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value) { 347 c = std::move(__q.c); 348 return *this; 349 } 350#endif // _LIBCPP_CXX03_LANG 351 352 _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {} 353#ifndef _LIBCPP_CXX03_LANG 354 _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {} 355#endif // _LIBCPP_CXX03_LANG 356 template <class _Alloc> 357 _LIBCPP_HIDE_FROM_ABI explicit queue(const _Alloc& __a, 358 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 359 : c(__a) {} 360 template <class _Alloc> 361 _LIBCPP_HIDE_FROM_ABI 362 queue(const queue& __q, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 363 : c(__q.c, __a) {} 364 template <class _Alloc> 365 _LIBCPP_HIDE_FROM_ABI 366 queue(const container_type& __c, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 367 : c(__c, __a) {} 368#ifndef _LIBCPP_CXX03_LANG 369 template <class _Alloc> 370 _LIBCPP_HIDE_FROM_ABI 371 queue(container_type&& __c, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 372 : c(std::move(__c), __a) {} 373 template <class _Alloc> 374 _LIBCPP_HIDE_FROM_ABI 375 queue(queue&& __q, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 376 : c(std::move(__q.c), __a) {} 377 378#endif // _LIBCPP_CXX03_LANG 379 380 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); } 381 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); } 382 383 _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); } 384 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); } 385 _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); } 386 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return c.back(); } 387 388 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); } 389#ifndef _LIBCPP_CXX03_LANG 390 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); } 391 392# if _LIBCPP_STD_VER >= 23 393 template <_ContainerCompatibleRange<_Tp> _Range> 394 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) { 395 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) { 396 c.append_range(std::forward<_Range>(__range)); 397 } else { 398 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c)); 399 } 400 } 401# endif 402 403 template <class... _Args> 404 _LIBCPP_HIDE_FROM_ABI 405# if _LIBCPP_STD_VER >= 17 406 decltype(auto) 407 emplace(_Args&&... __args) { 408 return c.emplace_back(std::forward<_Args>(__args)...); 409 } 410# else 411 void 412 emplace(_Args&&... __args) { 413 c.emplace_back(std::forward<_Args>(__args)...); 414 } 415# endif 416#endif // _LIBCPP_CXX03_LANG 417 _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_front(); } 418 419 _LIBCPP_HIDE_FROM_ABI void swap(queue& __q) _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) { 420 using std::swap; 421 swap(c, __q.c); 422 } 423 424 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; } 425 426 template <class _T1, class _OtherContainer> 427 friend _LIBCPP_HIDE_FROM_ABI bool 428 operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y); 429 430 template <class _T1, class _OtherContainer> 431 friend _LIBCPP_HIDE_FROM_ABI bool 432 operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y); 433}; 434 435#if _LIBCPP_STD_VER >= 17 436template <class _Container, class = enable_if_t<!__is_allocator<_Container>::value> > 437queue(_Container) -> queue<typename _Container::value_type, _Container>; 438 439template <class _Container, 440 class _Alloc, 441 class = enable_if_t<!__is_allocator<_Container>::value>, 442 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> > 443queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>; 444#endif 445 446#if _LIBCPP_STD_VER >= 23 447template <class _InputIterator, class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>> 448queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>; 449 450template <ranges::input_range _Range> 451queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>; 452 453template <class _InputIterator, 454 class _Alloc, 455 class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 456 class = __enable_if_t<__is_allocator<_Alloc>::value>> 457queue(_InputIterator, _InputIterator, _Alloc) 458 -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>; 459 460template <ranges::input_range _Range, class _Alloc, class = __enable_if_t<__is_allocator<_Alloc>::value>> 461queue(from_range_t, _Range&&, _Alloc) 462 -> 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<_Container>::value, 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 = vector<_Tp>, class _Compare = less<typename _Container::value_type> > 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) 550 _NOEXCEPT_(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, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> > 563 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare()); 564 template <class _InputIter, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> > 565 _LIBCPP_HIDE_FROM_ABI 566 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c); 567#ifndef _LIBCPP_CXX03_LANG 568 template <class _InputIter, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> > 569 _LIBCPP_HIDE_FROM_ABI 570 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c); 571#endif // _LIBCPP_CXX03_LANG 572 573#if _LIBCPP_STD_VER >= 23 574 template <_ContainerCompatibleRange<_Tp> _Range> 575 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare()) 576 : c(from_range, std::forward<_Range>(__range)), comp(__comp) { 577 std::make_heap(c.begin(), c.end(), comp); 578 } 579#endif 580 581 template <class _Alloc> 582 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const _Alloc& __a, 583 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 584 template <class _Alloc> 585 _LIBCPP_HIDE_FROM_ABI 586 priority_queue(const value_compare& __comp, 587 const _Alloc& __a, 588 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 589 template <class _Alloc> 590 _LIBCPP_HIDE_FROM_ABI 591 priority_queue(const value_compare& __comp, 592 const container_type& __c, 593 const _Alloc& __a, 594 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 595 template <class _Alloc> 596 _LIBCPP_HIDE_FROM_ABI priority_queue( 597 const priority_queue& __q, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 598#ifndef _LIBCPP_CXX03_LANG 599 template <class _Alloc> 600 _LIBCPP_HIDE_FROM_ABI 601 priority_queue(const value_compare& __comp, 602 container_type&& __c, 603 const _Alloc& __a, 604 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 605 template <class _Alloc> 606 _LIBCPP_HIDE_FROM_ABI priority_queue( 607 priority_queue&& __q, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 608#endif // _LIBCPP_CXX03_LANG 609 610 template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> > 611 _LIBCPP_HIDE_FROM_ABI 612 priority_queue(_InputIter __f, 613 _InputIter __l, 614 const _Alloc& __a, 615 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 616 617 template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> > 618 _LIBCPP_HIDE_FROM_ABI priority_queue( 619 _InputIter __f, 620 _InputIter __l, 621 const value_compare& __comp, 622 const _Alloc& __a, 623 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 624 625 template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> > 626 _LIBCPP_HIDE_FROM_ABI priority_queue( 627 _InputIter __f, 628 _InputIter __l, 629 const value_compare& __comp, 630 const container_type& __c, 631 const _Alloc& __a, 632 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 633 634#ifndef _LIBCPP_CXX03_LANG 635 template <class _InputIter, class _Alloc, class = __enable_if_t<__has_input_iterator_category<_InputIter>::value> > 636 _LIBCPP_HIDE_FROM_ABI priority_queue( 637 _InputIter __f, 638 _InputIter __l, 639 const value_compare& __comp, 640 container_type&& __c, 641 const _Alloc& __a, 642 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 643#endif // _LIBCPP_CXX03_LANG 644 645#if _LIBCPP_STD_VER >= 23 646 647 template <_ContainerCompatibleRange<_Tp> _Range, 648 class _Alloc, 649 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>> 650 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a) 651 : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) { 652 std::make_heap(c.begin(), c.end(), comp); 653 } 654 655 template <_ContainerCompatibleRange<_Tp> _Range, 656 class _Alloc, 657 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>> 658 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a) 659 : c(from_range, std::forward<_Range>(__range), __a), comp() { 660 std::make_heap(c.begin(), c.end(), comp); 661 } 662 663#endif 664 665 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); } 666 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); } 667 _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.front(); } 668 669 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v); 670#ifndef _LIBCPP_CXX03_LANG 671 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v); 672 673# if _LIBCPP_STD_VER >= 23 674 template <_ContainerCompatibleRange<_Tp> _Range> 675 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) { 676 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) { 677 c.append_range(std::forward<_Range>(__range)); 678 } else { 679 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c)); 680 } 681 682 std::make_heap(c.begin(), c.end(), comp); 683 } 684# endif 685 686 template <class... _Args> 687 _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args); 688#endif // _LIBCPP_CXX03_LANG 689 _LIBCPP_HIDE_FROM_ABI void pop(); 690 691 _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q) 692 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value&& __is_nothrow_swappable<value_compare>::value); 693 694 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; } 695}; 696 697#if _LIBCPP_STD_VER >= 17 698template <class _Compare, 699 class _Container, 700 class = enable_if_t<!__is_allocator<_Compare>::value>, 701 class = enable_if_t<!__is_allocator<_Container>::value> > 702priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>; 703 704template <class _InputIterator, 705 class _Compare = less<__iter_value_type<_InputIterator>>, 706 class _Container = vector<__iter_value_type<_InputIterator>>, 707 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 708 class = enable_if_t<!__is_allocator<_Compare>::value>, 709 class = enable_if_t<!__is_allocator<_Container>::value> > 710priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container()) 711 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>; 712 713template <class _Compare, 714 class _Container, 715 class _Alloc, 716 class = enable_if_t<!__is_allocator<_Compare>::value>, 717 class = enable_if_t<!__is_allocator<_Container>::value>, 718 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> > 719priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>; 720 721template <class _InputIterator, 722 class _Allocator, 723 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 724 class = enable_if_t<__is_allocator<_Allocator>::value> > 725priority_queue(_InputIterator, _InputIterator, _Allocator) 726 -> priority_queue<__iter_value_type<_InputIterator>, 727 vector<__iter_value_type<_InputIterator>, _Allocator>, 728 less<__iter_value_type<_InputIterator>>>; 729 730template <class _InputIterator, 731 class _Compare, 732 class _Allocator, 733 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 734 class = enable_if_t<!__is_allocator<_Compare>::value>, 735 class = enable_if_t<__is_allocator<_Allocator>::value> > 736priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator) 737 -> priority_queue<__iter_value_type<_InputIterator>, 738 vector<__iter_value_type<_InputIterator>, _Allocator>, 739 _Compare>; 740 741template <class _InputIterator, 742 class _Compare, 743 class _Container, 744 class _Alloc, 745 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 746 class = enable_if_t<!__is_allocator<_Compare>::value>, 747 class = enable_if_t<!__is_allocator<_Container>::value>, 748 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> > 749priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc) 750 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 751#endif 752 753#if _LIBCPP_STD_VER >= 23 754 755template <ranges::input_range _Range, 756 class _Compare = less<ranges::range_value_t<_Range>>, 757 class = enable_if_t<!__is_allocator<_Compare>::value>> 758priority_queue(from_range_t, _Range&&, _Compare = _Compare()) 759 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>; 760 761template <ranges::input_range _Range, 762 class _Compare, 763 class _Alloc, 764 class = enable_if_t<!__is_allocator<_Compare>::value>, 765 class = enable_if_t<__is_allocator<_Alloc>::value>> 766priority_queue(from_range_t, _Range&&, _Compare, _Alloc) 767 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>; 768 769template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator<_Alloc>::value>> 770priority_queue(from_range_t, _Range&&, _Alloc) 771 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>; 772 773#endif 774 775template <class _Tp, class _Container, class _Compare> 776inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, const container_type& __c) 777 : c(__c), comp(__comp) { 778 std::make_heap(c.begin(), c.end(), comp); 779} 780 781#ifndef _LIBCPP_CXX03_LANG 782 783template <class _Tp, class _Container, class _Compare> 784inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, container_type&& __c) 785 : c(std::move(__c)), comp(__comp) { 786 std::make_heap(c.begin(), c.end(), comp); 787} 788 789#endif // _LIBCPP_CXX03_LANG 790 791template <class _Tp, class _Container, class _Compare> 792template <class _InputIter, class> 793inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 794 _InputIter __f, _InputIter __l, const value_compare& __comp) 795 : c(__f, __l), comp(__comp) { 796 std::make_heap(c.begin(), c.end(), comp); 797} 798 799template <class _Tp, class _Container, class _Compare> 800template <class _InputIter, class> 801inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 802 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c) 803 : c(__c), comp(__comp) { 804 c.insert(c.end(), __f, __l); 805 std::make_heap(c.begin(), c.end(), comp); 806} 807 808#ifndef _LIBCPP_CXX03_LANG 809 810template <class _Tp, class _Container, class _Compare> 811template <class _InputIter, class> 812inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 813 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c) 814 : c(std::move(__c)), comp(__comp) { 815 c.insert(c.end(), __f, __l); 816 std::make_heap(c.begin(), c.end(), comp); 817} 818 819#endif // _LIBCPP_CXX03_LANG 820 821template <class _Tp, class _Container, class _Compare> 822template <class _Alloc> 823inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 824 const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 825 : c(__a) {} 826 827template <class _Tp, class _Container, class _Compare> 828template <class _Alloc> 829inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 830 const value_compare& __comp, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 831 : c(__a), comp(__comp) {} 832 833template <class _Tp, class _Container, class _Compare> 834template <class _Alloc> 835inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 836 const value_compare& __comp, 837 const container_type& __c, 838 const _Alloc& __a, 839 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 840 : c(__c, __a), comp(__comp) { 841 std::make_heap(c.begin(), c.end(), comp); 842} 843 844template <class _Tp, class _Container, class _Compare> 845template <class _Alloc> 846inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 847 const priority_queue& __q, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 848 : c(__q.c, __a), comp(__q.comp) {} 849 850#ifndef _LIBCPP_CXX03_LANG 851 852template <class _Tp, class _Container, class _Compare> 853template <class _Alloc> 854inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 855 const value_compare& __comp, 856 container_type&& __c, 857 const _Alloc& __a, 858 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 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> 865inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 866 priority_queue&& __q, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 867 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {} 868 869#endif // _LIBCPP_CXX03_LANG 870 871template <class _Tp, class _Container, class _Compare> 872template <class _InputIter, class _Alloc, class> 873inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 874 _InputIter __f, _InputIter __l, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 875 : c(__f, __l, __a), comp() { 876 std::make_heap(c.begin(), c.end(), comp); 877} 878 879template <class _Tp, class _Container, class _Compare> 880template <class _InputIter, class _Alloc, class> 881inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 882 _InputIter __f, 883 _InputIter __l, 884 const value_compare& __comp, 885 const _Alloc& __a, 886 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 887 : c(__f, __l, __a), comp(__comp) { 888 std::make_heap(c.begin(), c.end(), comp); 889} 890 891template <class _Tp, class _Container, class _Compare> 892template <class _InputIter, class _Alloc, class> 893inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 894 _InputIter __f, 895 _InputIter __l, 896 const value_compare& __comp, 897 const container_type& __c, 898 const _Alloc& __a, 899 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 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_LANG 906template <class _Tp, class _Container, class _Compare> 907template <class _InputIter, class _Alloc, class> 908inline priority_queue<_Tp, _Container, _Compare>::priority_queue( 909 _InputIter __f, 910 _InputIter __l, 911 const value_compare& __comp, 912 container_type&& __c, 913 const _Alloc& __a, 914 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 915 : c(std::move(__c), __a), comp(__comp) { 916 c.insert(c.end(), __f, __l); 917 std::make_heap(c.begin(), c.end(), comp); 918} 919#endif // _LIBCPP_CXX03_LANG 920 921template <class _Tp, class _Container, class _Compare> 922inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) { 923 c.push_back(__v); 924 std::push_heap(c.begin(), c.end(), comp); 925} 926 927#ifndef _LIBCPP_CXX03_LANG 928 929template <class _Tp, class _Container, class _Compare> 930inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) { 931 c.push_back(std::move(__v)); 932 std::push_heap(c.begin(), c.end(), comp); 933} 934 935template <class _Tp, class _Container, class _Compare> 936template <class... _Args> 937inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) { 938 c.emplace_back(std::forward<_Args>(__args)...); 939 std::push_heap(c.begin(), c.end(), comp); 940} 941 942#endif // _LIBCPP_CXX03_LANG 943 944template <class _Tp, class _Container, class _Compare> 945inline void priority_queue<_Tp, _Container, _Compare>::pop() { 946 std::pop_heap(c.begin(), c.end(), comp); 947 c.pop_back(); 948} 949 950template <class _Tp, class _Container, class _Compare> 951inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q) 952 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value&& __is_nothrow_swappable<value_compare>::value) { 953 using std::swap; 954 swap(c, __q.c); 955 swap(comp, __q.comp); 956} 957 958template <class _Tp, 959 class _Container, 960 class _Compare, 961 __enable_if_t<__is_swappable<_Container>::value && __is_swappable<_Compare>::value, int> = 0> 962inline _LIBCPP_HIDE_FROM_ABI void 963swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y) 964 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 965 __x.swap(__y); 966} 967 968template <class _Tp, class _Container, class _Compare, class _Alloc> 969struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> 970 : public uses_allocator<_Container, _Alloc> {}; 971 972_LIBCPP_END_NAMESPACE_STD 973 974#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 975# include <concepts> 976# include <cstdlib> 977# include <functional> 978# include <type_traits> 979#endif 980 981#endif // _LIBCPP_QUEUE 982