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