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