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