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);
  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         reference emplace(_Args&&... __args)
 296             { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
 297 #endif  // _LIBCPP_HAS_NO_VARIADICS
 298 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 299     _LIBCPP_INLINE_VISIBILITY
 300     void pop() {c.pop_front();}
 301
 302     _LIBCPP_INLINE_VISIBILITY
 303     void swap(queue& __q)
 304         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
 305     {
 306         using _VSTD::swap;
 307         swap(c, __q.c);
 308     }
 309
 310     template <class _T1, class _C1>
 311     friend
 312     _LIBCPP_INLINE_VISIBILITY
 313     bool
 314     operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
 315
 316     template <class _T1, class _C1>
 317     friend
 318     _LIBCPP_INLINE_VISIBILITY
 319     bool
 320     operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
 321 };
 322
 323 template <class _Tp, class _Container>
 324 inline _LIBCPP_INLINE_VISIBILITY
 325 bool
 326 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 327 {
 328     return __x.c == __y.c;
 329 }
 330
 331 template <class _Tp, class _Container>
 332 inline _LIBCPP_INLINE_VISIBILITY
 333 bool
 334 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 335 {
 336     return __x.c < __y.c;
 337 }
 338
 339 template <class _Tp, class _Container>
 340 inline _LIBCPP_INLINE_VISIBILITY
 341 bool
 342 operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 343 {
 344     return !(__x == __y);
 345 }
 346
 347 template <class _Tp, class _Container>
 348 inline _LIBCPP_INLINE_VISIBILITY
 349 bool
 350 operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 351 {
 352     return __y < __x;
 353 }
 354
 355 template <class _Tp, class _Container>
 356 inline _LIBCPP_INLINE_VISIBILITY
 357 bool
 358 operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 359 {
 360     return !(__x < __y);
 361 }
 362
 363 template <class _Tp, class _Container>
 364 inline _LIBCPP_INLINE_VISIBILITY
 365 bool
 366 operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 367 {
 368     return !(__y < __x);
 369 }
 370
 371 template <class _Tp, class _Container>
 372 inline _LIBCPP_INLINE_VISIBILITY
 373 typename enable_if<
 374     __is_swappable<_Container>::value,
 375     void
 376 >::type
 377 swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
 378     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 379 {
 380     __x.swap(__y);
 381 }
 382
 383 template <class _Tp, class _Container, class _Alloc>
 384 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc>
 385     : public uses_allocator<_Container, _Alloc>
 386 {
 387 };
 388
 389 template <class _Tp, class _Container = vector<_Tp>,
 390           class _Compare = less<typename _Container::value_type> >
 391 class _LIBCPP_TEMPLATE_VIS priority_queue
 392 {
 393 public:
 394     typedef _Container                               container_type;
 395     typedef _Compare                                 value_compare;
 396     typedef typename container_type::value_type      value_type;
 397     typedef typename container_type::reference       reference;
 398     typedef typename container_type::const_reference const_reference;
 399     typedef typename container_type::size_type       size_type;
 400     static_assert((is_same<_Tp, value_type>::value), "" );
 401
 402 protected:
 403     container_type c;
 404     value_compare comp;
 405
 406 public:
 407     _LIBCPP_INLINE_VISIBILITY
 408     priority_queue()
 409         _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
 410                    is_nothrow_default_constructible<value_compare>::value)
 411         : c(), comp() {}
 412
 413     _LIBCPP_INLINE_VISIBILITY
 414     priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
 415
 416 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 417     _LIBCPP_INLINE_VISIBILITY
 418     priority_queue(priority_queue&& __q)
 419         _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
 420                    is_nothrow_move_constructible<value_compare>::value)
 421         : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
 422 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 423
 424     _LIBCPP_INLINE_VISIBILITY
 425     priority_queue& operator=(const priority_queue& __q)
 426         {c = __q.c; comp = __q.comp; return *this;}
 427
 428 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 429     _LIBCPP_INLINE_VISIBILITY
 430     priority_queue& operator=(priority_queue&& __q)
 431         _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
 432                    is_nothrow_move_assignable<value_compare>::value)
 433         {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
 434 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 435
 436     _LIBCPP_INLINE_VISIBILITY
 437     explicit priority_queue(const value_compare& __comp)
 438         : c(), comp(__comp) {}
 439     _LIBCPP_INLINE_VISIBILITY
 440     priority_queue(const value_compare& __comp, const container_type& __c);
 441 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 442     _LIBCPP_INLINE_VISIBILITY
 443     explicit priority_queue(const value_compare& __comp, container_type&& __c);
 444 #endif
 445     template <class _InputIter>
 446         _LIBCPP_INLINE_VISIBILITY
 447         priority_queue(_InputIter __f, _InputIter __l,
 448                        const value_compare& __comp = value_compare());
 449     template <class _InputIter>
 450         _LIBCPP_INLINE_VISIBILITY
 451         priority_queue(_InputIter __f, _InputIter __l,
 452                        const value_compare& __comp, const container_type& __c);
 453 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 454     template <class _InputIter>
 455         _LIBCPP_INLINE_VISIBILITY
 456         priority_queue(_InputIter __f, _InputIter __l,
 457                        const value_compare& __comp, container_type&& __c);
 458 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 459     template <class _Alloc>
 460         _LIBCPP_INLINE_VISIBILITY
 461         explicit priority_queue(const _Alloc& __a,
 462                        typename enable_if<uses_allocator<container_type,
 463                                                          _Alloc>::value>::type* = 0);
 464     template <class _Alloc>
 465         _LIBCPP_INLINE_VISIBILITY
 466         priority_queue(const value_compare& __comp, 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 container_type& __c,
 472                        const _Alloc& __a,
 473                        typename enable_if<uses_allocator<container_type,
 474                                                          _Alloc>::value>::type* = 0);
 475     template <class _Alloc>
 476         _LIBCPP_INLINE_VISIBILITY
 477         priority_queue(const priority_queue& __q, const _Alloc& __a,
 478                        typename enable_if<uses_allocator<container_type,
 479                                                          _Alloc>::value>::type* = 0);
 480 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 481     template <class _Alloc>
 482         _LIBCPP_INLINE_VISIBILITY
 483         priority_queue(const value_compare& __comp, container_type&& __c,
 484                        const _Alloc& __a,
 485                        typename enable_if<uses_allocator<container_type,
 486                                                          _Alloc>::value>::type* = 0);
 487     template <class _Alloc>
 488         _LIBCPP_INLINE_VISIBILITY
 489         priority_queue(priority_queue&& __q, const _Alloc& __a,
 490                        typename enable_if<uses_allocator<container_type,
 491                                                          _Alloc>::value>::type* = 0);
 492 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 493
 494     _LIBCPP_INLINE_VISIBILITY
 495     bool            empty() const {return c.empty();}
 496     _LIBCPP_INLINE_VISIBILITY
 497     size_type       size() const  {return c.size();}
 498     _LIBCPP_INLINE_VISIBILITY
 499     const_reference top() const   {return c.front();}
 500
 501     _LIBCPP_INLINE_VISIBILITY
 502     void push(const value_type& __v);
 503 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 504     _LIBCPP_INLINE_VISIBILITY
 505     void push(value_type&& __v);
 506 #ifndef _LIBCPP_HAS_NO_VARIADICS
 507     template <class... _Args> _LIBCPP_INLINE_VISIBILITY void emplace(_Args&&... __args);
 508 #endif
 509 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 510     _LIBCPP_INLINE_VISIBILITY
 511     void pop();
 512
 513     _LIBCPP_INLINE_VISIBILITY
 514     void swap(priority_queue& __q)
 515         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
 516                    __is_nothrow_swappable<value_compare>::value);
 517 };
 518
 519 template <class _Tp, class _Container, class _Compare>
 520 inline
 521 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
 522                                                           const container_type& __c)
 523     : c(__c),
 524       comp(__comp)
 525 {
 526     _VSTD::make_heap(c.begin(), c.end(), comp);
 527 }
 528
 529 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 530
 531 template <class _Tp, class _Container, class _Compare>
 532 inline
 533 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 534                                                           container_type&& __c)
 535     : c(_VSTD::move(__c)),
 536       comp(__comp)
 537 {
 538     _VSTD::make_heap(c.begin(), c.end(), comp);
 539 }
 540
 541 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 542
 543 template <class _Tp, class _Container, class _Compare>
 544 template <class _InputIter>
 545 inline
 546 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
 547                                                           const value_compare& __comp)
 548     : c(__f, __l),
 549       comp(__comp)
 550 {
 551     _VSTD::make_heap(c.begin(), c.end(), comp);
 552 }
 553
 554 template <class _Tp, class _Container, class _Compare>
 555 template <class _InputIter>
 556 inline
 557 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
 558                                                           const value_compare& __comp,
 559                                                           const container_type& __c)
 560     : c(__c),
 561       comp(__comp)
 562 {
 563     c.insert(c.end(), __f, __l);
 564     _VSTD::make_heap(c.begin(), c.end(), comp);
 565 }
 566
 567 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 568
 569 template <class _Tp, class _Container, class _Compare>
 570 template <class _InputIter>
 571 inline
 572 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
 573                                                           const value_compare& __comp,
 574                                                           container_type&& __c)
 575     : c(_VSTD::move(__c)),
 576       comp(__comp)
 577 {
 578     c.insert(c.end(), __f, __l);
 579     _VSTD::make_heap(c.begin(), c.end(), comp);
 580 }
 581
 582 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 583
 584 template <class _Tp, class _Container, class _Compare>
 585 template <class _Alloc>
 586 inline
 587 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
 588                        typename enable_if<uses_allocator<container_type,
 589                                                          _Alloc>::value>::type*)
 590     : c(__a)
 591 {
 592 }
 593
 594 template <class _Tp, class _Container, class _Compare>
 595 template <class _Alloc>
 596 inline
 597 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 598                                                           const _Alloc& __a,
 599                        typename enable_if<uses_allocator<container_type,
 600                                                          _Alloc>::value>::type*)
 601     : c(__a),
 602       comp(__comp)
 603 {
 604 }
 605
 606 template <class _Tp, class _Container, class _Compare>
 607 template <class _Alloc>
 608 inline
 609 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 610                                                           const container_type& __c,
 611                                                           const _Alloc& __a,
 612                        typename enable_if<uses_allocator<container_type,
 613                                                          _Alloc>::value>::type*)
 614     : c(__c, __a),
 615       comp(__comp)
 616 {
 617     _VSTD::make_heap(c.begin(), c.end(), comp);
 618 }
 619
 620 template <class _Tp, class _Container, class _Compare>
 621 template <class _Alloc>
 622 inline
 623 priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
 624                                                           const _Alloc& __a,
 625                        typename enable_if<uses_allocator<container_type,
 626                                                          _Alloc>::value>::type*)
 627     : c(__q.c, __a),
 628       comp(__q.comp)
 629 {
 630     _VSTD::make_heap(c.begin(), c.end(), comp);
 631 }
 632
 633 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 634
 635 template <class _Tp, class _Container, class _Compare>
 636 template <class _Alloc>
 637 inline
 638 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 639                                                           container_type&& __c,
 640                                                           const _Alloc& __a,
 641                        typename enable_if<uses_allocator<container_type,
 642                                                          _Alloc>::value>::type*)
 643     : c(_VSTD::move(__c), __a),
 644       comp(__comp)
 645 {
 646     _VSTD::make_heap(c.begin(), c.end(), comp);
 647 }
 648
 649 template <class _Tp, class _Container, class _Compare>
 650 template <class _Alloc>
 651 inline
 652 priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
 653                                                           const _Alloc& __a,
 654                        typename enable_if<uses_allocator<container_type,
 655                                                          _Alloc>::value>::type*)
 656     : c(_VSTD::move(__q.c), __a),
 657       comp(_VSTD::move(__q.comp))
 658 {
 659     _VSTD::make_heap(c.begin(), c.end(), comp);
 660 }
 661
 662 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 663
 664 template <class _Tp, class _Container, class _Compare>
 665 inline
 666 void
 667 priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
 668 {
 669     c.push_back(__v);
 670     _VSTD::push_heap(c.begin(), c.end(), comp);
 671 }
 672
 673 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 674
 675 template <class _Tp, class _Container, class _Compare>
 676 inline
 677 void
 678 priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
 679 {
 680     c.push_back(_VSTD::move(__v));
 681     _VSTD::push_heap(c.begin(), c.end(), comp);
 682 }
 683
 684 #ifndef _LIBCPP_HAS_NO_VARIADICS
 685
 686 template <class _Tp, class _Container, class _Compare>
 687 template <class... _Args>
 688 inline
 689 void
 690 priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
 691 {
 692     c.emplace_back(_VSTD::forward<_Args>(__args)...);
 693     _VSTD::push_heap(c.begin(), c.end(), comp);
 694 }
 695
 696 #endif  // _LIBCPP_HAS_NO_VARIADICS
 697 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 698
 699 template <class _Tp, class _Container, class _Compare>
 700 inline
 701 void
 702 priority_queue<_Tp, _Container, _Compare>::pop()
 703 {
 704     _VSTD::pop_heap(c.begin(), c.end(), comp);
 705     c.pop_back();
 706 }
 707
 708 template <class _Tp, class _Container, class _Compare>
 709 inline
 710 void
 711 priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
 712         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
 713                    __is_nothrow_swappable<value_compare>::value)
 714 {
 715     using _VSTD::swap;
 716     swap(c, __q.c);
 717     swap(comp, __q.comp);
 718 }
 719
 720 template <class _Tp, class _Container, class _Compare>
 721 inline _LIBCPP_INLINE_VISIBILITY
 722 typename enable_if<
 723     __is_swappable<_Container>::value
 724     && __is_swappable<_Compare>::value,
 725     void
 726 >::type
 727 swap(priority_queue<_Tp, _Container, _Compare>& __x,
 728      priority_queue<_Tp, _Container, _Compare>& __y)
 729     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 730 {
 731     __x.swap(__y);
 732 }
 733
 734 template <class _Tp, class _Container, class _Compare, class _Alloc>
 735 struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
 736     : public uses_allocator<_Container, _Alloc>
 737 {
 738 };
 739
 740 _LIBCPP_END_NAMESPACE_STD
 741
 742 #endif  // _LIBCPP_QUEUE