xref: /llvm-project-15.0.7/libcxx/include/queue (revision 30fdc8d8) 
1// -*- C++ -*-
2//===--------------------------- queue ------------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is distributed under the University of Illinois Open Source
7// License. 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 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    queue() : c() {}
184    explicit queue(const container_type& __c)  : c(__c) {}
185#ifdef _LIBCPP_MOVE
186    explicit queue(container_type&& __c) : c(_STD::move(__c)) {}
187    queue(queue&& __q) : c(_STD::move(__q.c)) {}
188#endif
189    template <class _Alloc>
190        explicit queue(const _Alloc& __a,
191                       typename enable_if<uses_allocator<container_type,
192                                                         _Alloc>::value>::type* = 0)
193            : c(__a) {}
194    template <class _Alloc>
195        queue(const queue& __q, const _Alloc& __a,
196                       typename enable_if<uses_allocator<container_type,
197                                                         _Alloc>::value>::type* = 0)
198            : c(__q.c, __a) {}
199    template <class _Alloc>
200        queue(const container_type& __c, const _Alloc& __a,
201                       typename enable_if<uses_allocator<container_type,
202                                                         _Alloc>::value>::type* = 0)
203            : c(__c, __a) {}
204#ifdef _LIBCPP_MOVE
205    template <class _Alloc>
206        queue(container_type&& __c, const _Alloc& __a,
207                       typename enable_if<uses_allocator<container_type,
208                                                         _Alloc>::value>::type* = 0)
209            : c(_STD::move(__c), __a) {}
210    template <class _Alloc>
211        queue(queue&& __q, const _Alloc& __a,
212                       typename enable_if<uses_allocator<container_type,
213                                                         _Alloc>::value>::type* = 0)
214            : c(_STD::move(__q.c), __a) {}
215
216    queue& operator=(queue&& __q)
217    {
218        c = _STD::move(__q.c);
219        return *this;
220    }
221#endif
222
223    bool      empty() const {return c.empty();}
224    size_type size() const  {return c.size();}
225
226    reference       front()       {return c.front();}
227    const_reference front() const {return c.front();}
228    reference       back()        {return c.back();}
229    const_reference back() const  {return c.back();}
230
231    void push(const value_type& __v) {c.push_back(__v);}
232#ifdef _LIBCPP_MOVE
233    void push(value_type&& __v)      {c.push_back(_STD::move(__v));}
234    template <class... _Args>
235        void emplace(_Args&&... __args)
236            {c.emplace_back(_STD::forward<_Args>(__args)...);}
237#endif
238    void pop() {c.pop_front();}
239
240    void swap(queue& __q)
241    {
242        using _STD::swap;
243        swap(c, __q.c);
244    }
245
246    template <class _T1, class _C1>
247    friend
248    bool
249    operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
250
251    template <class _T1, class _C1>
252    friend
253    bool
254    operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
255};
256
257template <class _Tp, class _Container>
258inline
259bool
260operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
261{
262    return __x.c == __y.c;
263}
264
265template <class _Tp, class _Container>
266inline
267bool
268operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
269{
270    return __x.c < __y.c;
271}
272
273template <class _Tp, class _Container>
274inline
275bool
276operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
277{
278    return !(__x == __y);
279}
280
281template <class _Tp, class _Container>
282inline
283bool
284operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
285{
286    return __y < __x;
287}
288
289template <class _Tp, class _Container>
290inline
291bool
292operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
293{
294    return !(__x < __y);
295}
296
297template <class _Tp, class _Container>
298inline
299bool
300operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
301{
302    return !(__y < __x);
303}
304
305template <class _Tp, class _Container>
306inline
307void
308swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
309{
310    __x.swap(__y);
311}
312
313template <class _Tp, class _Container, class _Alloc>
314struct uses_allocator<queue<_Tp, _Container>, _Alloc>
315    : public uses_allocator<_Container, _Alloc>
316{
317};
318
319template <class _Tp, class _Container = vector<_Tp>,
320          class _Compare = less<typename _Container::value_type> >
321class priority_queue
322{
323public:
324    typedef _Container                               container_type;
325    typedef _Compare                                 value_compare;
326    typedef typename container_type::value_type      value_type;
327    typedef typename container_type::reference       reference;
328    typedef typename container_type::const_reference const_reference;
329    typedef typename container_type::size_type       size_type;
330
331protected:
332    container_type c;
333    value_compare comp;
334
335public:
336    explicit priority_queue(const value_compare& __comp = value_compare())
337        : c(), comp(__comp) {}
338    priority_queue(const value_compare& __comp, const container_type& __c);
339#ifdef _LIBCPP_MOVE
340    explicit priority_queue(const value_compare& __comp, container_type&& __c);
341#endif
342    template <class _InputIter>
343        priority_queue(_InputIter __f, _InputIter __l,
344                       const value_compare& __comp = value_compare());
345    template <class _InputIter>
346        priority_queue(_InputIter __f, _InputIter __l,
347                       const value_compare& __comp, const container_type& __c);
348#ifdef _LIBCPP_MOVE
349    template <class _InputIter>
350        priority_queue(_InputIter __f, _InputIter __l,
351                       const value_compare& __comp, container_type&& __c);
352    priority_queue(priority_queue&& __q);
353    priority_queue& operator=(priority_queue&& __q);
354#endif
355    template <class _Alloc>
356        explicit priority_queue(const _Alloc& __a,
357                       typename enable_if<uses_allocator<container_type,
358                                                         _Alloc>::value>::type* = 0);
359    template <class _Alloc>
360        priority_queue(const value_compare& __comp, const _Alloc& __a,
361                       typename enable_if<uses_allocator<container_type,
362                                                         _Alloc>::value>::type* = 0);
363    template <class _Alloc>
364        priority_queue(const value_compare& __comp, const container_type& __c,
365                       const _Alloc& __a,
366                       typename enable_if<uses_allocator<container_type,
367                                                         _Alloc>::value>::type* = 0);
368    template <class _Alloc>
369        priority_queue(const priority_queue& __q, const _Alloc& __a,
370                       typename enable_if<uses_allocator<container_type,
371                                                         _Alloc>::value>::type* = 0);
372#ifdef _LIBCPP_MOVE
373    template <class _Alloc>
374        priority_queue(const value_compare& __comp, container_type&& __c,
375                       const _Alloc& __a,
376                       typename enable_if<uses_allocator<container_type,
377                                                         _Alloc>::value>::type* = 0);
378    template <class _Alloc>
379        priority_queue(priority_queue&& __q, const _Alloc& __a,
380                       typename enable_if<uses_allocator<container_type,
381                                                         _Alloc>::value>::type* = 0);
382#endif
383
384    bool            empty() const {return c.empty();}
385    size_type       size() const  {return c.size();}
386    const_reference top() const   {return c.front();}
387
388    void push(const value_type& __v);
389#ifdef _LIBCPP_MOVE
390    void push(value_type&& __v);
391    template <class... _Args> void emplace(_Args&&... __args);
392#endif
393    void pop();
394
395    void swap(priority_queue& __q);
396};
397
398template <class _Tp, class _Container, class _Compare>
399inline
400priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
401                                                          const container_type& __c)
402    : c(__c),
403      comp(__comp)
404{
405    _STD::make_heap(c.begin(), c.end(), comp);
406}
407
408#ifdef _LIBCPP_MOVE
409
410template <class _Tp, class _Container, class _Compare>
411inline
412priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
413                                                          container_type&& __c)
414    : c(_STD::move(__c)),
415      comp(__comp)
416{
417    _STD::make_heap(c.begin(), c.end(), comp);
418}
419
420#endif
421
422template <class _Tp, class _Container, class _Compare>
423template <class _InputIter>
424inline
425priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
426                                                          const value_compare& __comp)
427    : c(__f, __l),
428      comp(__comp)
429{
430    _STD::make_heap(c.begin(), c.end(), comp);
431}
432
433template <class _Tp, class _Container, class _Compare>
434template <class _InputIter>
435inline
436priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
437                                                          const value_compare& __comp,
438                                                          const container_type& __c)
439    : c(__c),
440      comp(__comp)
441{
442    c.insert(c.end(), __f, __l);
443    _STD::make_heap(c.begin(), c.end(), comp);
444}
445
446#ifdef _LIBCPP_MOVE
447
448template <class _Tp, class _Container, class _Compare>
449template <class _InputIter>
450inline
451priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
452                                                          const value_compare& __comp,
453                                                          container_type&& __c)
454    : c(_STD::move(__c)),
455      comp(__comp)
456{
457    c.insert(c.end(), __f, __l);
458    _STD::make_heap(c.begin(), c.end(), comp);
459}
460
461template <class _Tp, class _Container, class _Compare>
462inline
463priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q)
464    : c(_STD::move(__q.c)),
465      comp(_STD::move(__q.comp))
466{
467}
468
469template <class _Tp, class _Container, class _Compare>
470priority_queue<_Tp, _Container, _Compare>&
471priority_queue<_Tp, _Container, _Compare>::operator=(priority_queue&& __q)
472{
473    c = _STD::move(__q.c);
474    comp = _STD::move(__q.comp);
475    return *this;
476}
477
478#endif
479
480template <class _Tp, class _Container, class _Compare>
481template <class _Alloc>
482inline
483priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
484                       typename enable_if<uses_allocator<container_type,
485                                                         _Alloc>::value>::type*)
486    : c(__a)
487{
488}
489
490template <class _Tp, class _Container, class _Compare>
491template <class _Alloc>
492inline
493priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
494                                                          const _Alloc& __a,
495                       typename enable_if<uses_allocator<container_type,
496                                                         _Alloc>::value>::type*)
497    : c(__a),
498      comp(__comp)
499{
500}
501
502template <class _Tp, class _Container, class _Compare>
503template <class _Alloc>
504inline
505priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
506                                                          const container_type& __c,
507                                                          const _Alloc& __a,
508                       typename enable_if<uses_allocator<container_type,
509                                                         _Alloc>::value>::type*)
510    : c(__c, __a),
511      comp(__comp)
512{
513    _STD::make_heap(c.begin(), c.end(), comp);
514}
515
516template <class _Tp, class _Container, class _Compare>
517template <class _Alloc>
518inline
519priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
520                                                          const _Alloc& __a,
521                       typename enable_if<uses_allocator<container_type,
522                                                         _Alloc>::value>::type*)
523    : c(__q.c, __a),
524      comp(__q.comp)
525{
526    _STD::make_heap(c.begin(), c.end(), comp);
527}
528
529#ifdef _LIBCPP_MOVE
530
531template <class _Tp, class _Container, class _Compare>
532template <class _Alloc>
533inline
534priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
535                                                          container_type&& __c,
536                                                          const _Alloc& __a,
537                       typename enable_if<uses_allocator<container_type,
538                                                         _Alloc>::value>::type*)
539    : c(_STD::move(__c), __a),
540      comp(__comp)
541{
542    _STD::make_heap(c.begin(), c.end(), comp);
543}
544
545
546template <class _Tp, class _Container, class _Compare>
547template <class _Alloc>
548inline
549priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
550                                                          const _Alloc& __a,
551                       typename enable_if<uses_allocator<container_type,
552                                                         _Alloc>::value>::type*)
553    : c(_STD::move(__q.c), __a),
554      comp(_STD::move(__q.comp))
555{
556    _STD::make_heap(c.begin(), c.end(), comp);
557}
558
559#endif
560
561template <class _Tp, class _Container, class _Compare>
562inline
563void
564priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
565{
566    c.push_back(__v);
567    _STD::push_heap(c.begin(), c.end(), comp);
568}
569
570#ifdef _LIBCPP_MOVE
571
572template <class _Tp, class _Container, class _Compare>
573inline
574void
575priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
576{
577    c.push_back(_STD::move(__v));
578    _STD::push_heap(c.begin(), c.end(), comp);
579}
580
581template <class _Tp, class _Container, class _Compare>
582template <class... _Args>
583inline
584void
585priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
586{
587    c.emplace_back(_STD::forward<_Args>(__args)...);
588    _STD::push_heap(c.begin(), c.end(), comp);
589}
590
591#endif
592
593template <class _Tp, class _Container, class _Compare>
594inline
595void
596priority_queue<_Tp, _Container, _Compare>::pop()
597{
598    _STD::pop_heap(c.begin(), c.end(), comp);
599    c.pop_back();
600}
601
602template <class _Tp, class _Container, class _Compare>
603inline
604void
605priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
606{
607    using _STD::swap;
608    swap(c, __q.c);
609    swap(comp, __q.comp);
610}
611
612template <class _Tp, class _Container, class _Compare>
613inline
614void
615swap(priority_queue<_Tp, _Container, _Compare>& __x,
616     priority_queue<_Tp, _Container, _Compare>& __y)
617{
618    __x.swap(__y);
619}
620
621template <class _Tp, class _Container, class _Compare, class _Alloc>
622struct uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
623    : public uses_allocator<_Container, _Alloc>
624{
625};
626
627_LIBCPP_END_NAMESPACE_STD
628
629#endif  // _LIBCPP_QUEUE
630