contrib/libc++/include/queue

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