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> void emplace(Args&&... args); 67 void pop(); 68 69 void swap(queue& q) noexcept(noexcept(swap(c, q.c))); 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(noexcept(swap(c, q.c)) && noexcept(swap(comp.q.comp))); 157}; 158 159template <class T, class Container, class Compare> 160 void swap(priority_queue<T, Container, Compare>& x, 161 priority_queue<T, Container, Compare>& y) 162 noexcept(noexcept(x.swap(y))); 163 164} // std 165 166*/ 167 168#include <__config> 169#include <deque> 170#include <vector> 171#include <functional> 172#include <algorithm> 173 174#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 175#pragma GCC system_header 176#endif 177 178_LIBCPP_BEGIN_NAMESPACE_STD 179 180template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TYPE_VIS_ONLY queue; 181 182template <class _Tp, class _Container> 183_LIBCPP_INLINE_VISIBILITY 184bool 185operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 186 187template <class _Tp, class _Container> 188_LIBCPP_INLINE_VISIBILITY 189bool 190operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 191 192template <class _Tp, class _Container /*= deque<_Tp>*/> 193class _LIBCPP_TYPE_VIS_ONLY queue 194{ 195public: 196 typedef _Container container_type; 197 typedef typename container_type::value_type value_type; 198 typedef typename container_type::reference reference; 199 typedef typename container_type::const_reference const_reference; 200 typedef typename container_type::size_type size_type; 201 static_assert((is_same<_Tp, value_type>::value), "" ); 202 203protected: 204 container_type c; 205 206public: 207 _LIBCPP_INLINE_VISIBILITY 208 queue() 209 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) 210 : c() {} 211 212 _LIBCPP_INLINE_VISIBILITY 213 queue(const queue& __q) : c(__q.c) {} 214 215#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 216 _LIBCPP_INLINE_VISIBILITY 217 queue(queue&& __q) 218 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value) 219 : c(_VSTD::move(__q.c)) {} 220#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 221 222 _LIBCPP_INLINE_VISIBILITY 223 queue& operator=(const queue& __q) {c = __q.c; return *this;} 224 225#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 226 _LIBCPP_INLINE_VISIBILITY 227 queue& operator=(queue&& __q) 228 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value) 229 {c = _VSTD::move(__q.c); return *this;} 230#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 231 232 _LIBCPP_INLINE_VISIBILITY 233 explicit queue(const container_type& __c) : c(__c) {} 234#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 235 _LIBCPP_INLINE_VISIBILITY 236 explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {} 237#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 238 template <class _Alloc> 239 _LIBCPP_INLINE_VISIBILITY 240 explicit queue(const _Alloc& __a, 241 typename enable_if<uses_allocator<container_type, 242 _Alloc>::value>::type* = 0) 243 : c(__a) {} 244 template <class _Alloc> 245 _LIBCPP_INLINE_VISIBILITY 246 queue(const queue& __q, const _Alloc& __a, 247 typename enable_if<uses_allocator<container_type, 248 _Alloc>::value>::type* = 0) 249 : c(__q.c, __a) {} 250 template <class _Alloc> 251 _LIBCPP_INLINE_VISIBILITY 252 queue(const container_type& __c, const _Alloc& __a, 253 typename enable_if<uses_allocator<container_type, 254 _Alloc>::value>::type* = 0) 255 : c(__c, __a) {} 256#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 257 template <class _Alloc> 258 _LIBCPP_INLINE_VISIBILITY 259 queue(container_type&& __c, const _Alloc& __a, 260 typename enable_if<uses_allocator<container_type, 261 _Alloc>::value>::type* = 0) 262 : c(_VSTD::move(__c), __a) {} 263 template <class _Alloc> 264 _LIBCPP_INLINE_VISIBILITY 265 queue(queue&& __q, const _Alloc& __a, 266 typename enable_if<uses_allocator<container_type, 267 _Alloc>::value>::type* = 0) 268 : c(_VSTD::move(__q.c), __a) {} 269 270#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 271 272 _LIBCPP_INLINE_VISIBILITY 273 bool empty() const {return c.empty();} 274 _LIBCPP_INLINE_VISIBILITY 275 size_type size() const {return c.size();} 276 277 _LIBCPP_INLINE_VISIBILITY 278 reference front() {return c.front();} 279 _LIBCPP_INLINE_VISIBILITY 280 const_reference front() const {return c.front();} 281 _LIBCPP_INLINE_VISIBILITY 282 reference back() {return c.back();} 283 _LIBCPP_INLINE_VISIBILITY 284 const_reference back() const {return c.back();} 285 286 _LIBCPP_INLINE_VISIBILITY 287 void push(const value_type& __v) {c.push_back(__v);} 288#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 289 _LIBCPP_INLINE_VISIBILITY 290 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} 291#ifndef _LIBCPP_HAS_NO_VARIADICS 292 template <class... _Args> 293 _LIBCPP_INLINE_VISIBILITY 294 void emplace(_Args&&... __args) 295 {c.emplace_back(_VSTD::forward<_Args>(__args)...);} 296#endif // _LIBCPP_HAS_NO_VARIADICS 297#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 298 _LIBCPP_INLINE_VISIBILITY 299 void pop() {c.pop_front();} 300 301 _LIBCPP_INLINE_VISIBILITY 302 void swap(queue& __q) 303 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) 304 { 305 using _VSTD::swap; 306 swap(c, __q.c); 307 } 308 309 template <class _T1, class _C1> 310 friend 311 _LIBCPP_INLINE_VISIBILITY 312 bool 313 operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y); 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 322template <class _Tp, class _Container> 323inline _LIBCPP_INLINE_VISIBILITY 324bool 325operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 326{ 327 return __x.c == __y.c; 328} 329 330template <class _Tp, class _Container> 331inline _LIBCPP_INLINE_VISIBILITY 332bool 333operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 334{ 335 return __x.c < __y.c; 336} 337 338template <class _Tp, class _Container> 339inline _LIBCPP_INLINE_VISIBILITY 340bool 341operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 342{ 343 return !(__x == __y); 344} 345 346template <class _Tp, class _Container> 347inline _LIBCPP_INLINE_VISIBILITY 348bool 349operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 350{ 351 return __y < __x; 352} 353 354template <class _Tp, class _Container> 355inline _LIBCPP_INLINE_VISIBILITY 356bool 357operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 358{ 359 return !(__x < __y); 360} 361 362template <class _Tp, class _Container> 363inline _LIBCPP_INLINE_VISIBILITY 364bool 365operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 366{ 367 return !(__y < __x); 368} 369 370template <class _Tp, class _Container> 371inline _LIBCPP_INLINE_VISIBILITY 372void 373swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y) 374 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 375{ 376 __x.swap(__y); 377} 378 379template <class _Tp, class _Container, class _Alloc> 380struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<queue<_Tp, _Container>, _Alloc> 381 : public uses_allocator<_Container, _Alloc> 382{ 383}; 384 385template <class _Tp, class _Container = vector<_Tp>, 386 class _Compare = less<typename _Container::value_type> > 387class _LIBCPP_TYPE_VIS_ONLY priority_queue 388{ 389public: 390 typedef _Container container_type; 391 typedef _Compare value_compare; 392 typedef typename container_type::value_type value_type; 393 typedef typename container_type::reference reference; 394 typedef typename container_type::const_reference const_reference; 395 typedef typename container_type::size_type size_type; 396 static_assert((is_same<_Tp, value_type>::value), "" ); 397 398protected: 399 container_type c; 400 value_compare comp; 401 402public: 403 _LIBCPP_INLINE_VISIBILITY 404 priority_queue() 405 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value && 406 is_nothrow_default_constructible<value_compare>::value) 407 : c(), comp() {} 408 409 _LIBCPP_INLINE_VISIBILITY 410 priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {} 411 412#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 413 _LIBCPP_INLINE_VISIBILITY 414 priority_queue(priority_queue&& __q) 415 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value && 416 is_nothrow_move_constructible<value_compare>::value) 417 : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {} 418#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 419 420 _LIBCPP_INLINE_VISIBILITY 421 priority_queue& operator=(const priority_queue& __q) 422 {c = __q.c; comp = __q.comp; return *this;} 423 424#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 425 _LIBCPP_INLINE_VISIBILITY 426 priority_queue& operator=(priority_queue&& __q) 427 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value && 428 is_nothrow_move_assignable<value_compare>::value) 429 {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;} 430#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 431 432 _LIBCPP_INLINE_VISIBILITY 433 explicit priority_queue(const value_compare& __comp) 434 : c(), comp(__comp) {} 435 priority_queue(const value_compare& __comp, const container_type& __c); 436#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 437 explicit priority_queue(const value_compare& __comp, container_type&& __c); 438#endif 439 template <class _InputIter> 440 priority_queue(_InputIter __f, _InputIter __l, 441 const value_compare& __comp = value_compare()); 442 template <class _InputIter> 443 priority_queue(_InputIter __f, _InputIter __l, 444 const value_compare& __comp, const container_type& __c); 445#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 446 template <class _InputIter> 447 priority_queue(_InputIter __f, _InputIter __l, 448 const value_compare& __comp, container_type&& __c); 449#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 450 template <class _Alloc> 451 explicit priority_queue(const _Alloc& __a, 452 typename enable_if<uses_allocator<container_type, 453 _Alloc>::value>::type* = 0); 454 template <class _Alloc> 455 priority_queue(const value_compare& __comp, const _Alloc& __a, 456 typename enable_if<uses_allocator<container_type, 457 _Alloc>::value>::type* = 0); 458 template <class _Alloc> 459 priority_queue(const value_compare& __comp, const container_type& __c, 460 const _Alloc& __a, 461 typename enable_if<uses_allocator<container_type, 462 _Alloc>::value>::type* = 0); 463 template <class _Alloc> 464 priority_queue(const priority_queue& __q, const _Alloc& __a, 465 typename enable_if<uses_allocator<container_type, 466 _Alloc>::value>::type* = 0); 467#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 468 template <class _Alloc> 469 priority_queue(const value_compare& __comp, container_type&& __c, 470 const _Alloc& __a, 471 typename enable_if<uses_allocator<container_type, 472 _Alloc>::value>::type* = 0); 473 template <class _Alloc> 474 priority_queue(priority_queue&& __q, const _Alloc& __a, 475 typename enable_if<uses_allocator<container_type, 476 _Alloc>::value>::type* = 0); 477#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 478 479 _LIBCPP_INLINE_VISIBILITY 480 bool empty() const {return c.empty();} 481 _LIBCPP_INLINE_VISIBILITY 482 size_type size() const {return c.size();} 483 _LIBCPP_INLINE_VISIBILITY 484 const_reference top() const {return c.front();} 485 486 void push(const value_type& __v); 487#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 488 void push(value_type&& __v); 489#ifndef _LIBCPP_HAS_NO_VARIADICS 490 template <class... _Args> void emplace(_Args&&... __args); 491#endif 492#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 493 void pop(); 494 495 void swap(priority_queue& __q) 496 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 497 __is_nothrow_swappable<value_compare>::value); 498}; 499 500template <class _Tp, class _Container, class _Compare> 501inline _LIBCPP_INLINE_VISIBILITY 502priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, 503 const container_type& __c) 504 : c(__c), 505 comp(__comp) 506{ 507 _VSTD::make_heap(c.begin(), c.end(), comp); 508} 509 510#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 511 512template <class _Tp, class _Container, class _Compare> 513inline _LIBCPP_INLINE_VISIBILITY 514priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 515 container_type&& __c) 516 : c(_VSTD::move(__c)), 517 comp(__comp) 518{ 519 _VSTD::make_heap(c.begin(), c.end(), comp); 520} 521 522#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 523 524template <class _Tp, class _Container, class _Compare> 525template <class _InputIter> 526inline _LIBCPP_INLINE_VISIBILITY 527priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 528 const value_compare& __comp) 529 : c(__f, __l), 530 comp(__comp) 531{ 532 _VSTD::make_heap(c.begin(), c.end(), comp); 533} 534 535template <class _Tp, class _Container, class _Compare> 536template <class _InputIter> 537inline _LIBCPP_INLINE_VISIBILITY 538priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 539 const value_compare& __comp, 540 const container_type& __c) 541 : c(__c), 542 comp(__comp) 543{ 544 c.insert(c.end(), __f, __l); 545 _VSTD::make_heap(c.begin(), c.end(), comp); 546} 547 548#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 549 550template <class _Tp, class _Container, class _Compare> 551template <class _InputIter> 552inline _LIBCPP_INLINE_VISIBILITY 553priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 554 const value_compare& __comp, 555 container_type&& __c) 556 : c(_VSTD::move(__c)), 557 comp(__comp) 558{ 559 c.insert(c.end(), __f, __l); 560 _VSTD::make_heap(c.begin(), c.end(), comp); 561} 562 563#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 564 565template <class _Tp, class _Container, class _Compare> 566template <class _Alloc> 567inline _LIBCPP_INLINE_VISIBILITY 568priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a, 569 typename enable_if<uses_allocator<container_type, 570 _Alloc>::value>::type*) 571 : c(__a) 572{ 573} 574 575template <class _Tp, class _Container, class _Compare> 576template <class _Alloc> 577inline _LIBCPP_INLINE_VISIBILITY 578priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 579 const _Alloc& __a, 580 typename enable_if<uses_allocator<container_type, 581 _Alloc>::value>::type*) 582 : c(__a), 583 comp(__comp) 584{ 585} 586 587template <class _Tp, class _Container, class _Compare> 588template <class _Alloc> 589inline _LIBCPP_INLINE_VISIBILITY 590priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 591 const container_type& __c, 592 const _Alloc& __a, 593 typename enable_if<uses_allocator<container_type, 594 _Alloc>::value>::type*) 595 : c(__c, __a), 596 comp(__comp) 597{ 598 _VSTD::make_heap(c.begin(), c.end(), comp); 599} 600 601template <class _Tp, class _Container, class _Compare> 602template <class _Alloc> 603inline _LIBCPP_INLINE_VISIBILITY 604priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, 605 const _Alloc& __a, 606 typename enable_if<uses_allocator<container_type, 607 _Alloc>::value>::type*) 608 : c(__q.c, __a), 609 comp(__q.comp) 610{ 611 _VSTD::make_heap(c.begin(), c.end(), comp); 612} 613 614#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 615 616template <class _Tp, class _Container, class _Compare> 617template <class _Alloc> 618inline _LIBCPP_INLINE_VISIBILITY 619priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 620 container_type&& __c, 621 const _Alloc& __a, 622 typename enable_if<uses_allocator<container_type, 623 _Alloc>::value>::type*) 624 : c(_VSTD::move(__c), __a), 625 comp(__comp) 626{ 627 _VSTD::make_heap(c.begin(), c.end(), comp); 628} 629 630template <class _Tp, class _Container, class _Compare> 631template <class _Alloc> 632inline _LIBCPP_INLINE_VISIBILITY 633priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, 634 const _Alloc& __a, 635 typename enable_if<uses_allocator<container_type, 636 _Alloc>::value>::type*) 637 : c(_VSTD::move(__q.c), __a), 638 comp(_VSTD::move(__q.comp)) 639{ 640 _VSTD::make_heap(c.begin(), c.end(), comp); 641} 642 643#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 644 645template <class _Tp, class _Container, class _Compare> 646inline _LIBCPP_INLINE_VISIBILITY 647void 648priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) 649{ 650 c.push_back(__v); 651 _VSTD::push_heap(c.begin(), c.end(), comp); 652} 653 654#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 655 656template <class _Tp, class _Container, class _Compare> 657inline _LIBCPP_INLINE_VISIBILITY 658void 659priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) 660{ 661 c.push_back(_VSTD::move(__v)); 662 _VSTD::push_heap(c.begin(), c.end(), comp); 663} 664 665#ifndef _LIBCPP_HAS_NO_VARIADICS 666 667template <class _Tp, class _Container, class _Compare> 668template <class... _Args> 669inline _LIBCPP_INLINE_VISIBILITY 670void 671priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) 672{ 673 c.emplace_back(_VSTD::forward<_Args>(__args)...); 674 _VSTD::push_heap(c.begin(), c.end(), comp); 675} 676 677#endif // _LIBCPP_HAS_NO_VARIADICS 678#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 679 680template <class _Tp, class _Container, class _Compare> 681inline _LIBCPP_INLINE_VISIBILITY 682void 683priority_queue<_Tp, _Container, _Compare>::pop() 684{ 685 _VSTD::pop_heap(c.begin(), c.end(), comp); 686 c.pop_back(); 687} 688 689template <class _Tp, class _Container, class _Compare> 690inline _LIBCPP_INLINE_VISIBILITY 691void 692priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q) 693 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 694 __is_nothrow_swappable<value_compare>::value) 695{ 696 using _VSTD::swap; 697 swap(c, __q.c); 698 swap(comp, __q.comp); 699} 700 701template <class _Tp, class _Container, class _Compare> 702inline _LIBCPP_INLINE_VISIBILITY 703void 704swap(priority_queue<_Tp, _Container, _Compare>& __x, 705 priority_queue<_Tp, _Container, _Compare>& __y) 706 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 707{ 708 __x.swap(__y); 709} 710 711template <class _Tp, class _Container, class _Compare, class _Alloc> 712struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> 713 : public uses_allocator<_Container, _Alloc> 714{ 715}; 716 717_LIBCPP_END_NAMESPACE_STD 718 719#endif // _LIBCPP_QUEUE 720