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