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