libcxx/include/queue

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   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 InputIterator>
  45         queue(InputIterator first, InputIterator last); // since C++23
  46     template <class Alloc>
  47         explicit queue(const Alloc& a);
  48     template <class Alloc>
  49         queue(const container_type& c, const Alloc& a);
  50     template <class Alloc>
  51         queue(container_type&& c, const Alloc& a);
  52     template <class Alloc>
  53         queue(const queue& q, const Alloc& a);
  54     template <class Alloc>
  55         queue(queue&& q, const Alloc& a);
  56     template <class InputIterator, class Alloc>
  57         queue(InputIterator first, InputIterator last, const Alloc&); // since C++23
  58
  59     bool      empty() const;
  60     size_type size() const;
  61
  62     reference       front();
  63     const_reference front() const;
  64     reference       back();
  65     const_reference back() const;
  66
  67     void push(const value_type& v);
  68     void push(value_type&& v);
  69     template <class... Args> reference emplace(Args&&... args); // reference in C++17
  70     void pop();
  71
  72     void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
  73 };
  74
  75 template<class Container>
  76   queue(Container) -> queue<typename Container::value_type, Container>; // C++17
  77
  78 template<class InputIterator>
  79   queue(InputIterator, InputIterator) -> queue<iter-value-type<InputIterator>>; // since C++23
  80
  81 template<class Container, class Allocator>
  82   queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17
  83
  84 template<class InputIterator, class Allocator>
  85   queue(InputIterator, InputIterator, Allocator)
  86   -> queue<iter-value-type<InputIterator>,
  87            deque<iter-value-type<InputIterator>, Allocator>>; // since C++23
  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   bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
  97
  98 template <class T, class Container>
  99   bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
 100
 101 template <class T, class Container>
 102   bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
 103
 104 template <class T, class Container>
 105   bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
 106
 107 template <class T, class Container>
 108   void swap(queue<T, Container>& x, queue<T, Container>& y)
 109   noexcept(noexcept(x.swap(y)));
 110
 111 template <class T, class Container = vector<T>,
 112           class Compare = less<typename Container::value_type>>
 113 class priority_queue
 114 {
 115 public:
 116     typedef Container                                container_type;
 117     typedef typename container_type::value_type      value_type;
 118     typedef typename container_type::reference       reference;
 119     typedef typename container_type::const_reference const_reference;
 120     typedef typename container_type::size_type       size_type;
 121
 122 protected:
 123     container_type c;
 124     Compare comp;
 125
 126 public:
 127     priority_queue() : priority_queue(Compare()) {} // C++20
 128     explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
 129     priority_queue(const Compare& x, const Container&);
 130     explicit priority_queue(const Compare& x = Compare(), Container&& = Container()); // before C++20
 131     priority_queue(const Compare& x, Container&&); // C++20
 132     template <class InputIterator>
 133         priority_queue(InputIterator first, InputIterator last,
 134                        const Compare& comp = Compare());
 135     template <class InputIterator>
 136         priority_queue(InputIterator first, InputIterator last,
 137                        const Compare& comp, const Container& c);
 138     template <class InputIterator>
 139         priority_queue(InputIterator first, InputIterator last,
 140                        const Compare& comp, Container&& c);
 141     template <class Alloc>
 142         explicit priority_queue(const Alloc& a);
 143     template <class Alloc>
 144         priority_queue(const Compare& comp, const Alloc& a);
 145     template <class Alloc>
 146         priority_queue(const Compare& comp, const Container& c,
 147                        const Alloc& a);
 148     template <class Alloc>
 149         priority_queue(const Compare& comp, Container&& c,
 150                        const Alloc& a);
 151     template <class InputIterator>
 152         priority_queue(InputIterator first, InputIterator last,
 153                        const Alloc& a);
 154     template <class InputIterator>
 155         priority_queue(InputIterator first, InputIterator last,
 156                        const Compare& comp, const Alloc& a);
 157     template <class InputIterator>
 158         priority_queue(InputIterator first, InputIterator last,
 159                        const Compare& comp, const Container& c, const Alloc& a);
 160     template <class InputIterator>
 161         priority_queue(InputIterator first, InputIterator last,
 162                        const Compare& comp, Container&& c, const Alloc& a);
 163     template <class Alloc>
 164         priority_queue(const priority_queue& q, const Alloc& a);
 165     template <class Alloc>
 166         priority_queue(priority_queue&& q, const Alloc& a);
 167
 168     bool            empty() const;
 169     size_type       size() const;
 170     const_reference top() const;
 171
 172     void push(const value_type& v);
 173     void push(value_type&& v);
 174     template <class... Args> void emplace(Args&&... args);
 175     void pop();
 176
 177     void swap(priority_queue& q)
 178         noexcept(is_nothrow_swappable_v<Container> &&
 179                  is_nothrow_swappable_v<Comp>)
 180 };
 181
 182 template <class Compare, class Container>
 183 priority_queue(Compare, Container)
 184     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 185
 186 template<class InputIterator,
 187          class Compare = less<iter-value-type<InputIterator>>,
 188          class Container = vector<iter-value-type<InputIterator>>>
 189 priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
 190     -> priority_queue<iter-value-type<InputIterator>, Container, Compare>; // C++17
 191
 192 template<class Compare, class Container, class Allocator>
 193 priority_queue(Compare, Container, Allocator)
 194     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 195
 196 template<class InputIterator, class Allocator>
 197 priority_queue(InputIterator, InputIterator, Allocator)
 198     -> priority_queue<iter-value-type<InputIterator>,
 199                       vector<iter-value-type<InputIterator>, Allocator>,
 200                       less<iter-value-type<InputIterator>>>; // C++17
 201
 202 template<class InputIterator, class Compare, class Allocator>
 203 priority_queue(InputIterator, InputIterator, Compare, Allocator)
 204     -> priority_queue<iter-value-type<InputIterator>,
 205                       vector<iter-value-type<InputIterator>, Allocator>, Compare>; // C++17
 206
 207 template<class InputIterator, class Compare, class Container, class Allocator>
 208 priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
 209     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 210
 211 template <class T, class Container, class Compare>
 212   void swap(priority_queue<T, Container, Compare>& x,
 213             priority_queue<T, Container, Compare>& y)
 214             noexcept(noexcept(x.swap(y)));
 215
 216 }  // std
 217
 218 */
 219
 220 #include <__config>
 221 #include <__iterator/iterator_traits.h>
 222 #include <__memory/uses_allocator.h>
 223 #include <__utility/forward.h>
 224 #include <algorithm>
 225 #include <compare>
 226 #include <deque>
 227 #include <functional>
 228 #include <type_traits>
 229 #include <vector>
 230 #include <version>
 231
 232 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 233 #pragma GCC system_header
 234 #endif
 235
 236 _LIBCPP_BEGIN_NAMESPACE_STD
 237
 238 template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue;
 239
 240 template <class _Tp, class _Container>
 241 _LIBCPP_INLINE_VISIBILITY
 242 bool
 243 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
 244
 245 template <class _Tp, class _Container>
 246 _LIBCPP_INLINE_VISIBILITY
 247 bool
 248 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
 249
 250 template <class _Tp, class _Container /*= deque<_Tp>*/>
 251 class _LIBCPP_TEMPLATE_VIS queue
 252 {
 253 public:
 254     typedef _Container                               container_type;
 255     typedef typename container_type::value_type      value_type;
 256     typedef typename container_type::reference       reference;
 257     typedef typename container_type::const_reference const_reference;
 258     typedef typename container_type::size_type       size_type;
 259     static_assert((is_same<_Tp, value_type>::value), "" );
 260
 261 protected:
 262     container_type c;
 263
 264 public:
 265     _LIBCPP_INLINE_VISIBILITY
 266     queue()
 267         _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
 268         : c() {}
 269
 270     _LIBCPP_INLINE_VISIBILITY
 271     queue(const queue& __q) : c(__q.c) {}
 272
 273 #if _LIBCPP_STD_VER > 20
 274     template <class _InputIterator,
 275               class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>>
 276     _LIBCPP_HIDE_FROM_ABI
 277     queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
 278
 279     template <class _InputIterator,
 280               class _Alloc,
 281               class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
 282               class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>>
 283     _LIBCPP_HIDE_FROM_ABI
 284     queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc) : c(__first, __second, __alloc) {}
 285 #endif
 286
 287     _LIBCPP_INLINE_VISIBILITY
 288     queue& operator=(const queue& __q) {c = __q.c; return *this;}
 289
 290 #ifndef _LIBCPP_CXX03_LANG
 291     _LIBCPP_INLINE_VISIBILITY
 292     queue(queue&& __q)
 293         _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
 294         : c(_VSTD::move(__q.c)) {}
 295
 296     _LIBCPP_INLINE_VISIBILITY
 297     queue& operator=(queue&& __q)
 298         _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
 299         {c = _VSTD::move(__q.c); return *this;}
 300 #endif // _LIBCPP_CXX03_LANG
 301
 302     _LIBCPP_INLINE_VISIBILITY
 303     explicit queue(const container_type& __c)  : c(__c) {}
 304 #ifndef _LIBCPP_CXX03_LANG
 305     _LIBCPP_INLINE_VISIBILITY
 306     explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
 307 #endif // _LIBCPP_CXX03_LANG
 308     template <class _Alloc>
 309         _LIBCPP_INLINE_VISIBILITY
 310         explicit queue(const _Alloc& __a,
 311                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
 312             : c(__a) {}
 313     template <class _Alloc>
 314         _LIBCPP_INLINE_VISIBILITY
 315         queue(const queue& __q, const _Alloc& __a,
 316                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
 317             : c(__q.c, __a) {}
 318     template <class _Alloc>
 319         _LIBCPP_INLINE_VISIBILITY
 320         queue(const container_type& __c, const _Alloc& __a,
 321                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
 322             : c(__c, __a) {}
 323 #ifndef _LIBCPP_CXX03_LANG
 324     template <class _Alloc>
 325         _LIBCPP_INLINE_VISIBILITY
 326         queue(container_type&& __c, const _Alloc& __a,
 327                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
 328             : c(_VSTD::move(__c), __a) {}
 329     template <class _Alloc>
 330         _LIBCPP_INLINE_VISIBILITY
 331         queue(queue&& __q, const _Alloc& __a,
 332                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
 333             : c(_VSTD::move(__q.c), __a) {}
 334
 335 #endif // _LIBCPP_CXX03_LANG
 336
 337     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 338     bool      empty() const {return c.empty();}
 339     _LIBCPP_INLINE_VISIBILITY
 340     size_type size() const  {return c.size();}
 341
 342     _LIBCPP_INLINE_VISIBILITY
 343     reference       front()       {return c.front();}
 344     _LIBCPP_INLINE_VISIBILITY
 345     const_reference front() const {return c.front();}
 346     _LIBCPP_INLINE_VISIBILITY
 347     reference       back()        {return c.back();}
 348     _LIBCPP_INLINE_VISIBILITY
 349     const_reference back() const  {return c.back();}
 350
 351     _LIBCPP_INLINE_VISIBILITY
 352     void push(const value_type& __v) {c.push_back(__v);}
 353 #ifndef _LIBCPP_CXX03_LANG
 354     _LIBCPP_INLINE_VISIBILITY
 355     void push(value_type&& __v)      {c.push_back(_VSTD::move(__v));}
 356     template <class... _Args>
 357         _LIBCPP_INLINE_VISIBILITY
 358 #if _LIBCPP_STD_VER > 14
 359         decltype(auto) emplace(_Args&&... __args)
 360             { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
 361 #else
 362         void     emplace(_Args&&... __args)
 363             {        c.emplace_back(_VSTD::forward<_Args>(__args)...);}
 364 #endif
 365 #endif // _LIBCPP_CXX03_LANG
 366     _LIBCPP_INLINE_VISIBILITY
 367     void pop() {c.pop_front();}
 368
 369     _LIBCPP_INLINE_VISIBILITY
 370     void swap(queue& __q)
 371         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
 372     {
 373         using _VSTD::swap;
 374         swap(c, __q.c);
 375     }
 376
 377     template <class _T1, class _C1>
 378     friend
 379     _LIBCPP_INLINE_VISIBILITY
 380     bool
 381     operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
 382
 383     template <class _T1, class _C1>
 384     friend
 385     _LIBCPP_INLINE_VISIBILITY
 386     bool
 387     operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
 388 };
 389
 390 #if _LIBCPP_STD_VER > 14
 391 template<class _Container,
 392          class = enable_if_t<!__is_allocator<_Container>::value>
 393 >
 394 queue(_Container)
 395     -> queue<typename _Container::value_type, _Container>;
 396
 397 template<class _Container,
 398          class _Alloc,
 399          class = enable_if_t<!__is_allocator<_Container>::value>,
 400          class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
 401 >
 402 queue(_Container, _Alloc)
 403     -> queue<typename _Container::value_type, _Container>;
 404 #endif
 405
 406 #if _LIBCPP_STD_VER > 20
 407 template <class _InputIterator,
 408           class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>>
 409 queue(_InputIterator, _InputIterator)
 410     -> queue<__iter_value_type<_InputIterator>>;
 411
 412 template <class _InputIterator,
 413           class _Alloc,
 414           class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
 415           class = __enable_if_t<__is_allocator<_Alloc>::value>>
 416 queue(_InputIterator, _InputIterator, _Alloc)
 417     -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
 418 #endif
 419
 420 template <class _Tp, class _Container>
 421 inline _LIBCPP_INLINE_VISIBILITY
 422 bool
 423 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 424 {
 425     return __x.c == __y.c;
 426 }
 427
 428 template <class _Tp, class _Container>
 429 inline _LIBCPP_INLINE_VISIBILITY
 430 bool
 431 operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 432 {
 433     return __x.c < __y.c;
 434 }
 435
 436 template <class _Tp, class _Container>
 437 inline _LIBCPP_INLINE_VISIBILITY
 438 bool
 439 operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 440 {
 441     return !(__x == __y);
 442 }
 443
 444 template <class _Tp, class _Container>
 445 inline _LIBCPP_INLINE_VISIBILITY
 446 bool
 447 operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 448 {
 449     return __y < __x;
 450 }
 451
 452 template <class _Tp, class _Container>
 453 inline _LIBCPP_INLINE_VISIBILITY
 454 bool
 455 operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 456 {
 457     return !(__x < __y);
 458 }
 459
 460 template <class _Tp, class _Container>
 461 inline _LIBCPP_INLINE_VISIBILITY
 462 bool
 463 operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 464 {
 465     return !(__y < __x);
 466 }
 467
 468 template <class _Tp, class _Container>
 469 inline _LIBCPP_INLINE_VISIBILITY
 470 __enable_if_t<__is_swappable<_Container>::value, void>
 471 swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
 472     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 473 {
 474     __x.swap(__y);
 475 }
 476
 477 template <class _Tp, class _Container, class _Alloc>
 478 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc>
 479     : public uses_allocator<_Container, _Alloc>
 480 {
 481 };
 482
 483 template <class _Tp, class _Container = vector<_Tp>,
 484           class _Compare = less<typename _Container::value_type> >
 485 class _LIBCPP_TEMPLATE_VIS priority_queue
 486 {
 487 public:
 488     typedef _Container                               container_type;
 489     typedef _Compare                                 value_compare;
 490     typedef typename container_type::value_type      value_type;
 491     typedef typename container_type::reference       reference;
 492     typedef typename container_type::const_reference const_reference;
 493     typedef typename container_type::size_type       size_type;
 494     static_assert((is_same<_Tp, value_type>::value), "" );
 495
 496 protected:
 497     container_type c;
 498     value_compare comp;
 499
 500 public:
 501     _LIBCPP_INLINE_VISIBILITY
 502     priority_queue()
 503         _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
 504                    is_nothrow_default_constructible<value_compare>::value)
 505         : c(), comp() {}
 506
 507     _LIBCPP_INLINE_VISIBILITY
 508     priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
 509
 510     _LIBCPP_INLINE_VISIBILITY
 511     priority_queue& operator=(const priority_queue& __q)
 512         {c = __q.c; comp = __q.comp; return *this;}
 513
 514 #ifndef _LIBCPP_CXX03_LANG
 515     _LIBCPP_INLINE_VISIBILITY
 516     priority_queue(priority_queue&& __q)
 517         _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
 518                    is_nothrow_move_constructible<value_compare>::value)
 519         : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
 520
 521     _LIBCPP_INLINE_VISIBILITY
 522     priority_queue& operator=(priority_queue&& __q)
 523         _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
 524                    is_nothrow_move_assignable<value_compare>::value)
 525         {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
 526 #endif // _LIBCPP_CXX03_LANG
 527
 528     _LIBCPP_INLINE_VISIBILITY
 529     explicit priority_queue(const value_compare& __comp)
 530         : c(), comp(__comp) {}
 531     _LIBCPP_INLINE_VISIBILITY
 532     priority_queue(const value_compare& __comp, const container_type& __c);
 533 #ifndef _LIBCPP_CXX03_LANG
 534     _LIBCPP_INLINE_VISIBILITY
 535     priority_queue(const value_compare& __comp, container_type&& __c);
 536 #endif
 537     template <class _InputIter, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> >
 538         _LIBCPP_INLINE_VISIBILITY
 539         priority_queue(_InputIter __f, _InputIter __l,
 540                        const value_compare& __comp = value_compare());
 541     template <class _InputIter, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> >
 542         _LIBCPP_INLINE_VISIBILITY
 543         priority_queue(_InputIter __f, _InputIter __l,
 544                        const value_compare& __comp, const container_type& __c);
 545 #ifndef _LIBCPP_CXX03_LANG
 546     template <class _InputIter, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> >
 547         _LIBCPP_INLINE_VISIBILITY
 548         priority_queue(_InputIter __f, _InputIter __l,
 549                        const value_compare& __comp, container_type&& __c);
 550 #endif // _LIBCPP_CXX03_LANG
 551     template <class _Alloc>
 552         _LIBCPP_INLINE_VISIBILITY
 553         explicit priority_queue(const _Alloc& __a,
 554                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 555     template <class _Alloc>
 556         _LIBCPP_INLINE_VISIBILITY
 557         priority_queue(const value_compare& __comp, const _Alloc& __a,
 558                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 559     template <class _Alloc>
 560         _LIBCPP_INLINE_VISIBILITY
 561         priority_queue(const value_compare& __comp, const container_type& __c,
 562                        const _Alloc& __a,
 563                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 564     template <class _Alloc>
 565         _LIBCPP_INLINE_VISIBILITY
 566         priority_queue(const priority_queue& __q, const _Alloc& __a,
 567                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 568 #ifndef _LIBCPP_CXX03_LANG
 569     template <class _Alloc>
 570         _LIBCPP_INLINE_VISIBILITY
 571         priority_queue(const value_compare& __comp, container_type&& __c,
 572                        const _Alloc& __a,
 573                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 574     template <class _Alloc>
 575         _LIBCPP_INLINE_VISIBILITY
 576         priority_queue(priority_queue&& __q, const _Alloc& __a,
 577                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 578 #endif // _LIBCPP_CXX03_LANG
 579
 580     template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> >
 581         _LIBCPP_INLINE_VISIBILITY
 582         priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a,
 583                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 584
 585     template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> >
 586         _LIBCPP_INLINE_VISIBILITY
 587         priority_queue(_InputIter __f, _InputIter __l,
 588                        const value_compare& __comp, const _Alloc& __a,
 589                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 590
 591     template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> >
 592         _LIBCPP_INLINE_VISIBILITY
 593         priority_queue(_InputIter __f, _InputIter __l,
 594                        const value_compare& __comp, const container_type& __c, const _Alloc& __a,
 595                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 596
 597 #ifndef _LIBCPP_CXX03_LANG
 598     template <class _InputIter, class _Alloc, class = __enable_if_t<__is_cpp17_input_iterator<_InputIter>::value> >
 599         _LIBCPP_INLINE_VISIBILITY
 600         priority_queue(_InputIter __f, _InputIter __l,
 601                        const value_compare& __comp, container_type&& __c, const _Alloc& __a,
 602                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0);
 603 #endif  // _LIBCPP_CXX03_LANG
 604
 605     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 606     bool            empty() const {return c.empty();}
 607     _LIBCPP_INLINE_VISIBILITY
 608     size_type       size() const  {return c.size();}
 609     _LIBCPP_INLINE_VISIBILITY
 610     const_reference top() const   {return c.front();}
 611
 612     _LIBCPP_INLINE_VISIBILITY
 613     void push(const value_type& __v);
 614 #ifndef _LIBCPP_CXX03_LANG
 615     _LIBCPP_INLINE_VISIBILITY
 616     void push(value_type&& __v);
 617     template <class... _Args>
 618     _LIBCPP_INLINE_VISIBILITY
 619     void emplace(_Args&&... __args);
 620 #endif // _LIBCPP_CXX03_LANG
 621     _LIBCPP_INLINE_VISIBILITY
 622     void pop();
 623
 624     _LIBCPP_INLINE_VISIBILITY
 625     void swap(priority_queue& __q)
 626         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
 627                    __is_nothrow_swappable<value_compare>::value);
 628 };
 629
 630 #if _LIBCPP_STD_VER >= 17
 631 template <class _Compare,
 632           class _Container,
 633           class = enable_if_t<!__is_allocator<_Compare>::value>,
 634           class = enable_if_t<!__is_allocator<_Container>::value>
 635 >
 636 priority_queue(_Compare, _Container)
 637     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 638
 639 template<class _InputIterator,
 640          class _Compare = less<__iter_value_type<_InputIterator>>,
 641          class _Container = vector<__iter_value_type<_InputIterator>>,
 642          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
 643          class = enable_if_t<!__is_allocator<_Compare>::value>,
 644          class = enable_if_t<!__is_allocator<_Container>::value>
 645 >
 646 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
 647     -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
 648
 649 template<class _Compare,
 650          class _Container,
 651          class _Alloc,
 652          class = enable_if_t<!__is_allocator<_Compare>::value>,
 653          class = enable_if_t<!__is_allocator<_Container>::value>,
 654          class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
 655 >
 656 priority_queue(_Compare, _Container, _Alloc)
 657     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 658
 659 template<class _InputIterator, class _Allocator,
 660          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
 661          class = enable_if_t<__is_allocator<_Allocator>::value>
 662 >
 663 priority_queue(_InputIterator, _InputIterator, _Allocator)
 664     -> priority_queue<__iter_value_type<_InputIterator>,
 665                       vector<__iter_value_type<_InputIterator>, _Allocator>,
 666                       less<__iter_value_type<_InputIterator>>>;
 667
 668 template<class _InputIterator, class _Compare, class _Allocator,
 669          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
 670          class = enable_if_t<!__is_allocator<_Compare>::value>,
 671          class = enable_if_t<__is_allocator<_Allocator>::value>
 672 >
 673 priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
 674     -> priority_queue<__iter_value_type<_InputIterator>,
 675                       vector<__iter_value_type<_InputIterator>, _Allocator>, _Compare>;
 676
 677 template<class _InputIterator, class _Compare, class _Container, class _Alloc,
 678          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
 679          class = enable_if_t<!__is_allocator<_Compare>::value>,
 680          class = enable_if_t<!__is_allocator<_Container>::value>,
 681          class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
 682 >
 683 priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
 684     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 685 #endif
 686
 687 template <class _Tp, class _Container, class _Compare>
 688 inline
 689 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
 690                                                           const container_type& __c)
 691     : c(__c),
 692       comp(__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 inline
 701 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 702                                                           container_type&& __c)
 703     : c(_VSTD::move(__c)),
 704       comp(__comp)
 705 {
 706     _VSTD::make_heap(c.begin(), c.end(), comp);
 707 }
 708
 709 #endif // _LIBCPP_CXX03_LANG
 710
 711 template <class _Tp, class _Container, class _Compare>
 712 template <class _InputIter, class>
 713 inline
 714 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
 715                                                           const value_compare& __comp)
 716     : c(__f, __l),
 717       comp(__comp)
 718 {
 719     _VSTD::make_heap(c.begin(), c.end(), comp);
 720 }
 721
 722 template <class _Tp, class _Container, class _Compare>
 723 template <class _InputIter, class>
 724 inline
 725 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
 726                                                           const value_compare& __comp,
 727                                                           const container_type& __c)
 728     : c(__c),
 729       comp(__comp)
 730 {
 731     c.insert(c.end(), __f, __l);
 732     _VSTD::make_heap(c.begin(), c.end(), comp);
 733 }
 734
 735 #ifndef _LIBCPP_CXX03_LANG
 736
 737 template <class _Tp, class _Container, class _Compare>
 738 template <class _InputIter, class>
 739 inline
 740 priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
 741                                                           const value_compare& __comp,
 742                                                           container_type&& __c)
 743     : c(_VSTD::move(__c)),
 744       comp(__comp)
 745 {
 746     c.insert(c.end(), __f, __l);
 747     _VSTD::make_heap(c.begin(), c.end(), comp);
 748 }
 749
 750 #endif // _LIBCPP_CXX03_LANG
 751
 752 template <class _Tp, class _Container, class _Compare>
 753 template <class _Alloc>
 754 inline
 755 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
 756                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 757     : c(__a)
 758 {
 759 }
 760
 761 template <class _Tp, class _Container, class _Compare>
 762 template <class _Alloc>
 763 inline
 764 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 765                                                           const _Alloc& __a,
 766                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 767     : c(__a),
 768       comp(__comp)
 769 {
 770 }
 771
 772 template <class _Tp, class _Container, class _Compare>
 773 template <class _Alloc>
 774 inline
 775 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 776                                                           const container_type& __c,
 777                                                           const _Alloc& __a,
 778                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 779     : c(__c, __a),
 780       comp(__comp)
 781 {
 782     _VSTD::make_heap(c.begin(), c.end(), comp);
 783 }
 784
 785 template <class _Tp, class _Container, class _Compare>
 786 template <class _Alloc>
 787 inline
 788 priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
 789                                                           const _Alloc& __a,
 790                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 791     : c(__q.c, __a),
 792       comp(__q.comp)
 793 {
 794 }
 795
 796 #ifndef _LIBCPP_CXX03_LANG
 797
 798 template <class _Tp, class _Container, class _Compare>
 799 template <class _Alloc>
 800 inline
 801 priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
 802                                                           container_type&& __c,
 803                                                           const _Alloc& __a,
 804                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 805     : c(_VSTD::move(__c), __a),
 806       comp(__comp)
 807 {
 808     _VSTD::make_heap(c.begin(), c.end(), comp);
 809 }
 810
 811 template <class _Tp, class _Container, class _Compare>
 812 template <class _Alloc>
 813 inline
 814 priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
 815                                                           const _Alloc& __a,
 816                        __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 817     : c(_VSTD::move(__q.c), __a),
 818       comp(_VSTD::move(__q.comp))
 819 {
 820 }
 821
 822 #endif  // _LIBCPP_CXX03_LANG
 823
 824 template <class _Tp, class _Container, class _Compare>
 825 template <class _InputIter, class _Alloc, class>
 826 inline
 827 priority_queue<_Tp, _Container, _Compare>::priority_queue(
 828         _InputIter __f, _InputIter __l, const _Alloc& __a,
 829         __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 830     : c(__f, __l, __a),
 831       comp()
 832 {
 833     _VSTD::make_heap(c.begin(), c.end(), comp);
 834 }
 835
 836 template <class _Tp, class _Container, class _Compare>
 837 template <class _InputIter, class _Alloc, class>
 838 inline
 839 priority_queue<_Tp, _Container, _Compare>::priority_queue(
 840         _InputIter __f, _InputIter __l,
 841         const value_compare& __comp, const _Alloc& __a,
 842         __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 843     : c(__f, __l, __a),
 844       comp(__comp)
 845 {
 846     _VSTD::make_heap(c.begin(), c.end(), comp);
 847 }
 848
 849 template <class _Tp, class _Container, class _Compare>
 850 template <class _InputIter, class _Alloc, class>
 851 inline
 852 priority_queue<_Tp, _Container, _Compare>::priority_queue(
 853         _InputIter __f, _InputIter __l,
 854         const value_compare& __comp, const container_type& __c, const _Alloc& __a,
 855         __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 856     : c(__c, __a),
 857       comp(__comp)
 858 {
 859     c.insert(c.end(), __f, __l);
 860     _VSTD::make_heap(c.begin(), c.end(), comp);
 861 }
 862
 863 #ifndef _LIBCPP_CXX03_LANG
 864 template <class _Tp, class _Container, class _Compare>
 865 template <class _InputIter, class _Alloc, class>
 866 inline
 867 priority_queue<_Tp, _Container, _Compare>::priority_queue(
 868         _InputIter __f, _InputIter __l, const value_compare& __comp,
 869         container_type&& __c, const _Alloc& __a,
 870         __enable_if_t<uses_allocator<container_type, _Alloc>::value>*)
 871     : c(_VSTD::move(__c), __a),
 872       comp(__comp)
 873 {
 874     c.insert(c.end(), __f, __l);
 875     _VSTD::make_heap(c.begin(), c.end(), comp);
 876 }
 877 #endif  // _LIBCPP_CXX03_LANG
 878
 879 template <class _Tp, class _Container, class _Compare>
 880 inline
 881 void
 882 priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
 883 {
 884     c.push_back(__v);
 885     _VSTD::push_heap(c.begin(), c.end(), comp);
 886 }
 887
 888 #ifndef _LIBCPP_CXX03_LANG
 889
 890 template <class _Tp, class _Container, class _Compare>
 891 inline
 892 void
 893 priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
 894 {
 895     c.push_back(_VSTD::move(__v));
 896     _VSTD::push_heap(c.begin(), c.end(), comp);
 897 }
 898
 899 template <class _Tp, class _Container, class _Compare>
 900 template <class... _Args>
 901 inline
 902 void
 903 priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
 904 {
 905     c.emplace_back(_VSTD::forward<_Args>(__args)...);
 906     _VSTD::push_heap(c.begin(), c.end(), comp);
 907 }
 908
 909 #endif // _LIBCPP_CXX03_LANG
 910
 911 template <class _Tp, class _Container, class _Compare>
 912 inline
 913 void
 914 priority_queue<_Tp, _Container, _Compare>::pop()
 915 {
 916     _VSTD::pop_heap(c.begin(), c.end(), comp);
 917     c.pop_back();
 918 }
 919
 920 template <class _Tp, class _Container, class _Compare>
 921 inline
 922 void
 923 priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
 924         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
 925                    __is_nothrow_swappable<value_compare>::value)
 926 {
 927     using _VSTD::swap;
 928     swap(c, __q.c);
 929     swap(comp, __q.comp);
 930 }
 931
 932 template <class _Tp, class _Container, class _Compare>
 933 inline _LIBCPP_INLINE_VISIBILITY
 934 __enable_if_t<
 935     __is_swappable<_Container>::value && __is_swappable<_Compare>::value,
 936     void
 937 >
 938 swap(priority_queue<_Tp, _Container, _Compare>& __x,
 939      priority_queue<_Tp, _Container, _Compare>& __y)
 940     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 941 {
 942     __x.swap(__y);
 943 }
 944
 945 template <class _Tp, class _Container, class _Compare, class _Alloc>
 946 struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
 947     : public uses_allocator<_Container, _Alloc>
 948 {
 949 };
 950
 951 _LIBCPP_END_NAMESPACE_STD
 952
 953 #endif // _LIBCPP_QUEUE