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