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