contrib/libc++/include/queue

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