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 <class Alloc> 47 explicit queue(const Alloc& a); 48 template <class Alloc> 49 queue(const container_type& c, const Alloc& a); 50 template <class Alloc> 51 queue(container_type&& c, const Alloc& a); 52 template <class Alloc> 53 queue(const queue& q, const Alloc& a); 54 template <class Alloc> 55 queue(queue&& q, const Alloc& a); 56 template <class InputIterator, class Alloc> 57 queue(InputIterator first, InputIterator last, const Alloc&); // since C++23 58 59 bool empty() const; 60 size_type size() const; 61 62 reference front(); 63 const_reference front() const; 64 reference back(); 65 const_reference back() const; 66 67 void push(const value_type& v); 68 void push(value_type&& v); 69 template <class... Args> reference emplace(Args&&... args); // reference in C++17 70 void pop(); 71 72 void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>) 73}; 74 75template<class Container> 76 queue(Container) -> queue<typename Container::value_type, Container>; // C++17 77 78template<class InputIterator> 79 queue(InputIterator, InputIterator) -> queue<iter-value-type<InputIterator>>; // since C++23 80 81template<class Container, class Allocator> 82 queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17 83 84template<class InputIterator, class Allocator> 85 queue(InputIterator, InputIterator, Allocator) 86 -> queue<iter-value-type<InputIterator>, 87 deque<iter-value-type<InputIterator>, Allocator>>; // since C++23 88 89template <class T, class Container> 90 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y); 91 92template <class T, class Container> 93 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y); 94 95template <class T, class Container> 96 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y); 97 98template <class T, class Container> 99 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y); 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 void swap(queue<T, Container>& x, queue<T, Container>& y) 109 noexcept(noexcept(x.swap(y))); 110 111template <class T, class Container = vector<T>, 112 class Compare = less<typename Container::value_type>> 113class priority_queue 114{ 115public: 116 typedef Container container_type; 117 typedef typename container_type::value_type value_type; 118 typedef typename container_type::reference reference; 119 typedef typename container_type::const_reference const_reference; 120 typedef typename container_type::size_type size_type; 121 122protected: 123 container_type c; 124 Compare comp; 125 126public: 127 priority_queue() : priority_queue(Compare()) {} // C++20 128 explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {} 129 priority_queue(const Compare& x, const Container&); 130 explicit priority_queue(const Compare& x = Compare(), Container&& = Container()); // before C++20 131 priority_queue(const Compare& x, Container&&); // C++20 132 template <class InputIterator> 133 priority_queue(InputIterator first, InputIterator last, 134 const Compare& comp = Compare()); 135 template <class InputIterator> 136 priority_queue(InputIterator first, InputIterator last, 137 const Compare& comp, const Container& c); 138 template <class InputIterator> 139 priority_queue(InputIterator first, InputIterator last, 140 const Compare& comp, Container&& c); 141 template <class Alloc> 142 explicit priority_queue(const Alloc& a); 143 template <class Alloc> 144 priority_queue(const Compare& comp, const Alloc& a); 145 template <class Alloc> 146 priority_queue(const Compare& comp, const Container& c, 147 const Alloc& a); 148 template <class Alloc> 149 priority_queue(const Compare& comp, Container&& c, 150 const Alloc& a); 151 template <class InputIterator> 152 priority_queue(InputIterator first, InputIterator last, 153 const Alloc& a); 154 template <class InputIterator> 155 priority_queue(InputIterator first, InputIterator last, 156 const Compare& comp, const Alloc& a); 157 template <class InputIterator> 158 priority_queue(InputIterator first, InputIterator last, 159 const Compare& comp, const Container& c, const Alloc& a); 160 template <class InputIterator> 161 priority_queue(InputIterator first, InputIterator last, 162 const Compare& comp, Container&& c, const Alloc& a); 163 template <class Alloc> 164 priority_queue(const priority_queue& q, const Alloc& a); 165 template <class Alloc> 166 priority_queue(priority_queue&& q, const Alloc& a); 167 168 bool empty() const; 169 size_type size() const; 170 const_reference top() const; 171 172 void push(const value_type& v); 173 void push(value_type&& v); 174 template <class... Args> void emplace(Args&&... args); 175 void pop(); 176 177 void swap(priority_queue& q) 178 noexcept(is_nothrow_swappable_v<Container> && 179 is_nothrow_swappable_v<Comp>) 180}; 181 182template <class Compare, class Container> 183priority_queue(Compare, Container) 184 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17 185 186template<class InputIterator, 187 class Compare = less<iter-value-type<InputIterator>>, 188 class Container = vector<iter-value-type<InputIterator>>> 189priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container()) 190 -> priority_queue<iter-value-type<InputIterator>, Container, Compare>; // C++17 191 192template<class Compare, class Container, class Allocator> 193priority_queue(Compare, Container, Allocator) 194 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17 195 196template<class InputIterator, class Allocator> 197priority_queue(InputIterator, InputIterator, Allocator) 198 -> priority_queue<iter-value-type<InputIterator>, 199 vector<iter-value-type<InputIterator>, Allocator>, 200 less<iter-value-type<InputIterator>>>; // C++17 201 202template<class InputIterator, class Compare, class Allocator> 203priority_queue(InputIterator, InputIterator, Compare, Allocator) 204 -> priority_queue<iter-value-type<InputIterator>, 205 vector<iter-value-type<InputIterator>, Allocator>, Compare>; // C++17 206 207template<class InputIterator, class Compare, class Container, class Allocator> 208priority_queue(InputIterator, InputIterator, Compare, Container, Allocator) 209 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17 210 211template <class T, class Container, class Compare> 212 void swap(priority_queue<T, Container, Compare>& x, 213 priority_queue<T, Container, Compare>& y) 214 noexcept(noexcept(x.swap(y))); 215 216} // std 217 218*/ 219 220#include <__algorithm/make_heap.h> 221#include <__algorithm/pop_heap.h> 222#include <__algorithm/push_heap.h> 223#include <__assert> // all public C++ headers provide the assertion handler 224#include <__config> 225#include <__functional/operations.h> 226#include <__iterator/iterator_traits.h> 227#include <__memory/uses_allocator.h> 228#include <__utility/forward.h> 229#include <deque> 230#include <type_traits> 231#include <vector> 232#include <version> 233 234// standard-mandated includes 235 236// [queue.syn] 237#include <compare> 238#include <initializer_list> 239 240#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 241# pragma GCC system_header 242#endif 243 244_LIBCPP_BEGIN_NAMESPACE_STD 245 246template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue; 247 248template <class _Tp, class _Container> 249_LIBCPP_INLINE_VISIBILITY 250bool 251operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 252 253template <class _Tp, class _Container> 254_LIBCPP_INLINE_VISIBILITY 255bool 256operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 257 258template <class _Tp, class _Container /*= deque<_Tp>*/> 259class _LIBCPP_TEMPLATE_VIS queue 260{ 261public: 262 typedef _Container container_type; 263 typedef typename container_type::value_type value_type; 264 typedef typename container_type::reference reference; 265 typedef typename container_type::const_reference const_reference; 266 typedef typename container_type::size_type size_type; 267 static_assert((is_same<_Tp, value_type>::value), "" ); 268 269protected: 270 container_type c; 271 272public: 273 _LIBCPP_INLINE_VISIBILITY 274 queue() 275 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) 276 : c() {} 277 278 _LIBCPP_INLINE_VISIBILITY 279 queue(const queue& __q) : c(__q.c) {} 280 281#if _LIBCPP_STD_VER > 20 282 template <class _InputIterator, 283 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>> 284 _LIBCPP_HIDE_FROM_ABI 285 queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {} 286 287 template <class _InputIterator, 288 class _Alloc, 289 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 290 class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>> 291 _LIBCPP_HIDE_FROM_ABI 292 queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc) : c(__first, __second, __alloc) {} 293#endif 294 295 _LIBCPP_INLINE_VISIBILITY 296 queue& operator=(const queue& __q) {c = __q.c; return *this;} 297 298#ifndef _LIBCPP_CXX03_LANG 299 _LIBCPP_INLINE_VISIBILITY 300 queue(queue&& __q) 301 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value) 302 : c(_VSTD::move(__q.c)) {} 303 304 _LIBCPP_INLINE_VISIBILITY 305 queue& operator=(queue&& __q) 306 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value) 307 {c = _VSTD::move(__q.c); return *this;} 308#endif // _LIBCPP_CXX03_LANG 309 310 _LIBCPP_INLINE_VISIBILITY 311 explicit queue(const container_type& __c) : c(__c) {} 312#ifndef _LIBCPP_CXX03_LANG 313 _LIBCPP_INLINE_VISIBILITY 314 explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {} 315#endif // _LIBCPP_CXX03_LANG 316 template <class _Alloc> 317 _LIBCPP_INLINE_VISIBILITY 318 explicit queue(const _Alloc& __a, 319 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 320 : c(__a) {} 321 template <class _Alloc> 322 _LIBCPP_INLINE_VISIBILITY 323 queue(const queue& __q, const _Alloc& __a, 324 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 325 : c(__q.c, __a) {} 326 template <class _Alloc> 327 _LIBCPP_INLINE_VISIBILITY 328 queue(const container_type& __c, const _Alloc& __a, 329 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 330 : c(__c, __a) {} 331#ifndef _LIBCPP_CXX03_LANG 332 template <class _Alloc> 333 _LIBCPP_INLINE_VISIBILITY 334 queue(container_type&& __c, const _Alloc& __a, 335 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 336 : c(_VSTD::move(__c), __a) {} 337 template <class _Alloc> 338 _LIBCPP_INLINE_VISIBILITY 339 queue(queue&& __q, const _Alloc& __a, 340 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 341 : c(_VSTD::move(__q.c), __a) {} 342 343#endif // _LIBCPP_CXX03_LANG 344 345 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 346 bool empty() const {return c.empty();} 347 _LIBCPP_INLINE_VISIBILITY 348 size_type size() const {return c.size();} 349 350 _LIBCPP_INLINE_VISIBILITY 351 reference front() {return c.front();} 352 _LIBCPP_INLINE_VISIBILITY 353 const_reference front() const {return c.front();} 354 _LIBCPP_INLINE_VISIBILITY 355 reference back() {return c.back();} 356 _LIBCPP_INLINE_VISIBILITY 357 const_reference back() const {return c.back();} 358 359 _LIBCPP_INLINE_VISIBILITY 360 void push(const value_type& __v) {c.push_back(__v);} 361#ifndef _LIBCPP_CXX03_LANG 362 _LIBCPP_INLINE_VISIBILITY 363 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} 364 template <class... _Args> 365 _LIBCPP_INLINE_VISIBILITY 366#if _LIBCPP_STD_VER > 14 367 decltype(auto) emplace(_Args&&... __args) 368 { return c.emplace_back(_VSTD::forward<_Args>(__args)...);} 369#else 370 void emplace(_Args&&... __args) 371 { c.emplace_back(_VSTD::forward<_Args>(__args)...);} 372#endif 373#endif // _LIBCPP_CXX03_LANG 374 _LIBCPP_INLINE_VISIBILITY 375 void pop() {c.pop_front();} 376 377 _LIBCPP_INLINE_VISIBILITY 378 void swap(queue& __q) 379 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) 380 { 381 using _VSTD::swap; 382 swap(c, __q.c); 383 } 384 385 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; } 386 387 template <class _T1, class _C1> 388 friend 389 _LIBCPP_INLINE_VISIBILITY 390 bool 391 operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y); 392 393 template <class _T1, class _C1> 394 friend 395 _LIBCPP_INLINE_VISIBILITY 396 bool 397 operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y); 398}; 399 400#if _LIBCPP_STD_VER > 14 401template<class _Container, 402 class = enable_if_t<!__is_allocator<_Container>::value> 403> 404queue(_Container) 405 -> queue<typename _Container::value_type, _Container>; 406 407template<class _Container, 408 class _Alloc, 409 class = enable_if_t<!__is_allocator<_Container>::value>, 410 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> 411> 412queue(_Container, _Alloc) 413 -> queue<typename _Container::value_type, _Container>; 414#endif 415 416#if _LIBCPP_STD_VER > 20 417template <class _InputIterator, 418 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>> 419queue(_InputIterator, _InputIterator) 420 -> queue<__iter_value_type<_InputIterator>>; 421 422template <class _InputIterator, 423 class _Alloc, 424 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 425 class = __enable_if_t<__is_allocator<_Alloc>::value>> 426queue(_InputIterator, _InputIterator, _Alloc) 427 -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>; 428#endif 429 430template <class _Tp, class _Container> 431inline _LIBCPP_INLINE_VISIBILITY 432bool 433operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 434{ 435 return __x.c == __y.c; 436} 437 438template <class _Tp, class _Container> 439inline _LIBCPP_INLINE_VISIBILITY 440bool 441operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 442{ 443 return __x.c < __y.c; 444} 445 446template <class _Tp, class _Container> 447inline _LIBCPP_INLINE_VISIBILITY 448bool 449operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 450{ 451 return !(__x == __y); 452} 453 454template <class _Tp, class _Container> 455inline _LIBCPP_INLINE_VISIBILITY 456bool 457operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 458{ 459 return __y < __x; 460} 461 462template <class _Tp, class _Container> 463inline _LIBCPP_INLINE_VISIBILITY 464bool 465operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 466{ 467 return !(__x < __y); 468} 469 470template <class _Tp, class _Container> 471inline _LIBCPP_INLINE_VISIBILITY 472bool 473operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 474{ 475 return !(__y < __x); 476} 477 478template <class _Tp, class _Container> 479inline _LIBCPP_INLINE_VISIBILITY 480__enable_if_t<__is_swappable<_Container>::value, void> 481swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y) 482 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 483{ 484 __x.swap(__y); 485} 486 487template <class _Tp, class _Container, class _Alloc> 488struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> 489 : public uses_allocator<_Container, _Alloc> 490{ 491}; 492 493template <class _Tp, class _Container = vector<_Tp>, 494 class _Compare = less<typename _Container::value_type> > 495class _LIBCPP_TEMPLATE_VIS priority_queue 496{ 497public: 498 typedef _Container container_type; 499 typedef _Compare value_compare; 500 typedef typename container_type::value_type value_type; 501 typedef typename container_type::reference reference; 502 typedef typename container_type::const_reference const_reference; 503 typedef typename container_type::size_type size_type; 504 static_assert((is_same<_Tp, value_type>::value), "" ); 505 506protected: 507 container_type c; 508 value_compare comp; 509 510public: 511 _LIBCPP_INLINE_VISIBILITY 512 priority_queue() 513 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value && 514 is_nothrow_default_constructible<value_compare>::value) 515 : c(), comp() {} 516 517 _LIBCPP_INLINE_VISIBILITY 518 priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {} 519 520 _LIBCPP_INLINE_VISIBILITY 521 priority_queue& operator=(const priority_queue& __q) 522 {c = __q.c; comp = __q.comp; return *this;} 523 524#ifndef _LIBCPP_CXX03_LANG 525 _LIBCPP_INLINE_VISIBILITY 526 priority_queue(priority_queue&& __q) 527 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value && 528 is_nothrow_move_constructible<value_compare>::value) 529 : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {} 530 531 _LIBCPP_INLINE_VISIBILITY 532 priority_queue& operator=(priority_queue&& __q) 533 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value && 534 is_nothrow_move_assignable<value_compare>::value) 535 {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;} 536#endif // _LIBCPP_CXX03_LANG 537 538 _LIBCPP_INLINE_VISIBILITY 539 explicit priority_queue(const value_compare& __comp) 540 : c(), comp(__comp) {} 541 _LIBCPP_INLINE_VISIBILITY 542 priority_queue(const value_compare& __comp, const container_type& __c); 543#ifndef _LIBCPP_CXX03_LANG 544 _LIBCPP_INLINE_VISIBILITY 545 priority_queue(const value_compare& __comp, container_type&& __c); 546#endif 547 template <class _InputIter, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> > 548 _LIBCPP_INLINE_VISIBILITY 549 priority_queue(_InputIter __f, _InputIter __l, 550 const value_compare& __comp = value_compare()); 551 template <class _InputIter, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> > 552 _LIBCPP_INLINE_VISIBILITY 553 priority_queue(_InputIter __f, _InputIter __l, 554 const value_compare& __comp, const container_type& __c); 555#ifndef _LIBCPP_CXX03_LANG 556 template <class _InputIter, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> > 557 _LIBCPP_INLINE_VISIBILITY 558 priority_queue(_InputIter __f, _InputIter __l, 559 const value_compare& __comp, container_type&& __c); 560#endif // _LIBCPP_CXX03_LANG 561 template <class _Alloc> 562 _LIBCPP_INLINE_VISIBILITY 563 explicit priority_queue(const _Alloc& __a, 564 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 565 template <class _Alloc> 566 _LIBCPP_INLINE_VISIBILITY 567 priority_queue(const value_compare& __comp, const _Alloc& __a, 568 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 569 template <class _Alloc> 570 _LIBCPP_INLINE_VISIBILITY 571 priority_queue(const value_compare& __comp, const container_type& __c, 572 const _Alloc& __a, 573 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 574 template <class _Alloc> 575 _LIBCPP_INLINE_VISIBILITY 576 priority_queue(const priority_queue& __q, const _Alloc& __a, 577 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 578#ifndef _LIBCPP_CXX03_LANG 579 template <class _Alloc> 580 _LIBCPP_INLINE_VISIBILITY 581 priority_queue(const value_compare& __comp, container_type&& __c, 582 const _Alloc& __a, 583 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 584 template <class _Alloc> 585 _LIBCPP_INLINE_VISIBILITY 586 priority_queue(priority_queue&& __q, const _Alloc& __a, 587 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 588#endif // _LIBCPP_CXX03_LANG 589 590 template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> > 591 _LIBCPP_INLINE_VISIBILITY 592 priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a, 593 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 594 595 template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> > 596 _LIBCPP_INLINE_VISIBILITY 597 priority_queue(_InputIter __f, _InputIter __l, 598 const value_compare& __comp, const _Alloc& __a, 599 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 600 601 template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> > 602 _LIBCPP_INLINE_VISIBILITY 603 priority_queue(_InputIter __f, _InputIter __l, 604 const value_compare& __comp, const container_type& __c, const _Alloc& __a, 605 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 606 607#ifndef _LIBCPP_CXX03_LANG 608 template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> > 609 _LIBCPP_INLINE_VISIBILITY 610 priority_queue(_InputIter __f, _InputIter __l, 611 const value_compare& __comp, container_type&& __c, const _Alloc& __a, 612 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0); 613#endif // _LIBCPP_CXX03_LANG 614 615 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 616 bool empty() const {return c.empty();} 617 _LIBCPP_INLINE_VISIBILITY 618 size_type size() const {return c.size();} 619 _LIBCPP_INLINE_VISIBILITY 620 const_reference top() const {return c.front();} 621 622 _LIBCPP_INLINE_VISIBILITY 623 void push(const value_type& __v); 624#ifndef _LIBCPP_CXX03_LANG 625 _LIBCPP_INLINE_VISIBILITY 626 void push(value_type&& __v); 627 template <class... _Args> 628 _LIBCPP_INLINE_VISIBILITY 629 void emplace(_Args&&... __args); 630#endif // _LIBCPP_CXX03_LANG 631 _LIBCPP_INLINE_VISIBILITY 632 void pop(); 633 634 _LIBCPP_INLINE_VISIBILITY 635 void swap(priority_queue& __q) 636 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 637 __is_nothrow_swappable<value_compare>::value); 638 639 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; } 640}; 641 642#if _LIBCPP_STD_VER >= 17 643template <class _Compare, 644 class _Container, 645 class = enable_if_t<!__is_allocator<_Compare>::value>, 646 class = enable_if_t<!__is_allocator<_Container>::value> 647> 648priority_queue(_Compare, _Container) 649 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 650 651template<class _InputIterator, 652 class _Compare = less<__iter_value_type<_InputIterator>>, 653 class _Container = vector<__iter_value_type<_InputIterator>>, 654 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 655 class = enable_if_t<!__is_allocator<_Compare>::value>, 656 class = enable_if_t<!__is_allocator<_Container>::value> 657> 658priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container()) 659 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>; 660 661template<class _Compare, 662 class _Container, 663 class _Alloc, 664 class = enable_if_t<!__is_allocator<_Compare>::value>, 665 class = enable_if_t<!__is_allocator<_Container>::value>, 666 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> 667> 668priority_queue(_Compare, _Container, _Alloc) 669 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 670 671template<class _InputIterator, class _Allocator, 672 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 673 class = enable_if_t<__is_allocator<_Allocator>::value> 674> 675priority_queue(_InputIterator, _InputIterator, _Allocator) 676 -> priority_queue<__iter_value_type<_InputIterator>, 677 vector<__iter_value_type<_InputIterator>, _Allocator>, 678 less<__iter_value_type<_InputIterator>>>; 679 680template<class _InputIterator, class _Compare, class _Allocator, 681 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 682 class = enable_if_t<!__is_allocator<_Compare>::value>, 683 class = enable_if_t<__is_allocator<_Allocator>::value> 684> 685priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator) 686 -> priority_queue<__iter_value_type<_InputIterator>, 687 vector<__iter_value_type<_InputIterator>, _Allocator>, _Compare>; 688 689template<class _InputIterator, class _Compare, class _Container, class _Alloc, 690 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 691 class = enable_if_t<!__is_allocator<_Compare>::value>, 692 class = enable_if_t<!__is_allocator<_Container>::value>, 693 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> 694> 695priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc) 696 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 697#endif 698 699template <class _Tp, class _Container, class _Compare> 700inline 701priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, 702 const container_type& __c) 703 : c(__c), 704 comp(__comp) 705{ 706 _VSTD::make_heap(c.begin(), c.end(), comp); 707} 708 709#ifndef _LIBCPP_CXX03_LANG 710 711template <class _Tp, class _Container, class _Compare> 712inline 713priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 714 container_type&& __c) 715 : c(_VSTD::move(__c)), 716 comp(__comp) 717{ 718 _VSTD::make_heap(c.begin(), c.end(), comp); 719} 720 721#endif // _LIBCPP_CXX03_LANG 722 723template <class _Tp, class _Container, class _Compare> 724template <class _InputIter, class> 725inline 726priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 727 const value_compare& __comp) 728 : c(__f, __l), 729 comp(__comp) 730{ 731 _VSTD::make_heap(c.begin(), c.end(), comp); 732} 733 734template <class _Tp, class _Container, class _Compare> 735template <class _InputIter, class> 736inline 737priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 738 const value_compare& __comp, 739 const container_type& __c) 740 : c(__c), 741 comp(__comp) 742{ 743 c.insert(c.end(), __f, __l); 744 _VSTD::make_heap(c.begin(), c.end(), comp); 745} 746 747#ifndef _LIBCPP_CXX03_LANG 748 749template <class _Tp, class _Container, class _Compare> 750template <class _InputIter, class> 751inline 752priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 753 const value_compare& __comp, 754 container_type&& __c) 755 : c(_VSTD::move(__c)), 756 comp(__comp) 757{ 758 c.insert(c.end(), __f, __l); 759 _VSTD::make_heap(c.begin(), c.end(), comp); 760} 761 762#endif // _LIBCPP_CXX03_LANG 763 764template <class _Tp, class _Container, class _Compare> 765template <class _Alloc> 766inline 767priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a, 768 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 769 : c(__a) 770{ 771} 772 773template <class _Tp, class _Container, class _Compare> 774template <class _Alloc> 775inline 776priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 777 const _Alloc& __a, 778 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 779 : c(__a), 780 comp(__comp) 781{ 782} 783 784template <class _Tp, class _Container, class _Compare> 785template <class _Alloc> 786inline 787priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 788 const container_type& __c, 789 const _Alloc& __a, 790 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 791 : c(__c, __a), 792 comp(__comp) 793{ 794 _VSTD::make_heap(c.begin(), c.end(), comp); 795} 796 797template <class _Tp, class _Container, class _Compare> 798template <class _Alloc> 799inline 800priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, 801 const _Alloc& __a, 802 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 803 : c(__q.c, __a), 804 comp(__q.comp) 805{ 806} 807 808#ifndef _LIBCPP_CXX03_LANG 809 810template <class _Tp, class _Container, class _Compare> 811template <class _Alloc> 812inline 813priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 814 container_type&& __c, 815 const _Alloc& __a, 816 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 817 : c(_VSTD::move(__c), __a), 818 comp(__comp) 819{ 820 _VSTD::make_heap(c.begin(), c.end(), comp); 821} 822 823template <class _Tp, class _Container, class _Compare> 824template <class _Alloc> 825inline 826priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, 827 const _Alloc& __a, 828 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 829 : c(_VSTD::move(__q.c), __a), 830 comp(_VSTD::move(__q.comp)) 831{ 832} 833 834#endif // _LIBCPP_CXX03_LANG 835 836template <class _Tp, class _Container, class _Compare> 837template <class _InputIter, class _Alloc, class> 838inline 839priority_queue<_Tp, _Container, _Compare>::priority_queue( 840 _InputIter __f, _InputIter __l, const _Alloc& __a, 841 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 842 : c(__f, __l, __a), 843 comp() 844{ 845 _VSTD::make_heap(c.begin(), c.end(), comp); 846} 847 848template <class _Tp, class _Container, class _Compare> 849template <class _InputIter, class _Alloc, class> 850inline 851priority_queue<_Tp, _Container, _Compare>::priority_queue( 852 _InputIter __f, _InputIter __l, 853 const value_compare& __comp, const _Alloc& __a, 854 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 855 : c(__f, __l, __a), 856 comp(__comp) 857{ 858 _VSTD::make_heap(c.begin(), c.end(), comp); 859} 860 861template <class _Tp, class _Container, class _Compare> 862template <class _InputIter, class _Alloc, class> 863inline 864priority_queue<_Tp, _Container, _Compare>::priority_queue( 865 _InputIter __f, _InputIter __l, 866 const value_compare& __comp, const container_type& __c, const _Alloc& __a, 867 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 868 : c(__c, __a), 869 comp(__comp) 870{ 871 c.insert(c.end(), __f, __l); 872 _VSTD::make_heap(c.begin(), c.end(), comp); 873} 874 875#ifndef _LIBCPP_CXX03_LANG 876template <class _Tp, class _Container, class _Compare> 877template <class _InputIter, class _Alloc, class> 878inline 879priority_queue<_Tp, _Container, _Compare>::priority_queue( 880 _InputIter __f, _InputIter __l, const value_compare& __comp, 881 container_type&& __c, const _Alloc& __a, 882 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 883 : c(_VSTD::move(__c), __a), 884 comp(__comp) 885{ 886 c.insert(c.end(), __f, __l); 887 _VSTD::make_heap(c.begin(), c.end(), comp); 888} 889#endif // _LIBCPP_CXX03_LANG 890 891template <class _Tp, class _Container, class _Compare> 892inline 893void 894priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) 895{ 896 c.push_back(__v); 897 _VSTD::push_heap(c.begin(), c.end(), comp); 898} 899 900#ifndef _LIBCPP_CXX03_LANG 901 902template <class _Tp, class _Container, class _Compare> 903inline 904void 905priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) 906{ 907 c.push_back(_VSTD::move(__v)); 908 _VSTD::push_heap(c.begin(), c.end(), comp); 909} 910 911template <class _Tp, class _Container, class _Compare> 912template <class... _Args> 913inline 914void 915priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) 916{ 917 c.emplace_back(_VSTD::forward<_Args>(__args)...); 918 _VSTD::push_heap(c.begin(), c.end(), comp); 919} 920 921#endif // _LIBCPP_CXX03_LANG 922 923template <class _Tp, class _Container, class _Compare> 924inline 925void 926priority_queue<_Tp, _Container, _Compare>::pop() 927{ 928 _VSTD::pop_heap(c.begin(), c.end(), comp); 929 c.pop_back(); 930} 931 932template <class _Tp, class _Container, class _Compare> 933inline 934void 935priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q) 936 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 937 __is_nothrow_swappable<value_compare>::value) 938{ 939 using _VSTD::swap; 940 swap(c, __q.c); 941 swap(comp, __q.comp); 942} 943 944template <class _Tp, class _Container, class _Compare> 945inline _LIBCPP_INLINE_VISIBILITY 946__enable_if_t< 947 __is_swappable<_Container>::value && __is_swappable<_Compare>::value, 948 void 949> 950swap(priority_queue<_Tp, _Container, _Compare>& __x, 951 priority_queue<_Tp, _Container, _Compare>& __y) 952 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 953{ 954 __x.swap(__y); 955} 956 957template <class _Tp, class _Container, class _Compare, class _Alloc> 958struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> 959 : public uses_allocator<_Container, _Alloc> 960{ 961}; 962 963_LIBCPP_END_NAMESPACE_STD 964 965#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 966# include <concepts> 967# include <functional> 968#endif 969 970#endif // _LIBCPP_QUEUE 971