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