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