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