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