1// -*- C++ -*- 2//===--------------------------- queue ------------------------------------===// 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 Alloc> 45 explicit queue(const Alloc& a); 46 template <class Alloc> 47 queue(const container_type& c, const Alloc& a); 48 template <class Alloc> 49 queue(container_type&& c, const Alloc& a); 50 template <class Alloc> 51 queue(const queue& q, const Alloc& a); 52 template <class Alloc> 53 queue(queue&& q, const Alloc& a); 54 55 bool empty() const; 56 size_type size() const; 57 58 reference front(); 59 const_reference front() const; 60 reference back(); 61 const_reference back() const; 62 63 void push(const value_type& v); 64 void push(value_type&& v); 65 template <class... Args> reference emplace(Args&&... args); // reference in C++17 66 void pop(); 67 68 void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>) 69}; 70 71template<class Container> 72 queue(Container) -> queue<typename Container::value_type, Container>; // C++17 73 74template<class Container, class Allocator> 75 queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17 76 77template <class T, class Container> 78 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y); 79 80template <class T, class Container> 81 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y); 82 83template <class T, class Container> 84 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y); 85 86template <class T, class Container> 87 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y); 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 void swap(queue<T, Container>& x, queue<T, Container>& y) 97 noexcept(noexcept(x.swap(y))); 98 99template <class T, class Container = vector<T>, 100 class Compare = less<typename Container::value_type>> 101class priority_queue 102{ 103public: 104 typedef Container container_type; 105 typedef typename container_type::value_type value_type; 106 typedef typename container_type::reference reference; 107 typedef typename container_type::const_reference const_reference; 108 typedef typename container_type::size_type size_type; 109 110protected: 111 container_type c; 112 Compare comp; 113 114public: 115 priority_queue() : priority_queue(Compare()) {} // C++20 116 explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {} 117 priority_queue(const Compare& x, const Container&); 118 explicit priority_queue(const Compare& x = Compare(), Container&&= Container()); // before C++20 119 priority_queue(const Compare& x, Container&&); // C++20 120 template <class InputIterator> 121 priority_queue(InputIterator first, InputIterator last, 122 const Compare& comp = Compare()); 123 template <class InputIterator> 124 priority_queue(InputIterator first, InputIterator last, 125 const Compare& comp, const container_type& c); 126 template <class InputIterator> 127 priority_queue(InputIterator first, InputIterator last, 128 const Compare& comp, container_type&& c); 129 template <class Alloc> 130 explicit priority_queue(const Alloc& a); 131 template <class Alloc> 132 priority_queue(const Compare& comp, const Alloc& a); 133 template <class Alloc> 134 priority_queue(const Compare& comp, const container_type& c, 135 const Alloc& a); 136 template <class Alloc> 137 priority_queue(const Compare& comp, container_type&& c, 138 const Alloc& a); 139 template <class Alloc> 140 priority_queue(const priority_queue& q, const Alloc& a); 141 template <class Alloc> 142 priority_queue(priority_queue&& q, const Alloc& a); 143 144 bool empty() const; 145 size_type size() const; 146 const_reference top() const; 147 148 void push(const value_type& v); 149 void push(value_type&& v); 150 template <class... Args> void emplace(Args&&... args); 151 void pop(); 152 153 void swap(priority_queue& q) 154 noexcept(is_nothrow_swappable_v<Container> && 155 is_nothrow_swappable_v<Comp>) 156}; 157 158template <class Compare, class Container> 159priority_queue(Compare, Container) 160 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17 161 162template<class InputIterator, 163 class Compare = less<typename iterator_traits<InputIterator>::value_type>, 164 class Container = vector<typename iterator_traits<InputIterator>::value_type>> 165priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container()) 166 -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>; // C++17 167 168template<class Compare, class Container, class Allocator> 169priority_queue(Compare, Container, Allocator) 170 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17 171 172template <class T, class Container, class Compare> 173 void swap(priority_queue<T, Container, Compare>& x, 174 priority_queue<T, Container, Compare>& y) 175 noexcept(noexcept(x.swap(y))); 176 177} // std 178 179*/ 180 181#include <__config> 182#include <deque> 183#include <vector> 184#include <functional> 185#include <algorithm> 186 187#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 188#pragma GCC system_header 189#endif 190 191_LIBCPP_BEGIN_NAMESPACE_STD 192 193template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue; 194 195template <class _Tp, class _Container> 196_LIBCPP_INLINE_VISIBILITY 197bool 198operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 199 200template <class _Tp, class _Container> 201_LIBCPP_INLINE_VISIBILITY 202bool 203operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 204 205template <class _Tp, class _Container /*= deque<_Tp>*/> 206class _LIBCPP_TEMPLATE_VIS queue 207{ 208public: 209 typedef _Container container_type; 210 typedef typename container_type::value_type value_type; 211 typedef typename container_type::reference reference; 212 typedef typename container_type::const_reference const_reference; 213 typedef typename container_type::size_type size_type; 214 static_assert((is_same<_Tp, value_type>::value), "" ); 215 216protected: 217 container_type c; 218 219public: 220 _LIBCPP_INLINE_VISIBILITY 221 queue() 222 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) 223 : c() {} 224 225 _LIBCPP_INLINE_VISIBILITY 226 queue(const queue& __q) : c(__q.c) {} 227 228 _LIBCPP_INLINE_VISIBILITY 229 queue& operator=(const queue& __q) {c = __q.c; return *this;} 230 231#ifndef _LIBCPP_CXX03_LANG 232 _LIBCPP_INLINE_VISIBILITY 233 queue(queue&& __q) 234 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value) 235 : c(_VSTD::move(__q.c)) {} 236 237 _LIBCPP_INLINE_VISIBILITY 238 queue& operator=(queue&& __q) 239 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value) 240 {c = _VSTD::move(__q.c); return *this;} 241#endif // _LIBCPP_CXX03_LANG 242 243 _LIBCPP_INLINE_VISIBILITY 244 explicit queue(const container_type& __c) : c(__c) {} 245#ifndef _LIBCPP_CXX03_LANG 246 _LIBCPP_INLINE_VISIBILITY 247 explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {} 248#endif // _LIBCPP_CXX03_LANG 249 template <class _Alloc> 250 _LIBCPP_INLINE_VISIBILITY 251 explicit queue(const _Alloc& __a, 252 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0) 253 : c(__a) {} 254 template <class _Alloc> 255 _LIBCPP_INLINE_VISIBILITY 256 queue(const queue& __q, const _Alloc& __a, 257 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0) 258 : c(__q.c, __a) {} 259 template <class _Alloc> 260 _LIBCPP_INLINE_VISIBILITY 261 queue(const container_type& __c, const _Alloc& __a, 262 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0) 263 : c(__c, __a) {} 264#ifndef _LIBCPP_CXX03_LANG 265 template <class _Alloc> 266 _LIBCPP_INLINE_VISIBILITY 267 queue(container_type&& __c, const _Alloc& __a, 268 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0) 269 : c(_VSTD::move(__c), __a) {} 270 template <class _Alloc> 271 _LIBCPP_INLINE_VISIBILITY 272 queue(queue&& __q, const _Alloc& __a, 273 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0) 274 : c(_VSTD::move(__q.c), __a) {} 275 276#endif // _LIBCPP_CXX03_LANG 277 278 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 279 bool empty() const {return c.empty();} 280 _LIBCPP_INLINE_VISIBILITY 281 size_type size() const {return c.size();} 282 283 _LIBCPP_INLINE_VISIBILITY 284 reference front() {return c.front();} 285 _LIBCPP_INLINE_VISIBILITY 286 const_reference front() const {return c.front();} 287 _LIBCPP_INLINE_VISIBILITY 288 reference back() {return c.back();} 289 _LIBCPP_INLINE_VISIBILITY 290 const_reference back() const {return c.back();} 291 292 _LIBCPP_INLINE_VISIBILITY 293 void push(const value_type& __v) {c.push_back(__v);} 294#ifndef _LIBCPP_CXX03_LANG 295 _LIBCPP_INLINE_VISIBILITY 296 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} 297 template <class... _Args> 298 _LIBCPP_INLINE_VISIBILITY 299#if _LIBCPP_STD_VER > 14 300 decltype(auto) emplace(_Args&&... __args) 301 { return c.emplace_back(_VSTD::forward<_Args>(__args)...);} 302#else 303 void emplace(_Args&&... __args) 304 { c.emplace_back(_VSTD::forward<_Args>(__args)...);} 305#endif 306#endif // _LIBCPP_CXX03_LANG 307 _LIBCPP_INLINE_VISIBILITY 308 void pop() {c.pop_front();} 309 310 _LIBCPP_INLINE_VISIBILITY 311 void swap(queue& __q) 312 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) 313 { 314 using _VSTD::swap; 315 swap(c, __q.c); 316 } 317 318 template <class _T1, class _C1> 319 friend 320 _LIBCPP_INLINE_VISIBILITY 321 bool 322 operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y); 323 324 template <class _T1, class _C1> 325 friend 326 _LIBCPP_INLINE_VISIBILITY 327 bool 328 operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y); 329}; 330 331#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 332template<class _Container, 333 class = _EnableIf<!__is_allocator<_Container>::value> 334> 335queue(_Container) 336 -> queue<typename _Container::value_type, _Container>; 337 338template<class _Container, 339 class _Alloc, 340 class = _EnableIf<!__is_allocator<_Container>::value>, 341 class = _EnableIf<__is_allocator<_Alloc>::value> 342> 343queue(_Container, _Alloc) 344 -> queue<typename _Container::value_type, _Container>; 345#endif 346 347template <class _Tp, class _Container> 348inline _LIBCPP_INLINE_VISIBILITY 349bool 350operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 351{ 352 return __x.c == __y.c; 353} 354 355template <class _Tp, class _Container> 356inline _LIBCPP_INLINE_VISIBILITY 357bool 358operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 359{ 360 return __x.c < __y.c; 361} 362 363template <class _Tp, class _Container> 364inline _LIBCPP_INLINE_VISIBILITY 365bool 366operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 367{ 368 return !(__x == __y); 369} 370 371template <class _Tp, class _Container> 372inline _LIBCPP_INLINE_VISIBILITY 373bool 374operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 375{ 376 return __y < __x; 377} 378 379template <class _Tp, class _Container> 380inline _LIBCPP_INLINE_VISIBILITY 381bool 382operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 383{ 384 return !(__x < __y); 385} 386 387template <class _Tp, class _Container> 388inline _LIBCPP_INLINE_VISIBILITY 389bool 390operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 391{ 392 return !(__y < __x); 393} 394 395template <class _Tp, class _Container> 396inline _LIBCPP_INLINE_VISIBILITY 397_EnableIf<__is_swappable<_Container>::value, void> 398swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y) 399 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 400{ 401 __x.swap(__y); 402} 403 404template <class _Tp, class _Container, class _Alloc> 405struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> 406 : public uses_allocator<_Container, _Alloc> 407{ 408}; 409 410template <class _Tp, class _Container = vector<_Tp>, 411 class _Compare = less<typename _Container::value_type> > 412class _LIBCPP_TEMPLATE_VIS priority_queue 413{ 414public: 415 typedef _Container container_type; 416 typedef _Compare value_compare; 417 typedef typename container_type::value_type value_type; 418 typedef typename container_type::reference reference; 419 typedef typename container_type::const_reference const_reference; 420 typedef typename container_type::size_type size_type; 421 static_assert((is_same<_Tp, value_type>::value), "" ); 422 423protected: 424 container_type c; 425 value_compare comp; 426 427public: 428 _LIBCPP_INLINE_VISIBILITY 429 priority_queue() 430 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value && 431 is_nothrow_default_constructible<value_compare>::value) 432 : c(), comp() {} 433 434 _LIBCPP_INLINE_VISIBILITY 435 priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {} 436 437 _LIBCPP_INLINE_VISIBILITY 438 priority_queue& operator=(const priority_queue& __q) 439 {c = __q.c; comp = __q.comp; return *this;} 440 441#ifndef _LIBCPP_CXX03_LANG 442 _LIBCPP_INLINE_VISIBILITY 443 priority_queue(priority_queue&& __q) 444 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value && 445 is_nothrow_move_constructible<value_compare>::value) 446 : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {} 447 448 _LIBCPP_INLINE_VISIBILITY 449 priority_queue& operator=(priority_queue&& __q) 450 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value && 451 is_nothrow_move_assignable<value_compare>::value) 452 {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;} 453#endif // _LIBCPP_CXX03_LANG 454 455 _LIBCPP_INLINE_VISIBILITY 456 explicit priority_queue(const value_compare& __comp) 457 : c(), comp(__comp) {} 458 _LIBCPP_INLINE_VISIBILITY 459 priority_queue(const value_compare& __comp, const container_type& __c); 460#ifndef _LIBCPP_CXX03_LANG 461 _LIBCPP_INLINE_VISIBILITY 462 priority_queue(const value_compare& __comp, container_type&& __c); 463#endif 464 template <class _InputIter> 465 _LIBCPP_INLINE_VISIBILITY 466 priority_queue(_InputIter __f, _InputIter __l, 467 const value_compare& __comp = value_compare()); 468 template <class _InputIter> 469 _LIBCPP_INLINE_VISIBILITY 470 priority_queue(_InputIter __f, _InputIter __l, 471 const value_compare& __comp, const container_type& __c); 472#ifndef _LIBCPP_CXX03_LANG 473 template <class _InputIter> 474 _LIBCPP_INLINE_VISIBILITY 475 priority_queue(_InputIter __f, _InputIter __l, 476 const value_compare& __comp, container_type&& __c); 477#endif // _LIBCPP_CXX03_LANG 478 template <class _Alloc> 479 _LIBCPP_INLINE_VISIBILITY 480 explicit priority_queue(const _Alloc& __a, 481 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0); 482 template <class _Alloc> 483 _LIBCPP_INLINE_VISIBILITY 484 priority_queue(const value_compare& __comp, const _Alloc& __a, 485 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0); 486 template <class _Alloc> 487 _LIBCPP_INLINE_VISIBILITY 488 priority_queue(const value_compare& __comp, const container_type& __c, 489 const _Alloc& __a, 490 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0); 491 template <class _Alloc> 492 _LIBCPP_INLINE_VISIBILITY 493 priority_queue(const priority_queue& __q, const _Alloc& __a, 494 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0); 495#ifndef _LIBCPP_CXX03_LANG 496 template <class _Alloc> 497 _LIBCPP_INLINE_VISIBILITY 498 priority_queue(const value_compare& __comp, container_type&& __c, 499 const _Alloc& __a, 500 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0); 501 template <class _Alloc> 502 _LIBCPP_INLINE_VISIBILITY 503 priority_queue(priority_queue&& __q, const _Alloc& __a, 504 _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0); 505#endif // _LIBCPP_CXX03_LANG 506 507 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 508 bool empty() const {return c.empty();} 509 _LIBCPP_INLINE_VISIBILITY 510 size_type size() const {return c.size();} 511 _LIBCPP_INLINE_VISIBILITY 512 const_reference top() const {return c.front();} 513 514 _LIBCPP_INLINE_VISIBILITY 515 void push(const value_type& __v); 516#ifndef _LIBCPP_CXX03_LANG 517 _LIBCPP_INLINE_VISIBILITY 518 void push(value_type&& __v); 519 template <class... _Args> 520 _LIBCPP_INLINE_VISIBILITY 521 void emplace(_Args&&... __args); 522#endif // _LIBCPP_CXX03_LANG 523 _LIBCPP_INLINE_VISIBILITY 524 void pop(); 525 526 _LIBCPP_INLINE_VISIBILITY 527 void swap(priority_queue& __q) 528 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 529 __is_nothrow_swappable<value_compare>::value); 530}; 531 532#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 533template <class _Compare, 534 class _Container, 535 class = _EnableIf<!__is_allocator<_Compare>::value>, 536 class = _EnableIf<!__is_allocator<_Container>::value> 537> 538priority_queue(_Compare, _Container) 539 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 540 541template<class _InputIterator, 542 class _Compare = less<__iter_value_type<_InputIterator>>, 543 class _Container = vector<__iter_value_type<_InputIterator>>, 544 class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::value>, 545 class = _EnableIf<!__is_allocator<_Compare>::value>, 546 class = _EnableIf<!__is_allocator<_Container>::value> 547> 548priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container()) 549 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>; 550 551template<class _Compare, 552 class _Container, 553 class _Alloc, 554 class = _EnableIf<!__is_allocator<_Compare>::value>, 555 class = _EnableIf<!__is_allocator<_Container>::value>, 556 class = _EnableIf<__is_allocator<_Alloc>::value> 557> 558priority_queue(_Compare, _Container, _Alloc) 559 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 560#endif 561 562template <class _Tp, class _Container, class _Compare> 563inline 564priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, 565 const container_type& __c) 566 : c(__c), 567 comp(__comp) 568{ 569 _VSTD::make_heap(c.begin(), c.end(), comp); 570} 571 572#ifndef _LIBCPP_CXX03_LANG 573 574template <class _Tp, class _Container, class _Compare> 575inline 576priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 577 container_type&& __c) 578 : c(_VSTD::move(__c)), 579 comp(__comp) 580{ 581 _VSTD::make_heap(c.begin(), c.end(), comp); 582} 583 584#endif // _LIBCPP_CXX03_LANG 585 586template <class _Tp, class _Container, class _Compare> 587template <class _InputIter> 588inline 589priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 590 const value_compare& __comp) 591 : c(__f, __l), 592 comp(__comp) 593{ 594 _VSTD::make_heap(c.begin(), c.end(), comp); 595} 596 597template <class _Tp, class _Container, class _Compare> 598template <class _InputIter> 599inline 600priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 601 const value_compare& __comp, 602 const container_type& __c) 603 : c(__c), 604 comp(__comp) 605{ 606 c.insert(c.end(), __f, __l); 607 _VSTD::make_heap(c.begin(), c.end(), comp); 608} 609 610#ifndef _LIBCPP_CXX03_LANG 611 612template <class _Tp, class _Container, class _Compare> 613template <class _InputIter> 614inline 615priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 616 const value_compare& __comp, 617 container_type&& __c) 618 : c(_VSTD::move(__c)), 619 comp(__comp) 620{ 621 c.insert(c.end(), __f, __l); 622 _VSTD::make_heap(c.begin(), c.end(), comp); 623} 624 625#endif // _LIBCPP_CXX03_LANG 626 627template <class _Tp, class _Container, class _Compare> 628template <class _Alloc> 629inline 630priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a, 631 _EnableIf<uses_allocator<container_type, _Alloc>::value>*) 632 : c(__a) 633{ 634} 635 636template <class _Tp, class _Container, class _Compare> 637template <class _Alloc> 638inline 639priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 640 const _Alloc& __a, 641 _EnableIf<uses_allocator<container_type, _Alloc>::value>*) 642 : c(__a), 643 comp(__comp) 644{ 645} 646 647template <class _Tp, class _Container, class _Compare> 648template <class _Alloc> 649inline 650priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 651 const container_type& __c, 652 const _Alloc& __a, 653 _EnableIf<uses_allocator<container_type, _Alloc>::value>*) 654 : c(__c, __a), 655 comp(__comp) 656{ 657 _VSTD::make_heap(c.begin(), c.end(), comp); 658} 659 660template <class _Tp, class _Container, class _Compare> 661template <class _Alloc> 662inline 663priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, 664 const _Alloc& __a, 665 _EnableIf<uses_allocator<container_type, _Alloc>::value>*) 666 : c(__q.c, __a), 667 comp(__q.comp) 668{ 669 _VSTD::make_heap(c.begin(), c.end(), comp); 670} 671 672#ifndef _LIBCPP_CXX03_LANG 673 674template <class _Tp, class _Container, class _Compare> 675template <class _Alloc> 676inline 677priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 678 container_type&& __c, 679 const _Alloc& __a, 680 _EnableIf<uses_allocator<container_type, _Alloc>::value>*) 681 : c(_VSTD::move(__c), __a), 682 comp(__comp) 683{ 684 _VSTD::make_heap(c.begin(), c.end(), comp); 685} 686 687template <class _Tp, class _Container, class _Compare> 688template <class _Alloc> 689inline 690priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, 691 const _Alloc& __a, 692 _EnableIf<uses_allocator<container_type, _Alloc>::value>*) 693 : c(_VSTD::move(__q.c), __a), 694 comp(_VSTD::move(__q.comp)) 695{ 696 _VSTD::make_heap(c.begin(), c.end(), comp); 697} 698 699#endif // _LIBCPP_CXX03_LANG 700 701template <class _Tp, class _Container, class _Compare> 702inline 703void 704priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) 705{ 706 c.push_back(__v); 707 _VSTD::push_heap(c.begin(), c.end(), comp); 708} 709 710#ifndef _LIBCPP_CXX03_LANG 711 712template <class _Tp, class _Container, class _Compare> 713inline 714void 715priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) 716{ 717 c.push_back(_VSTD::move(__v)); 718 _VSTD::push_heap(c.begin(), c.end(), comp); 719} 720 721template <class _Tp, class _Container, class _Compare> 722template <class... _Args> 723inline 724void 725priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) 726{ 727 c.emplace_back(_VSTD::forward<_Args>(__args)...); 728 _VSTD::push_heap(c.begin(), c.end(), comp); 729} 730 731#endif // _LIBCPP_CXX03_LANG 732 733template <class _Tp, class _Container, class _Compare> 734inline 735void 736priority_queue<_Tp, _Container, _Compare>::pop() 737{ 738 _VSTD::pop_heap(c.begin(), c.end(), comp); 739 c.pop_back(); 740} 741 742template <class _Tp, class _Container, class _Compare> 743inline 744void 745priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q) 746 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 747 __is_nothrow_swappable<value_compare>::value) 748{ 749 using _VSTD::swap; 750 swap(c, __q.c); 751 swap(comp, __q.comp); 752} 753 754template <class _Tp, class _Container, class _Compare> 755inline _LIBCPP_INLINE_VISIBILITY 756_EnableIf< 757 __is_swappable<_Container>::value && __is_swappable<_Compare>::value, 758 void 759> 760swap(priority_queue<_Tp, _Container, _Compare>& __x, 761 priority_queue<_Tp, _Container, _Compare>& __y) 762 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 763{ 764 __x.swap(__y); 765} 766 767template <class _Tp, class _Container, class _Compare, class _Alloc> 768struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> 769 : public uses_allocator<_Container, _Alloc> 770{ 771}; 772 773_LIBCPP_END_NAMESPACE_STD 774 775#endif // _LIBCPP_QUEUE 776