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#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES 235# include <functional> 236#endif 237 238// standard-mandated includes 239#include <compare> 240#include <initializer_list> 241 242#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 243# pragma GCC system_header 244#endif 245 246_LIBCPP_BEGIN_NAMESPACE_STD 247 248template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue; 249 250template <class _Tp, class _Container> 251_LIBCPP_INLINE_VISIBILITY 252bool 253operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 254 255template <class _Tp, class _Container> 256_LIBCPP_INLINE_VISIBILITY 257bool 258operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 259 260template <class _Tp, class _Container /*= deque<_Tp>*/> 261class _LIBCPP_TEMPLATE_VIS queue 262{ 263public: 264 typedef _Container container_type; 265 typedef typename container_type::value_type value_type; 266 typedef typename container_type::reference reference; 267 typedef typename container_type::const_reference const_reference; 268 typedef typename container_type::size_type size_type; 269 static_assert((is_same<_Tp, value_type>::value), "" ); 270 271protected: 272 container_type c; 273 274public: 275 _LIBCPP_INLINE_VISIBILITY 276 queue() 277 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) 278 : c() {} 279 280 _LIBCPP_INLINE_VISIBILITY 281 queue(const queue& __q) : c(__q.c) {} 282 283#if _LIBCPP_STD_VER > 20 284 template <class _InputIterator, 285 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>> 286 _LIBCPP_HIDE_FROM_ABI 287 queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {} 288 289 template <class _InputIterator, 290 class _Alloc, 291 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 292 class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>> 293 _LIBCPP_HIDE_FROM_ABI 294 queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc) : c(__first, __second, __alloc) {} 295#endif 296 297 _LIBCPP_INLINE_VISIBILITY 298 queue& operator=(const queue& __q) {c = __q.c; return *this;} 299 300#ifndef _LIBCPP_CXX03_LANG 301 _LIBCPP_INLINE_VISIBILITY 302 queue(queue&& __q) 303 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value) 304 : c(_VSTD::move(__q.c)) {} 305 306 _LIBCPP_INLINE_VISIBILITY 307 queue& operator=(queue&& __q) 308 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value) 309 {c = _VSTD::move(__q.c); return *this;} 310#endif // _LIBCPP_CXX03_LANG 311 312 _LIBCPP_INLINE_VISIBILITY 313 explicit queue(const container_type& __c) : c(__c) {} 314#ifndef _LIBCPP_CXX03_LANG 315 _LIBCPP_INLINE_VISIBILITY 316 explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {} 317#endif // _LIBCPP_CXX03_LANG 318 template <class _Alloc> 319 _LIBCPP_INLINE_VISIBILITY 320 explicit queue(const _Alloc& __a, 321 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 322 : c(__a) {} 323 template <class _Alloc> 324 _LIBCPP_INLINE_VISIBILITY 325 queue(const queue& __q, const _Alloc& __a, 326 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 327 : c(__q.c, __a) {} 328 template <class _Alloc> 329 _LIBCPP_INLINE_VISIBILITY 330 queue(const container_type& __c, const _Alloc& __a, 331 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 332 : c(__c, __a) {} 333#ifndef _LIBCPP_CXX03_LANG 334 template <class _Alloc> 335 _LIBCPP_INLINE_VISIBILITY 336 queue(container_type&& __c, const _Alloc& __a, 337 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 338 : c(_VSTD::move(__c), __a) {} 339 template <class _Alloc> 340 _LIBCPP_INLINE_VISIBILITY 341 queue(queue&& __q, const _Alloc& __a, 342 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 343 : c(_VSTD::move(__q.c), __a) {} 344 345#endif // _LIBCPP_CXX03_LANG 346 347 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 348 bool empty() const {return c.empty();} 349 _LIBCPP_INLINE_VISIBILITY 350 size_type size() const {return c.size();} 351 352 _LIBCPP_INLINE_VISIBILITY 353 reference front() {return c.front();} 354 _LIBCPP_INLINE_VISIBILITY 355 const_reference front() const {return c.front();} 356 _LIBCPP_INLINE_VISIBILITY 357 reference back() {return c.back();} 358 _LIBCPP_INLINE_VISIBILITY 359 const_reference back() const {return c.back();} 360 361 _LIBCPP_INLINE_VISIBILITY 362 void push(const value_type& __v) {c.push_back(__v);} 363#ifndef _LIBCPP_CXX03_LANG 364 _LIBCPP_INLINE_VISIBILITY 365 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} 366 template <class... _Args> 367 _LIBCPP_INLINE_VISIBILITY 368#if _LIBCPP_STD_VER > 14 369 decltype(auto) emplace(_Args&&... __args) 370 { return c.emplace_back(_VSTD::forward<_Args>(__args)...);} 371#else 372 void emplace(_Args&&... __args) 373 { c.emplace_back(_VSTD::forward<_Args>(__args)...);} 374#endif 375#endif // _LIBCPP_CXX03_LANG 376 _LIBCPP_INLINE_VISIBILITY 377 void pop() {c.pop_front();} 378 379 _LIBCPP_INLINE_VISIBILITY 380 void swap(queue& __q) 381 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) 382 { 383 using _VSTD::swap; 384 swap(c, __q.c); 385 } 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 640#if _LIBCPP_STD_VER >= 17 641template <class _Compare, 642 class _Container, 643 class = enable_if_t<!__is_allocator<_Compare>::value>, 644 class = enable_if_t<!__is_allocator<_Container>::value> 645> 646priority_queue(_Compare, _Container) 647 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 648 649template<class _InputIterator, 650 class _Compare = less<__iter_value_type<_InputIterator>>, 651 class _Container = vector<__iter_value_type<_InputIterator>>, 652 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 653 class = enable_if_t<!__is_allocator<_Compare>::value>, 654 class = enable_if_t<!__is_allocator<_Container>::value> 655> 656priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container()) 657 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>; 658 659template<class _Compare, 660 class _Container, 661 class _Alloc, 662 class = enable_if_t<!__is_allocator<_Compare>::value>, 663 class = enable_if_t<!__is_allocator<_Container>::value>, 664 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> 665> 666priority_queue(_Compare, _Container, _Alloc) 667 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 668 669template<class _InputIterator, class _Allocator, 670 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 671 class = enable_if_t<__is_allocator<_Allocator>::value> 672> 673priority_queue(_InputIterator, _InputIterator, _Allocator) 674 -> priority_queue<__iter_value_type<_InputIterator>, 675 vector<__iter_value_type<_InputIterator>, _Allocator>, 676 less<__iter_value_type<_InputIterator>>>; 677 678template<class _InputIterator, class _Compare, class _Allocator, 679 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 680 class = enable_if_t<!__is_allocator<_Compare>::value>, 681 class = enable_if_t<__is_allocator<_Allocator>::value> 682> 683priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator) 684 -> priority_queue<__iter_value_type<_InputIterator>, 685 vector<__iter_value_type<_InputIterator>, _Allocator>, _Compare>; 686 687template<class _InputIterator, class _Compare, class _Container, class _Alloc, 688 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 689 class = enable_if_t<!__is_allocator<_Compare>::value>, 690 class = enable_if_t<!__is_allocator<_Container>::value>, 691 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> 692> 693priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc) 694 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 695#endif 696 697template <class _Tp, class _Container, class _Compare> 698inline 699priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, 700 const container_type& __c) 701 : c(__c), 702 comp(__comp) 703{ 704 _VSTD::make_heap(c.begin(), c.end(), comp); 705} 706 707#ifndef _LIBCPP_CXX03_LANG 708 709template <class _Tp, class _Container, class _Compare> 710inline 711priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 712 container_type&& __c) 713 : c(_VSTD::move(__c)), 714 comp(__comp) 715{ 716 _VSTD::make_heap(c.begin(), c.end(), comp); 717} 718 719#endif // _LIBCPP_CXX03_LANG 720 721template <class _Tp, class _Container, class _Compare> 722template <class _InputIter, class> 723inline 724priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 725 const value_compare& __comp) 726 : c(__f, __l), 727 comp(__comp) 728{ 729 _VSTD::make_heap(c.begin(), c.end(), comp); 730} 731 732template <class _Tp, class _Container, class _Compare> 733template <class _InputIter, class> 734inline 735priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 736 const value_compare& __comp, 737 const container_type& __c) 738 : c(__c), 739 comp(__comp) 740{ 741 c.insert(c.end(), __f, __l); 742 _VSTD::make_heap(c.begin(), c.end(), comp); 743} 744 745#ifndef _LIBCPP_CXX03_LANG 746 747template <class _Tp, class _Container, class _Compare> 748template <class _InputIter, class> 749inline 750priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 751 const value_compare& __comp, 752 container_type&& __c) 753 : c(_VSTD::move(__c)), 754 comp(__comp) 755{ 756 c.insert(c.end(), __f, __l); 757 _VSTD::make_heap(c.begin(), c.end(), comp); 758} 759 760#endif // _LIBCPP_CXX03_LANG 761 762template <class _Tp, class _Container, class _Compare> 763template <class _Alloc> 764inline 765priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a, 766 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 767 : c(__a) 768{ 769} 770 771template <class _Tp, class _Container, class _Compare> 772template <class _Alloc> 773inline 774priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 775 const _Alloc& __a, 776 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 777 : c(__a), 778 comp(__comp) 779{ 780} 781 782template <class _Tp, class _Container, class _Compare> 783template <class _Alloc> 784inline 785priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 786 const container_type& __c, 787 const _Alloc& __a, 788 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 789 : c(__c, __a), 790 comp(__comp) 791{ 792 _VSTD::make_heap(c.begin(), c.end(), comp); 793} 794 795template <class _Tp, class _Container, class _Compare> 796template <class _Alloc> 797inline 798priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, 799 const _Alloc& __a, 800 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 801 : c(__q.c, __a), 802 comp(__q.comp) 803{ 804} 805 806#ifndef _LIBCPP_CXX03_LANG 807 808template <class _Tp, class _Container, class _Compare> 809template <class _Alloc> 810inline 811priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 812 container_type&& __c, 813 const _Alloc& __a, 814 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 815 : c(_VSTD::move(__c), __a), 816 comp(__comp) 817{ 818 _VSTD::make_heap(c.begin(), c.end(), comp); 819} 820 821template <class _Tp, class _Container, class _Compare> 822template <class _Alloc> 823inline 824priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, 825 const _Alloc& __a, 826 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 827 : c(_VSTD::move(__q.c), __a), 828 comp(_VSTD::move(__q.comp)) 829{ 830} 831 832#endif // _LIBCPP_CXX03_LANG 833 834template <class _Tp, class _Container, class _Compare> 835template <class _InputIter, class _Alloc, class> 836inline 837priority_queue<_Tp, _Container, _Compare>::priority_queue( 838 _InputIter __f, _InputIter __l, const _Alloc& __a, 839 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 840 : c(__f, __l, __a), 841 comp() 842{ 843 _VSTD::make_heap(c.begin(), c.end(), comp); 844} 845 846template <class _Tp, class _Container, class _Compare> 847template <class _InputIter, class _Alloc, class> 848inline 849priority_queue<_Tp, _Container, _Compare>::priority_queue( 850 _InputIter __f, _InputIter __l, 851 const value_compare& __comp, const _Alloc& __a, 852 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 853 : c(__f, __l, __a), 854 comp(__comp) 855{ 856 _VSTD::make_heap(c.begin(), c.end(), comp); 857} 858 859template <class _Tp, class _Container, class _Compare> 860template <class _InputIter, class _Alloc, class> 861inline 862priority_queue<_Tp, _Container, _Compare>::priority_queue( 863 _InputIter __f, _InputIter __l, 864 const value_compare& __comp, const container_type& __c, const _Alloc& __a, 865 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 866 : c(__c, __a), 867 comp(__comp) 868{ 869 c.insert(c.end(), __f, __l); 870 _VSTD::make_heap(c.begin(), c.end(), comp); 871} 872 873#ifndef _LIBCPP_CXX03_LANG 874template <class _Tp, class _Container, class _Compare> 875template <class _InputIter, class _Alloc, class> 876inline 877priority_queue<_Tp, _Container, _Compare>::priority_queue( 878 _InputIter __f, _InputIter __l, const value_compare& __comp, 879 container_type&& __c, const _Alloc& __a, 880 __enable_if_t<uses_allocator<container_type, _Alloc>::value>*) 881 : c(_VSTD::move(__c), __a), 882 comp(__comp) 883{ 884 c.insert(c.end(), __f, __l); 885 _VSTD::make_heap(c.begin(), c.end(), comp); 886} 887#endif // _LIBCPP_CXX03_LANG 888 889template <class _Tp, class _Container, class _Compare> 890inline 891void 892priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) 893{ 894 c.push_back(__v); 895 _VSTD::push_heap(c.begin(), c.end(), comp); 896} 897 898#ifndef _LIBCPP_CXX03_LANG 899 900template <class _Tp, class _Container, class _Compare> 901inline 902void 903priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) 904{ 905 c.push_back(_VSTD::move(__v)); 906 _VSTD::push_heap(c.begin(), c.end(), comp); 907} 908 909template <class _Tp, class _Container, class _Compare> 910template <class... _Args> 911inline 912void 913priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) 914{ 915 c.emplace_back(_VSTD::forward<_Args>(__args)...); 916 _VSTD::push_heap(c.begin(), c.end(), comp); 917} 918 919#endif // _LIBCPP_CXX03_LANG 920 921template <class _Tp, class _Container, class _Compare> 922inline 923void 924priority_queue<_Tp, _Container, _Compare>::pop() 925{ 926 _VSTD::pop_heap(c.begin(), c.end(), comp); 927 c.pop_back(); 928} 929 930template <class _Tp, class _Container, class _Compare> 931inline 932void 933priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q) 934 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 935 __is_nothrow_swappable<value_compare>::value) 936{ 937 using _VSTD::swap; 938 swap(c, __q.c); 939 swap(comp, __q.comp); 940} 941 942template <class _Tp, class _Container, class _Compare> 943inline _LIBCPP_INLINE_VISIBILITY 944__enable_if_t< 945 __is_swappable<_Container>::value && __is_swappable<_Compare>::value, 946 void 947> 948swap(priority_queue<_Tp, _Container, _Compare>& __x, 949 priority_queue<_Tp, _Container, _Compare>& __y) 950 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 951{ 952 __x.swap(__y); 953} 954 955template <class _Tp, class _Container, class _Compare, class _Alloc> 956struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> 957 : public uses_allocator<_Container, _Alloc> 958{ 959}; 960 961_LIBCPP_END_NAMESPACE_STD 962 963#endif // _LIBCPP_QUEUE 964