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