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