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