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> void emplace(Args&&... args); 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_TYPE_VIS_ONLY 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_TYPE_VIS_ONLY 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 void emplace(_Args&&... __args) 296 {c.emplace_back(_VSTD::forward<_Args>(__args)...);} 297 #endif // _LIBCPP_HAS_NO_VARIADICS 298 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 299 _LIBCPP_INLINE_VISIBILITY 300 void pop() {c.pop_front();} 301 302 _LIBCPP_INLINE_VISIBILITY 303 void swap(queue& __q) 304 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) 305 { 306 using _VSTD::swap; 307 swap(c, __q.c); 308 } 309 310 template <class _T1, class _C1> 311 friend 312 _LIBCPP_INLINE_VISIBILITY 313 bool 314 operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y); 315 316 template <class _T1, class _C1> 317 friend 318 _LIBCPP_INLINE_VISIBILITY 319 bool 320 operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y); 321 }; 322 323 template <class _Tp, class _Container> 324 inline _LIBCPP_INLINE_VISIBILITY 325 bool 326 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 327 { 328 return __x.c == __y.c; 329 } 330 331 template <class _Tp, class _Container> 332 inline _LIBCPP_INLINE_VISIBILITY 333 bool 334 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 335 { 336 return __x.c < __y.c; 337 } 338 339 template <class _Tp, class _Container> 340 inline _LIBCPP_INLINE_VISIBILITY 341 bool 342 operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 343 { 344 return !(__x == __y); 345 } 346 347 template <class _Tp, class _Container> 348 inline _LIBCPP_INLINE_VISIBILITY 349 bool 350 operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 351 { 352 return __y < __x; 353 } 354 355 template <class _Tp, class _Container> 356 inline _LIBCPP_INLINE_VISIBILITY 357 bool 358 operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 359 { 360 return !(__x < __y); 361 } 362 363 template <class _Tp, class _Container> 364 inline _LIBCPP_INLINE_VISIBILITY 365 bool 366 operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 367 { 368 return !(__y < __x); 369 } 370 371 template <class _Tp, class _Container> 372 inline _LIBCPP_INLINE_VISIBILITY 373 typename enable_if< 374 __is_swappable<_Container>::value, 375 void 376 >::type 377 swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y) 378 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 379 { 380 __x.swap(__y); 381 } 382 383 template <class _Tp, class _Container, class _Alloc> 384 struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<queue<_Tp, _Container>, _Alloc> 385 : public uses_allocator<_Container, _Alloc> 386 { 387 }; 388 389 template <class _Tp, class _Container = vector<_Tp>, 390 class _Compare = less<typename _Container::value_type> > 391 class _LIBCPP_TYPE_VIS_ONLY priority_queue 392 { 393 public: 394 typedef _Container container_type; 395 typedef _Compare value_compare; 396 typedef typename container_type::value_type value_type; 397 typedef typename container_type::reference reference; 398 typedef typename container_type::const_reference const_reference; 399 typedef typename container_type::size_type size_type; 400 static_assert((is_same<_Tp, value_type>::value), "" ); 401 402 protected: 403 container_type c; 404 value_compare comp; 405 406 public: 407 _LIBCPP_INLINE_VISIBILITY 408 priority_queue() 409 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value && 410 is_nothrow_default_constructible<value_compare>::value) 411 : c(), comp() {} 412 413 _LIBCPP_INLINE_VISIBILITY 414 priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {} 415 416 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 417 _LIBCPP_INLINE_VISIBILITY 418 priority_queue(priority_queue&& __q) 419 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value && 420 is_nothrow_move_constructible<value_compare>::value) 421 : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {} 422 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 423 424 _LIBCPP_INLINE_VISIBILITY 425 priority_queue& operator=(const priority_queue& __q) 426 {c = __q.c; comp = __q.comp; return *this;} 427 428 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 429 _LIBCPP_INLINE_VISIBILITY 430 priority_queue& operator=(priority_queue&& __q) 431 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value && 432 is_nothrow_move_assignable<value_compare>::value) 433 {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;} 434 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 435 436 _LIBCPP_INLINE_VISIBILITY 437 explicit priority_queue(const value_compare& __comp) 438 : c(), comp(__comp) {} 439 _LIBCPP_INLINE_VISIBILITY 440 priority_queue(const value_compare& __comp, const container_type& __c); 441 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 442 _LIBCPP_INLINE_VISIBILITY 443 explicit priority_queue(const value_compare& __comp, container_type&& __c); 444 #endif 445 template <class _InputIter> 446 _LIBCPP_INLINE_VISIBILITY 447 priority_queue(_InputIter __f, _InputIter __l, 448 const value_compare& __comp = value_compare()); 449 template <class _InputIter> 450 _LIBCPP_INLINE_VISIBILITY 451 priority_queue(_InputIter __f, _InputIter __l, 452 const value_compare& __comp, const container_type& __c); 453 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 454 template <class _InputIter> 455 _LIBCPP_INLINE_VISIBILITY 456 priority_queue(_InputIter __f, _InputIter __l, 457 const value_compare& __comp, container_type&& __c); 458 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 459 template <class _Alloc> 460 _LIBCPP_INLINE_VISIBILITY 461 explicit priority_queue(const _Alloc& __a, 462 typename enable_if<uses_allocator<container_type, 463 _Alloc>::value>::type* = 0); 464 template <class _Alloc> 465 _LIBCPP_INLINE_VISIBILITY 466 priority_queue(const value_compare& __comp, 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 container_type& __c, 472 const _Alloc& __a, 473 typename enable_if<uses_allocator<container_type, 474 _Alloc>::value>::type* = 0); 475 template <class _Alloc> 476 _LIBCPP_INLINE_VISIBILITY 477 priority_queue(const priority_queue& __q, const _Alloc& __a, 478 typename enable_if<uses_allocator<container_type, 479 _Alloc>::value>::type* = 0); 480 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 481 template <class _Alloc> 482 _LIBCPP_INLINE_VISIBILITY 483 priority_queue(const value_compare& __comp, container_type&& __c, 484 const _Alloc& __a, 485 typename enable_if<uses_allocator<container_type, 486 _Alloc>::value>::type* = 0); 487 template <class _Alloc> 488 _LIBCPP_INLINE_VISIBILITY 489 priority_queue(priority_queue&& __q, const _Alloc& __a, 490 typename enable_if<uses_allocator<container_type, 491 _Alloc>::value>::type* = 0); 492 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 493 494 _LIBCPP_INLINE_VISIBILITY 495 bool empty() const {return c.empty();} 496 _LIBCPP_INLINE_VISIBILITY 497 size_type size() const {return c.size();} 498 _LIBCPP_INLINE_VISIBILITY 499 const_reference top() const {return c.front();} 500 501 _LIBCPP_INLINE_VISIBILITY 502 void push(const value_type& __v); 503 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 504 _LIBCPP_INLINE_VISIBILITY 505 void push(value_type&& __v); 506 #ifndef _LIBCPP_HAS_NO_VARIADICS 507 template <class... _Args> _LIBCPP_INLINE_VISIBILITY void emplace(_Args&&... __args); 508 #endif 509 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 510 _LIBCPP_INLINE_VISIBILITY 511 void pop(); 512 513 _LIBCPP_INLINE_VISIBILITY 514 void swap(priority_queue& __q) 515 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 516 __is_nothrow_swappable<value_compare>::value); 517 }; 518 519 template <class _Tp, class _Container, class _Compare> 520 inline 521 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, 522 const container_type& __c) 523 : c(__c), 524 comp(__comp) 525 { 526 _VSTD::make_heap(c.begin(), c.end(), comp); 527 } 528 529 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 530 531 template <class _Tp, class _Container, class _Compare> 532 inline 533 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 534 container_type&& __c) 535 : c(_VSTD::move(__c)), 536 comp(__comp) 537 { 538 _VSTD::make_heap(c.begin(), c.end(), comp); 539 } 540 541 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 542 543 template <class _Tp, class _Container, class _Compare> 544 template <class _InputIter> 545 inline 546 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 547 const value_compare& __comp) 548 : c(__f, __l), 549 comp(__comp) 550 { 551 _VSTD::make_heap(c.begin(), c.end(), comp); 552 } 553 554 template <class _Tp, class _Container, class _Compare> 555 template <class _InputIter> 556 inline 557 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 558 const value_compare& __comp, 559 const container_type& __c) 560 : c(__c), 561 comp(__comp) 562 { 563 c.insert(c.end(), __f, __l); 564 _VSTD::make_heap(c.begin(), c.end(), comp); 565 } 566 567 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 568 569 template <class _Tp, class _Container, class _Compare> 570 template <class _InputIter> 571 inline 572 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, 573 const value_compare& __comp, 574 container_type&& __c) 575 : c(_VSTD::move(__c)), 576 comp(__comp) 577 { 578 c.insert(c.end(), __f, __l); 579 _VSTD::make_heap(c.begin(), c.end(), comp); 580 } 581 582 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 583 584 template <class _Tp, class _Container, class _Compare> 585 template <class _Alloc> 586 inline 587 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a, 588 typename enable_if<uses_allocator<container_type, 589 _Alloc>::value>::type*) 590 : c(__a) 591 { 592 } 593 594 template <class _Tp, class _Container, class _Compare> 595 template <class _Alloc> 596 inline 597 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 598 const _Alloc& __a, 599 typename enable_if<uses_allocator<container_type, 600 _Alloc>::value>::type*) 601 : c(__a), 602 comp(__comp) 603 { 604 } 605 606 template <class _Tp, class _Container, class _Compare> 607 template <class _Alloc> 608 inline 609 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 610 const container_type& __c, 611 const _Alloc& __a, 612 typename enable_if<uses_allocator<container_type, 613 _Alloc>::value>::type*) 614 : c(__c, __a), 615 comp(__comp) 616 { 617 _VSTD::make_heap(c.begin(), c.end(), comp); 618 } 619 620 template <class _Tp, class _Container, class _Compare> 621 template <class _Alloc> 622 inline 623 priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, 624 const _Alloc& __a, 625 typename enable_if<uses_allocator<container_type, 626 _Alloc>::value>::type*) 627 : c(__q.c, __a), 628 comp(__q.comp) 629 { 630 _VSTD::make_heap(c.begin(), c.end(), comp); 631 } 632 633 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 634 635 template <class _Tp, class _Container, class _Compare> 636 template <class _Alloc> 637 inline 638 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, 639 container_type&& __c, 640 const _Alloc& __a, 641 typename enable_if<uses_allocator<container_type, 642 _Alloc>::value>::type*) 643 : c(_VSTD::move(__c), __a), 644 comp(__comp) 645 { 646 _VSTD::make_heap(c.begin(), c.end(), comp); 647 } 648 649 template <class _Tp, class _Container, class _Compare> 650 template <class _Alloc> 651 inline 652 priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, 653 const _Alloc& __a, 654 typename enable_if<uses_allocator<container_type, 655 _Alloc>::value>::type*) 656 : c(_VSTD::move(__q.c), __a), 657 comp(_VSTD::move(__q.comp)) 658 { 659 _VSTD::make_heap(c.begin(), c.end(), comp); 660 } 661 662 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 663 664 template <class _Tp, class _Container, class _Compare> 665 inline 666 void 667 priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) 668 { 669 c.push_back(__v); 670 _VSTD::push_heap(c.begin(), c.end(), comp); 671 } 672 673 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 674 675 template <class _Tp, class _Container, class _Compare> 676 inline 677 void 678 priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) 679 { 680 c.push_back(_VSTD::move(__v)); 681 _VSTD::push_heap(c.begin(), c.end(), comp); 682 } 683 684 #ifndef _LIBCPP_HAS_NO_VARIADICS 685 686 template <class _Tp, class _Container, class _Compare> 687 template <class... _Args> 688 inline 689 void 690 priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) 691 { 692 c.emplace_back(_VSTD::forward<_Args>(__args)...); 693 _VSTD::push_heap(c.begin(), c.end(), comp); 694 } 695 696 #endif // _LIBCPP_HAS_NO_VARIADICS 697 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 698 699 template <class _Tp, class _Container, class _Compare> 700 inline 701 void 702 priority_queue<_Tp, _Container, _Compare>::pop() 703 { 704 _VSTD::pop_heap(c.begin(), c.end(), comp); 705 c.pop_back(); 706 } 707 708 template <class _Tp, class _Container, class _Compare> 709 inline 710 void 711 priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q) 712 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value && 713 __is_nothrow_swappable<value_compare>::value) 714 { 715 using _VSTD::swap; 716 swap(c, __q.c); 717 swap(comp, __q.comp); 718 } 719 720 template <class _Tp, class _Container, class _Compare> 721 inline _LIBCPP_INLINE_VISIBILITY 722 typename enable_if< 723 __is_swappable<_Container>::value 724 && __is_swappable<_Compare>::value, 725 void 726 >::type 727 swap(priority_queue<_Tp, _Container, _Compare>& __x, 728 priority_queue<_Tp, _Container, _Compare>& __y) 729 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 730 { 731 __x.swap(__y); 732 } 733 734 template <class _Tp, class _Container, class _Compare, class _Alloc> 735 struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc> 736 : public uses_allocator<_Container, _Alloc> 737 { 738 }; 739 740 _LIBCPP_END_NAMESPACE_STD 741 742 #endif // _LIBCPP_QUEUE 743
