xref: /freebsd/contrib/llvm-project/libcxx/include/queue (revision d4eeb02986980bf33dd56c41ceb9fc5f180c0d47) 
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 <__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
238template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue;
239
240template <class _Tp, class _Container>
241_LIBCPP_INLINE_VISIBILITY
242bool
243operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
244
245template <class _Tp, class _Container>
246_LIBCPP_INLINE_VISIBILITY
247bool
248operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
249
250template <class _Tp, class _Container /*= deque<_Tp>*/>
251class _LIBCPP_TEMPLATE_VIS queue
252{
253public:
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
261protected:
262    container_type c;
263
264public:
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
391template<class _Container,
392         class = enable_if_t<!__is_allocator<_Container>::value>
393>
394queue(_Container)
395    -> queue<typename _Container::value_type, _Container>;
396
397template<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>
402queue(_Container, _Alloc)
403    -> queue<typename _Container::value_type, _Container>;
404#endif
405
406#if _LIBCPP_STD_VER > 20
407template <class _InputIterator,
408          class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>>
409queue(_InputIterator, _InputIterator)
410    -> queue<__iter_value_type<_InputIterator>>;
411
412template <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>>
416queue(_InputIterator, _InputIterator, _Alloc)
417    -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
418#endif
419
420template <class _Tp, class _Container>
421inline _LIBCPP_INLINE_VISIBILITY
422bool
423operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
424{
425    return __x.c == __y.c;
426}
427
428template <class _Tp, class _Container>
429inline _LIBCPP_INLINE_VISIBILITY
430bool
431operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
432{
433    return __x.c < __y.c;
434}
435
436template <class _Tp, class _Container>
437inline _LIBCPP_INLINE_VISIBILITY
438bool
439operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
440{
441    return !(__x == __y);
442}
443
444template <class _Tp, class _Container>
445inline _LIBCPP_INLINE_VISIBILITY
446bool
447operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
448{
449    return __y < __x;
450}
451
452template <class _Tp, class _Container>
453inline _LIBCPP_INLINE_VISIBILITY
454bool
455operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
456{
457    return !(__x < __y);
458}
459
460template <class _Tp, class _Container>
461inline _LIBCPP_INLINE_VISIBILITY
462bool
463operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
464{
465    return !(__y < __x);
466}
467
468template <class _Tp, class _Container>
469inline _LIBCPP_INLINE_VISIBILITY
470__enable_if_t<__is_swappable<_Container>::value, void>
471swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
472    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
473{
474    __x.swap(__y);
475}
476
477template <class _Tp, class _Container, class _Alloc>
478struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc>
479    : public uses_allocator<_Container, _Alloc>
480{
481};
482
483template <class _Tp, class _Container = vector<_Tp>,
484          class _Compare = less<typename _Container::value_type> >
485class _LIBCPP_TEMPLATE_VIS priority_queue
486{
487public:
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
496protected:
497    container_type c;
498    value_compare comp;
499
500public:
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
631template <class _Compare,
632          class _Container,
633          class = enable_if_t<!__is_allocator<_Compare>::value>,
634          class = enable_if_t<!__is_allocator<_Container>::value>
635>
636priority_queue(_Compare, _Container)
637    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
638
639template<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>
646priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
647    -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
648
649template<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>
656priority_queue(_Compare, _Container, _Alloc)
657    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
658
659template<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>
663priority_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
668template<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>
673priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
674    -> priority_queue<__iter_value_type<_InputIterator>,
675                      vector<__iter_value_type<_InputIterator>, _Allocator>, _Compare>;
676
677template<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>
683priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
684    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
685#endif
686
687template <class _Tp, class _Container, class _Compare>
688inline
689priority_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
699template <class _Tp, class _Container, class _Compare>
700inline
701priority_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
711template <class _Tp, class _Container, class _Compare>
712template <class _InputIter, class>
713inline
714priority_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
722template <class _Tp, class _Container, class _Compare>
723template <class _InputIter, class>
724inline
725priority_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
737template <class _Tp, class _Container, class _Compare>
738template <class _InputIter, class>
739inline
740priority_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
752template <class _Tp, class _Container, class _Compare>
753template <class _Alloc>
754inline
755priority_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
761template <class _Tp, class _Container, class _Compare>
762template <class _Alloc>
763inline
764priority_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
772template <class _Tp, class _Container, class _Compare>
773template <class _Alloc>
774inline
775priority_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
785template <class _Tp, class _Container, class _Compare>
786template <class _Alloc>
787inline
788priority_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
798template <class _Tp, class _Container, class _Compare>
799template <class _Alloc>
800inline
801priority_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
811template <class _Tp, class _Container, class _Compare>
812template <class _Alloc>
813inline
814priority_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
824template <class _Tp, class _Container, class _Compare>
825template <class _InputIter, class _Alloc, class>
826inline
827priority_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
836template <class _Tp, class _Container, class _Compare>
837template <class _InputIter, class _Alloc, class>
838inline
839priority_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
849template <class _Tp, class _Container, class _Compare>
850template <class _InputIter, class _Alloc, class>
851inline
852priority_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
864template <class _Tp, class _Container, class _Compare>
865template <class _InputIter, class _Alloc, class>
866inline
867priority_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
879template <class _Tp, class _Container, class _Compare>
880inline
881void
882priority_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
890template <class _Tp, class _Container, class _Compare>
891inline
892void
893priority_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
899template <class _Tp, class _Container, class _Compare>
900template <class... _Args>
901inline
902void
903priority_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
911template <class _Tp, class _Container, class _Compare>
912inline
913void
914priority_queue<_Tp, _Container, _Compare>::pop()
915{
916    _VSTD::pop_heap(c.begin(), c.end(), comp);
917    c.pop_back();
918}
919
920template <class _Tp, class _Container, class _Compare>
921inline
922void
923priority_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
932template <class _Tp, class _Container, class _Compare>
933inline _LIBCPP_INLINE_VISIBILITY
934__enable_if_t<
935    __is_swappable<_Container>::value && __is_swappable<_Compare>::value,
936    void
937>
938swap(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
945template <class _Tp, class _Container, class _Compare, class _Alloc>
946struct _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
954