xref: /llvm-project-15.0.7/libcxx/include/queue (revision 0ab5e2cd) 
1// -*- C++ -*-
2//===--------------------------- queue ------------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_QUEUE
12#define _LIBCPP_QUEUE
13
14/*
15    queue synopsis
16
17namespace std
18{
19
20template <class T, class Container = deque<T>>
21class queue
22{
23public:
24    typedef Container                                container_type;
25    typedef typename container_type::value_type      value_type;
26    typedef typename container_type::reference       reference;
27    typedef typename container_type::const_reference const_reference;
28    typedef typename container_type::size_type       size_type;
29
30protected:
31    container_type c;
32
33public:
34    queue();
35    explicit queue(const container_type& c);
36    explicit queue(container_type&& c);
37    queue(queue&& q);
38    template <class Alloc>
39        explicit queue(const Alloc& a);
40    template <class Alloc>
41        queue(const container_type& c, const Alloc& a);
42    template <class Alloc>
43        queue(container_type&& c, const Alloc& a);
44    template <class Alloc>
45        queue(queue&& q, const Alloc& a);
46
47    queue& operator=(queue&& q);
48
49    bool      empty() const;
50    size_type size() const;
51
52    reference       front();
53    const_reference front() const;
54    reference       back();
55    const_reference back() const;
56
57    void push(const value_type& v);
58    void push(value_type&& v);
59    template <class... Args> void emplace(Args&&... args);
60    void pop();
61
62    void swap(queue& q);
63};
64
65template <class T, class Container>
66  bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
67
68template <class T, class Container>
69  bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
70
71template <class T, class Container>
72  bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
73
74template <class T, class Container>
75  bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
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  void swap(queue<T, Container>& x, queue<T, Container>& y);
85
86template <class T, class Container = vector<T>,
87          class Compare = less<typename Container::value_type>>
88class priority_queue
89{
90public:
91    typedef Container                                container_type;
92    typedef typename container_type::value_type      value_type;
93    typedef typename container_type::reference       reference;
94    typedef typename container_type::const_reference const_reference;
95    typedef typename container_type::size_type       size_type;
96
97protected:
98    container_type c;
99    Compare comp;
100
101public:
102    explicit priority_queue(const Compare& comp = Compare());
103    priority_queue(const Compare& comp, const container_type& c);
104    explicit priority_queue(const Compare& comp, container_type&& c);
105    template <class InputIterator>
106        priority_queue(InputIterator first, InputIterator last,
107                       const Compare& comp = Compare());
108    template <class InputIterator>
109        priority_queue(InputIterator first, InputIterator last,
110                       const Compare& comp, const container_type& c);
111    template <class InputIterator>
112        priority_queue(InputIterator first, InputIterator last,
113                       const Compare& comp, container_type&& c);
114    priority_queue(priority_queue&& q);
115    priority_queue& operator=(priority_queue&& q);
116    template <class Alloc>
117        explicit priority_queue(const Alloc& a);
118    template <class Alloc>
119        priority_queue(const Compare& comp, const Alloc& a);
120    template <class Alloc>
121        priority_queue(const Compare& comp, const container_type& c,
122                       const Alloc& a);
123    template <class Alloc>
124        priority_queue(const Compare& comp, container_type&& c,
125                       const Alloc& a);
126    template <class Alloc>
127        priority_queue(priority_queue&& q, const Alloc& a);
128
129    bool            empty() const;
130    size_type       size() const;
131    const_reference top() const;
132
133    void push(const value_type& v);
134    void push(value_type&& v);
135    template <class... Args> void emplace(Args&&... args);
136    void pop();
137
138    void swap(priority_queue& q);
139};
140
141template <class T, class Container, class Compare>
142  void swap(priority_queue<T, Container, Compare>& x,
143            priority_queue<T, Container, Compare>& y);
144
145}  // std
146
147*/
148
149#include <__config>
150#include <deque>
151#include <vector>
152#include <functional>
153#include <algorithm>
154
155#pragma GCC system_header
156
157_LIBCPP_BEGIN_NAMESPACE_STD
158
159template <class _Tp, class _Container> class queue;
160
161template <class _Tp, class _Container>
162bool
163operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
164
165template <class _Tp, class _Container>
166bool
167operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
168
169template <class _Tp, class _Container = deque<_Tp> >
170class _LIBCPP_VISIBLE queue
171{
172public:
173    typedef _Container                               container_type;
174    typedef typename container_type::value_type      value_type;
175    typedef typename container_type::reference       reference;
176    typedef typename container_type::const_reference const_reference;
177    typedef typename container_type::size_type       size_type;
178
179protected:
180    container_type c;
181
182public:
183    _LIBCPP_INLINE_VISIBILITY
184    queue() : c() {}
185    _LIBCPP_INLINE_VISIBILITY
186    explicit queue(const container_type& __c)  : c(__c) {}
187#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
188    _LIBCPP_INLINE_VISIBILITY
189    explicit queue(container_type&& __c) : c(_STD::move(__c)) {}
190    _LIBCPP_INLINE_VISIBILITY
191    queue(queue&& __q) : c(_STD::move(__q.c)) {}
192#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
193    template <class _Alloc>
194        _LIBCPP_INLINE_VISIBILITY
195        explicit queue(const _Alloc& __a,
196                       typename enable_if<uses_allocator<container_type,
197                                                         _Alloc>::value>::type* = 0)
198            : c(__a) {}
199    template <class _Alloc>
200        _LIBCPP_INLINE_VISIBILITY
201        queue(const queue& __q, const _Alloc& __a,
202                       typename enable_if<uses_allocator<container_type,
203                                                         _Alloc>::value>::type* = 0)
204            : c(__q.c, __a) {}
205    template <class _Alloc>
206        _LIBCPP_INLINE_VISIBILITY
207        queue(const container_type& __c, const _Alloc& __a,
208                       typename enable_if<uses_allocator<container_type,
209                                                         _Alloc>::value>::type* = 0)
210            : c(__c, __a) {}
211#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
212    template <class _Alloc>
213        _LIBCPP_INLINE_VISIBILITY
214        queue(container_type&& __c, const _Alloc& __a,
215                       typename enable_if<uses_allocator<container_type,
216                                                         _Alloc>::value>::type* = 0)
217            : c(_STD::move(__c), __a) {}
218    template <class _Alloc>
219        _LIBCPP_INLINE_VISIBILITY
220        queue(queue&& __q, const _Alloc& __a,
221                       typename enable_if<uses_allocator<container_type,
222                                                         _Alloc>::value>::type* = 0)
223            : c(_STD::move(__q.c), __a) {}
224
225    _LIBCPP_INLINE_VISIBILITY
226    queue& operator=(queue&& __q)
227    {
228        c = _STD::move(__q.c);
229        return *this;
230    }
231#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
232
233    _LIBCPP_INLINE_VISIBILITY
234    bool      empty() const {return c.empty();}
235    _LIBCPP_INLINE_VISIBILITY
236    size_type size() const  {return c.size();}
237
238    _LIBCPP_INLINE_VISIBILITY
239    reference       front()       {return c.front();}
240    _LIBCPP_INLINE_VISIBILITY
241    const_reference front() const {return c.front();}
242    _LIBCPP_INLINE_VISIBILITY
243    reference       back()        {return c.back();}
244    _LIBCPP_INLINE_VISIBILITY
245    const_reference back() const  {return c.back();}
246
247    _LIBCPP_INLINE_VISIBILITY
248    void push(const value_type& __v) {c.push_back(__v);}
249#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
250    _LIBCPP_INLINE_VISIBILITY
251    void push(value_type&& __v)      {c.push_back(_STD::move(__v));}
252#ifndef _LIBCPP_HAS_NO_VARIADICS
253    template <class... _Args>
254        _LIBCPP_INLINE_VISIBILITY
255        void emplace(_Args&&... __args)
256            {c.emplace_back(_STD::forward<_Args>(__args)...);}
257#endif  // _LIBCPP_HAS_NO_VARIADICS
258#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
259    _LIBCPP_INLINE_VISIBILITY
260    void pop() {c.pop_front();}
261
262    _LIBCPP_INLINE_VISIBILITY
263    void swap(queue& __q)
264    {
265        using _STD::swap;
266        swap(c, __q.c);
267    }
268
269    template <class _T1, class _C1>
270    friend
271    _LIBCPP_INLINE_VISIBILITY
272    bool
273    operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
274
275    template <class _T1, class _C1>
276    friend
277    _LIBCPP_INLINE_VISIBILITY
278    bool
279    operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
280};
281
282template <class _Tp, class _Container>
283inline _LIBCPP_INLINE_VISIBILITY
284bool
285operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
286{
287    return __x.c == __y.c;
288}
289
290template <class _Tp, class _Container>
291inline _LIBCPP_INLINE_VISIBILITY
292bool
293operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
294{
295    return __x.c < __y.c;
296}
297
298template <class _Tp, class _Container>
299inline _LIBCPP_INLINE_VISIBILITY
300bool
301operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
302{
303    return !(__x == __y);
304}
305
306template <class _Tp, class _Container>
307inline _LIBCPP_INLINE_VISIBILITY
308bool
309operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
310{
311    return __y < __x;
312}
313
314template <class _Tp, class _Container>
315inline _LIBCPP_INLINE_VISIBILITY
316bool
317operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
318{
319    return !(__x < __y);
320}
321
322template <class _Tp, class _Container>
323inline _LIBCPP_INLINE_VISIBILITY
324bool
325operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
326{
327    return !(__y < __x);
328}
329
330template <class _Tp, class _Container>
331inline _LIBCPP_INLINE_VISIBILITY
332void
333swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
334{
335    __x.swap(__y);
336}
337
338template <class _Tp, class _Container, class _Alloc>
339struct _LIBCPP_VISIBLE uses_allocator<queue<_Tp, _Container>, _Alloc>
340    : public uses_allocator<_Container, _Alloc>
341{
342};
343
344template <class _Tp, class _Container = vector<_Tp>,
345          class _Compare = less<typename _Container::value_type> >
346class _LIBCPP_VISIBLE priority_queue
347{
348public:
349    typedef _Container                               container_type;
350    typedef _Compare                                 value_compare;
351    typedef typename container_type::value_type      value_type;
352    typedef typename container_type::reference       reference;
353    typedef typename container_type::const_reference const_reference;
354    typedef typename container_type::size_type       size_type;
355
356protected:
357    container_type c;
358    value_compare comp;
359
360public:
361    _LIBCPP_INLINE_VISIBILITY
362    explicit priority_queue(const value_compare& __comp = value_compare())
363        : c(), comp(__comp) {}
364    priority_queue(const value_compare& __comp, const container_type& __c);
365#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
366    explicit priority_queue(const value_compare& __comp, container_type&& __c);
367#endif
368    template <class _InputIter>
369        priority_queue(_InputIter __f, _InputIter __l,
370                       const value_compare& __comp = value_compare());
371    template <class _InputIter>
372        priority_queue(_InputIter __f, _InputIter __l,
373                       const value_compare& __comp, const container_type& __c);
374#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
375    template <class _InputIter>
376        priority_queue(_InputIter __f, _InputIter __l,
377                       const value_compare& __comp, container_type&& __c);
378    priority_queue(priority_queue&& __q);
379    priority_queue& operator=(priority_queue&& __q);
380#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
381    template <class _Alloc>
382        explicit priority_queue(const _Alloc& __a,
383                       typename enable_if<uses_allocator<container_type,
384                                                         _Alloc>::value>::type* = 0);
385    template <class _Alloc>
386        priority_queue(const value_compare& __comp, const _Alloc& __a,
387                       typename enable_if<uses_allocator<container_type,
388                                                         _Alloc>::value>::type* = 0);
389    template <class _Alloc>
390        priority_queue(const value_compare& __comp, const container_type& __c,
391                       const _Alloc& __a,
392                       typename enable_if<uses_allocator<container_type,
393                                                         _Alloc>::value>::type* = 0);
394    template <class _Alloc>
395        priority_queue(const priority_queue& __q, const _Alloc& __a,
396                       typename enable_if<uses_allocator<container_type,
397                                                         _Alloc>::value>::type* = 0);
398#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
399    template <class _Alloc>
400        priority_queue(const value_compare& __comp, container_type&& __c,
401                       const _Alloc& __a,
402                       typename enable_if<uses_allocator<container_type,
403                                                         _Alloc>::value>::type* = 0);
404    template <class _Alloc>
405        priority_queue(priority_queue&& __q, const _Alloc& __a,
406                       typename enable_if<uses_allocator<container_type,
407                                                         _Alloc>::value>::type* = 0);
408#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
409
410    _LIBCPP_INLINE_VISIBILITY
411    bool            empty() const {return c.empty();}
412    _LIBCPP_INLINE_VISIBILITY
413    size_type       size() const  {return c.size();}
414    _LIBCPP_INLINE_VISIBILITY
415    const_reference top() const   {return c.front();}
416
417    void push(const value_type& __v);
418#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
419    void push(value_type&& __v);
420#ifndef _LIBCPP_HAS_NO_VARIADICS
421    template <class... _Args> void emplace(_Args&&... __args);
422#endif
423#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
424    void pop();
425
426    void swap(priority_queue& __q);
427};
428
429template <class _Tp, class _Container, class _Compare>
430inline _LIBCPP_INLINE_VISIBILITY
431priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
432                                                          const container_type& __c)
433    : c(__c),
434      comp(__comp)
435{
436    _STD::make_heap(c.begin(), c.end(), comp);
437}
438
439#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
440
441template <class _Tp, class _Container, class _Compare>
442inline _LIBCPP_INLINE_VISIBILITY
443priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
444                                                          container_type&& __c)
445    : c(_STD::move(__c)),
446      comp(__comp)
447{
448    _STD::make_heap(c.begin(), c.end(), comp);
449}
450
451#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
452
453template <class _Tp, class _Container, class _Compare>
454template <class _InputIter>
455inline _LIBCPP_INLINE_VISIBILITY
456priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
457                                                          const value_compare& __comp)
458    : c(__f, __l),
459      comp(__comp)
460{
461    _STD::make_heap(c.begin(), c.end(), comp);
462}
463
464template <class _Tp, class _Container, class _Compare>
465template <class _InputIter>
466inline _LIBCPP_INLINE_VISIBILITY
467priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
468                                                          const value_compare& __comp,
469                                                          const container_type& __c)
470    : c(__c),
471      comp(__comp)
472{
473    c.insert(c.end(), __f, __l);
474    _STD::make_heap(c.begin(), c.end(), comp);
475}
476
477#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
478
479template <class _Tp, class _Container, class _Compare>
480template <class _InputIter>
481inline _LIBCPP_INLINE_VISIBILITY
482priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
483                                                          const value_compare& __comp,
484                                                          container_type&& __c)
485    : c(_STD::move(__c)),
486      comp(__comp)
487{
488    c.insert(c.end(), __f, __l);
489    _STD::make_heap(c.begin(), c.end(), comp);
490}
491
492template <class _Tp, class _Container, class _Compare>
493inline _LIBCPP_INLINE_VISIBILITY
494priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q)
495    : c(_STD::move(__q.c)),
496      comp(_STD::move(__q.comp))
497{
498}
499
500template <class _Tp, class _Container, class _Compare>
501priority_queue<_Tp, _Container, _Compare>&
502priority_queue<_Tp, _Container, _Compare>::operator=(priority_queue&& __q)
503{
504    c = _STD::move(__q.c);
505    comp = _STD::move(__q.comp);
506    return *this;
507}
508
509#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
510
511template <class _Tp, class _Container, class _Compare>
512template <class _Alloc>
513inline _LIBCPP_INLINE_VISIBILITY
514priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
515                       typename enable_if<uses_allocator<container_type,
516                                                         _Alloc>::value>::type*)
517    : c(__a)
518{
519}
520
521template <class _Tp, class _Container, class _Compare>
522template <class _Alloc>
523inline _LIBCPP_INLINE_VISIBILITY
524priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
525                                                          const _Alloc& __a,
526                       typename enable_if<uses_allocator<container_type,
527                                                         _Alloc>::value>::type*)
528    : c(__a),
529      comp(__comp)
530{
531}
532
533template <class _Tp, class _Container, class _Compare>
534template <class _Alloc>
535inline _LIBCPP_INLINE_VISIBILITY
536priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
537                                                          const container_type& __c,
538                                                          const _Alloc& __a,
539                       typename enable_if<uses_allocator<container_type,
540                                                         _Alloc>::value>::type*)
541    : c(__c, __a),
542      comp(__comp)
543{
544    _STD::make_heap(c.begin(), c.end(), comp);
545}
546
547template <class _Tp, class _Container, class _Compare>
548template <class _Alloc>
549inline _LIBCPP_INLINE_VISIBILITY
550priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
551                                                          const _Alloc& __a,
552                       typename enable_if<uses_allocator<container_type,
553                                                         _Alloc>::value>::type*)
554    : c(__q.c, __a),
555      comp(__q.comp)
556{
557    _STD::make_heap(c.begin(), c.end(), comp);
558}
559
560#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
561
562template <class _Tp, class _Container, class _Compare>
563template <class _Alloc>
564inline _LIBCPP_INLINE_VISIBILITY
565priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
566                                                          container_type&& __c,
567                                                          const _Alloc& __a,
568                       typename enable_if<uses_allocator<container_type,
569                                                         _Alloc>::value>::type*)
570    : c(_STD::move(__c), __a),
571      comp(__comp)
572{
573    _STD::make_heap(c.begin(), c.end(), comp);
574}
575
576template <class _Tp, class _Container, class _Compare>
577template <class _Alloc>
578inline _LIBCPP_INLINE_VISIBILITY
579priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
580                                                          const _Alloc& __a,
581                       typename enable_if<uses_allocator<container_type,
582                                                         _Alloc>::value>::type*)
583    : c(_STD::move(__q.c), __a),
584      comp(_STD::move(__q.comp))
585{
586    _STD::make_heap(c.begin(), c.end(), comp);
587}
588
589#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
590
591template <class _Tp, class _Container, class _Compare>
592inline _LIBCPP_INLINE_VISIBILITY
593void
594priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
595{
596    c.push_back(__v);
597    _STD::push_heap(c.begin(), c.end(), comp);
598}
599
600#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
601
602template <class _Tp, class _Container, class _Compare>
603inline _LIBCPP_INLINE_VISIBILITY
604void
605priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
606{
607    c.push_back(_STD::move(__v));
608    _STD::push_heap(c.begin(), c.end(), comp);
609}
610
611#ifndef _LIBCPP_HAS_NO_VARIADICS
612
613template <class _Tp, class _Container, class _Compare>
614template <class... _Args>
615inline _LIBCPP_INLINE_VISIBILITY
616void
617priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
618{
619    c.emplace_back(_STD::forward<_Args>(__args)...);
620    _STD::push_heap(c.begin(), c.end(), comp);
621}
622
623#endif  // _LIBCPP_HAS_NO_VARIADICS
624#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
625
626template <class _Tp, class _Container, class _Compare>
627inline _LIBCPP_INLINE_VISIBILITY
628void
629priority_queue<_Tp, _Container, _Compare>::pop()
630{
631    _STD::pop_heap(c.begin(), c.end(), comp);
632    c.pop_back();
633}
634
635template <class _Tp, class _Container, class _Compare>
636inline _LIBCPP_INLINE_VISIBILITY
637void
638priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
639{
640    using _STD::swap;
641    swap(c, __q.c);
642    swap(comp, __q.comp);
643}
644
645template <class _Tp, class _Container, class _Compare>
646inline _LIBCPP_INLINE_VISIBILITY
647void
648swap(priority_queue<_Tp, _Container, _Compare>& __x,
649     priority_queue<_Tp, _Container, _Compare>& __y)
650{
651    __x.swap(__y);
652}
653
654template <class _Tp, class _Container, class _Compare, class _Alloc>
655struct _LIBCPP_VISIBLE uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
656    : public uses_allocator<_Container, _Alloc>
657{
658};
659
660_LIBCPP_END_NAMESPACE_STD
661
662#endif  // _LIBCPP_QUEUE
663