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 Container> 73 queue(Container) -> queue<typename Container::value_type, Container>; // C++17 74 75 template<class Container, class Allocator> 76 queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17 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 bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y); 92 93 template <class T, class Container> 94 bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y); 95 96 template <class T, class Container> 97 void swap(queue<T, Container>& x, queue<T, Container>& y) 98 noexcept(noexcept(x.swap(y))); 99 100 template <class T, class Container = vector<T>, 101 class Compare = less<typename Container::value_type>> 102 class priority_queue 103 { 104 public: 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 111 protected: 112 container_type c; 113 Compare comp; 114 115 public: 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 166 template <class Compare, class Container> 167 priority_queue(Compare, Container) 168 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17 169 170 template<class InputIterator, 171 class Compare = less<typename iterator_traits<InputIterator>::value_type>, 172 class Container = vector<typename iterator_traits<InputIterator>::value_type>> 173 priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container()) 174 -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>; // C++17 175 176 template<class Compare, class Container, class Allocator> 177 priority_queue(Compare, Container, Allocator) 178 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17 179 180 template <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 201 template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue; 202 203 template <class _Tp, class _Container> 204 _LIBCPP_INLINE_VISIBILITY 205 bool 206 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 207 208 template <class _Tp, class _Container> 209 _LIBCPP_INLINE_VISIBILITY 210 bool 211 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y); 212 213 template <class _Tp, class _Container /*= deque<_Tp>*/> 214 class _LIBCPP_TEMPLATE_VIS queue 215 { 216 public: 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 224 protected: 225 container_type c; 226 227 public: 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 345 template<class _Container, 346 class = typename enable_if<!__is_allocator<_Container>::value, nullptr_t>::type 347 > 348 queue(_Container) 349 -> queue<typename _Container::value_type, _Container>; 350 351 template<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 > 356 queue(_Container, _Alloc) 357 -> queue<typename _Container::value_type, _Container>; 358 #endif 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.c == __y.c; 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 __x.c < __y.c; 374 } 375 376 template <class _Tp, class _Container> 377 inline _LIBCPP_INLINE_VISIBILITY 378 bool 379 operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 380 { 381 return !(__x == __y); 382 } 383 384 template <class _Tp, class _Container> 385 inline _LIBCPP_INLINE_VISIBILITY 386 bool 387 operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 388 { 389 return __y < __x; 390 } 391 392 template <class _Tp, class _Container> 393 inline _LIBCPP_INLINE_VISIBILITY 394 bool 395 operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 396 { 397 return !(__x < __y); 398 } 399 400 template <class _Tp, class _Container> 401 inline _LIBCPP_INLINE_VISIBILITY 402 bool 403 operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y) 404 { 405 return !(__y < __x); 406 } 407 408 template <class _Tp, class _Container> 409 inline _LIBCPP_INLINE_VISIBILITY 410 typename enable_if< 411 __is_swappable<_Container>::value, 412 void 413 >::type 414 swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y) 415 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 416 { 417 __x.swap(__y); 418 } 419 420 template <class _Tp, class _Container, class _Alloc> 421 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> 422 : public uses_allocator<_Container, _Alloc> 423 { 424 }; 425 426 template <class _Tp, class _Container = vector<_Tp>, 427 class _Compare = less<typename _Container::value_type> > 428 class _LIBCPP_TEMPLATE_VIS priority_queue 429 { 430 public: 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 439 protected: 440 container_type c; 441 value_compare comp; 442 443 public: 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 555 template <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 > 560 priority_queue(_Compare, _Container) 561 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 562 563 template<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 > 570 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container()) 571 -> priority_queue<typename iterator_traits<_InputIterator>::value_type, _Container, _Compare>; 572 573 template<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 > 580 priority_queue(_Compare, _Container, _Alloc) 581 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 582 #endif 583 584 template <class _Tp, class _Container, class _Compare> 585 inline 586 priority_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 596 template <class _Tp, class _Container, class _Compare> 597 inline 598 priority_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 608 template <class _Tp, class _Container, class _Compare> 609 template <class _InputIter> 610 inline 611 priority_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 619 template <class _Tp, class _Container, class _Compare> 620 template <class _InputIter> 621 inline 622 priority_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 634 template <class _Tp, class _Container, class _Compare> 635 template <class _InputIter> 636 inline 637 priority_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 649 template <class _Tp, class _Container, class _Compare> 650 template <class _Alloc> 651 inline 652 priority_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 659 template <class _Tp, class _Container, class _Compare> 660 template <class _Alloc> 661 inline 662 priority_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 671 template <class _Tp, class _Container, class _Compare> 672 template <class _Alloc> 673 inline 674 priority_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 685 template <class _Tp, class _Container, class _Compare> 686 template <class _Alloc> 687 inline 688 priority_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 700 template <class _Tp, class _Container, class _Compare> 701 template <class _Alloc> 702 inline 703 priority_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 714 template <class _Tp, class _Container, class _Compare> 715 template <class _Alloc> 716 inline 717 priority_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 729 template <class _Tp, class _Container, class _Compare> 730 inline 731 void 732 priority_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 740 template <class _Tp, class _Container, class _Compare> 741 inline 742 void 743 priority_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 749 template <class _Tp, class _Container, class _Compare> 750 template <class... _Args> 751 inline 752 void 753 priority_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 761 template <class _Tp, class _Container, class _Compare> 762 inline 763 void 764 priority_queue<_Tp, _Container, _Compare>::pop() 765 { 766 _VSTD::pop_heap(c.begin(), c.end(), comp); 767 c.pop_back(); 768 } 769 770 template <class _Tp, class _Container, class _Compare> 771 inline 772 void 773 priority_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 782 template <class _Tp, class _Container, class _Compare> 783 inline _LIBCPP_INLINE_VISIBILITY 784 typename enable_if< 785 __is_swappable<_Container>::value 786 && __is_swappable<_Compare>::value, 787 void 788 >::type 789 swap(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 796 template <class _Tp, class _Container, class _Compare, class _Alloc> 797 struct _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
