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