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