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 17 namespace std 18 { 19 20 template <class T, class Container = deque<T>> 21 class queue 22 { 23 public: 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 30 protected: 31 container_type c; 32 33 public: 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 72 template <class T, class Container> 73 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y); 74 75 template <class T, class Container> 76 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y); 77 78 template <class T, class Container> 79 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y); 80 81 template <class T, class Container> 82 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y); 83 84 template <class T, class Container> 85 bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y); 86 87 template <class T, class Container> 88 bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y); 89 90 template <class T, class Container> 91 void swap(queue<T, Container>& x, queue<T, Container>& y) 92 noexcept(noexcept(x.swap(y))); 93 94 template <class T, class Container = vector<T>, 95 class Compare = less<typename Container::value_type>> 96 class priority_queue 97 { 98 public: 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 105 protected: 106 container_type c; 107 Compare comp; 108 109 public: 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 160 template <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 181 template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue; 182 183 template <class _Tp, class _Container> 184 _LIBCPP_INLINE_VISIBILITY 185 bool 186 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 187 188 template <class _Tp, class _Container> 189 _LIBCPP_INLINE_VISIBILITY 190 bool 191 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 192 193 template <class _Tp, class _Container /*= deque<_Tp>*/> 194 class _LIBCPP_TEMPLATE_VIS queue 195 { 196 public: 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 204 protected: 205 container_type c; 206 207 public: 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 328 template <class _Tp, class _Container> 329 inline _LIBCPP_INLINE_VISIBILITY 330 bool 331 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 332 { 333 return __x.c == __y.c; 334 } 335 336 template <class _Tp, class _Container> 337 inline _LIBCPP_INLINE_VISIBILITY 338 bool 339 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 340 { 341 return __x.c < __y.c; 342 } 343 344 template <class _Tp, class _Container> 345 inline _LIBCPP_INLINE_VISIBILITY 346 bool 347 operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 348 { 349 return !(__x == __y); 350 } 351 352 template <class _Tp, class _Container> 353 inline _LIBCPP_INLINE_VISIBILITY 354 bool 355 operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 356 { 357 return __y < __x; 358 } 359 360 template <class _Tp, class _Container> 361 inline _LIBCPP_INLINE_VISIBILITY 362 bool 363 operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 364 { 365 return !(__x < __y); 366 } 367 368 template <class _Tp, class _Container> 369 inline _LIBCPP_INLINE_VISIBILITY 370 bool 371 operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 372 { 373 return !(__y < __x); 374 } 375 376 template <class _Tp, class _Container> 377 inline _LIBCPP_INLINE_VISIBILITY 378 typename enable_if< 379 __is_swappable<_Container>::value, 380 void 381 >::type 382 swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y) 383 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 384 { 385 __x.swap(__y); 386 } 387 388 template <class _Tp, class _Container, class _Alloc> 389 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> 390 : public uses_allocator<_Container, _Alloc> 391 { 392 }; 393 394 template <class _Tp, class _Container = vector<_Tp>, 395 class _Compare = less<typename _Container::value_type> > 396 class _LIBCPP_TEMPLATE_VIS priority_queue 397 { 398 public: 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 407 protected: 408 container_type c; 409 value_compare comp; 410 411 public: 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 524 template <class _Tp, class _Container, class _Compare> 525 inline 526 priority_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 536 template <class _Tp, class _Container, class _Compare> 537 inline 538 priority_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 548 template <class _Tp, class _Container, class _Compare> 549 template <class _InputIter> 550 inline 551 priority_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 559 template <class _Tp, class _Container, class _Compare> 560 template <class _InputIter> 561 inline 562 priority_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 574 template <class _Tp, class _Container, class _Compare> 575 template <class _InputIter> 576 inline 577 priority_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 589 template <class _Tp, class _Container, class _Compare> 590 template <class _Alloc> 591 inline 592 priority_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 599 template <class _Tp, class _Container, class _Compare> 600 template <class _Alloc> 601 inline 602 priority_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 611 template <class _Tp, class _Container, class _Compare> 612 template <class _Alloc> 613 inline 614 priority_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 625 template <class _Tp, class _Container, class _Compare> 626 template <class _Alloc> 627 inline 628 priority_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 640 template <class _Tp, class _Container, class _Compare> 641 template <class _Alloc> 642 inline 643 priority_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 654 template <class _Tp, class _Container, class _Compare> 655 template <class _Alloc> 656 inline 657 priority_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 669 template <class _Tp, class _Container, class _Compare> 670 inline 671 void 672 priority_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 680 template <class _Tp, class _Container, class _Compare> 681 inline 682 void 683 priority_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 691 template <class _Tp, class _Container, class _Compare> 692 template <class... _Args> 693 inline 694 void 695 priority_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 704 template <class _Tp, class _Container, class _Compare> 705 inline 706 void 707 priority_queue<_Tp, _Container, _Compare>::pop() 708 { 709 _VSTD::pop_heap(c.begin(), c.end(), comp); 710 c.pop_back(); 711 } 712 713 template <class _Tp, class _Container, class _Compare> 714 inline 715 void 716 priority_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 725 template <class _Tp, class _Container, class _Compare> 726 inline _LIBCPP_INLINE_VISIBILITY 727 typename enable_if< 728 __is_swappable<_Container>::value 729 && __is_swappable<_Compare>::value, 730 void 731 >::type 732 swap(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 739 template <class _Tp, class _Container, class _Compare, class _Alloc> 740 struct _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
