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