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