blob: 01247a29da2b1b22685ffdd3b82f4ff111fa6f09 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===--------------------------- queue ------------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
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:
Howard Hinnant6a094412011-06-04 21:32:33 +000034 queue() = default;
35 ~queue() = default;
36
37 queue(const queue& q) = default;
38 queue(queue&& q) = default;
39
40 queue& operator=(const queue& q) = default;
41 queue& operator=(queue&& q) = default;
42
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000043 explicit queue(const container_type& c);
Howard Hinnant6a094412011-06-04 21:32:33 +000044 explicit queue(container_type&& c)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000045 template <class Alloc>
46 explicit queue(const Alloc& a);
47 template <class Alloc>
48 queue(const container_type& c, const Alloc& a);
49 template <class Alloc>
50 queue(container_type&& c, const Alloc& a);
51 template <class Alloc>
Howard Hinnant6a094412011-06-04 21:32:33 +000052 queue(const queue& q, const Alloc& a);
53 template <class Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000054 queue(queue&& q, const Alloc& a);
55
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000056 bool empty() const;
57 size_type size() const;
58
59 reference front();
60 const_reference front() const;
61 reference back();
62 const_reference back() const;
63
64 void push(const value_type& v);
65 void push(value_type&& v);
Eric Fiselier3816ef92016-07-21 03:20:17 +000066 template <class... Args> reference emplace(Args&&... args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000067 void pop();
68
Eric Fiselier8f1e73d2016-04-21 23:38:59 +000069 void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000070};
71
72template <class T, class Container>
73 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
74
75template <class T, class Container>
76 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
77
78template <class T, class Container>
79 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
80
81template <class T, class Container>
82 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
83
84template <class T, class Container>
85 bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
86
87template <class T, class Container>
88 bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
89
90template <class T, class Container>
Howard Hinnant6a094412011-06-04 21:32:33 +000091 void swap(queue<T, Container>& x, queue<T, Container>& y)
92 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000093
94template <class T, class Container = vector<T>,
95 class Compare = less<typename Container::value_type>>
96class priority_queue
97{
98public:
99 typedef Container container_type;
100 typedef typename container_type::value_type value_type;
101 typedef typename container_type::reference reference;
102 typedef typename container_type::const_reference const_reference;
103 typedef typename container_type::size_type size_type;
104
105protected:
106 container_type c;
107 Compare comp;
108
109public:
Howard Hinnant6a094412011-06-04 21:32:33 +0000110 priority_queue() = default;
111 ~priority_queue() = default;
112
113 priority_queue(const priority_queue& q) = default;
114 priority_queue(priority_queue&& q) = default;
115
116 priority_queue& operator=(const priority_queue& q) = default;
117 priority_queue& operator=(priority_queue&& q) = default;
118
119 explicit priority_queue(const Compare& comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120 priority_queue(const Compare& comp, const container_type& c);
121 explicit priority_queue(const Compare& comp, container_type&& c);
122 template <class InputIterator>
123 priority_queue(InputIterator first, InputIterator last,
124 const Compare& comp = Compare());
125 template <class InputIterator>
126 priority_queue(InputIterator first, InputIterator last,
127 const Compare& comp, const container_type& c);
128 template <class InputIterator>
129 priority_queue(InputIterator first, InputIterator last,
130 const Compare& comp, container_type&& c);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000131 template <class Alloc>
132 explicit priority_queue(const Alloc& a);
133 template <class Alloc>
134 priority_queue(const Compare& comp, const Alloc& a);
135 template <class Alloc>
136 priority_queue(const Compare& comp, const container_type& c,
137 const Alloc& a);
138 template <class Alloc>
139 priority_queue(const Compare& comp, container_type&& c,
140 const Alloc& a);
141 template <class Alloc>
Howard Hinnant6a094412011-06-04 21:32:33 +0000142 priority_queue(const priority_queue& q, const Alloc& a);
143 template <class Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000144 priority_queue(priority_queue&& q, const Alloc& a);
145
146 bool empty() const;
147 size_type size() const;
148 const_reference top() const;
149
150 void push(const value_type& v);
151 void push(value_type&& v);
152 template <class... Args> void emplace(Args&&... args);
153 void pop();
154
Howard Hinnant6a094412011-06-04 21:32:33 +0000155 void swap(priority_queue& q)
Eric Fiselier8f1e73d2016-04-21 23:38:59 +0000156 noexcept(is_nothrow_swappable_v<Container> &&
157 is_nothrow_swappable_v<Comp>)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000158};
159
160template <class T, class Container, class Compare>
161 void swap(priority_queue<T, Container, Compare>& x,
Howard Hinnant6a094412011-06-04 21:32:33 +0000162 priority_queue<T, Container, Compare>& y)
163 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000164
165} // std
166
167*/
168
169#include <__config>
170#include <deque>
171#include <vector>
172#include <functional>
173#include <algorithm>
174
Howard Hinnant08e17472011-10-17 20:05:10 +0000175#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000176#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000177#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000178
179_LIBCPP_BEGIN_NAMESPACE_STD
180
Marshall Clowa46f5ce2015-02-18 17:51:56 +0000181template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TYPE_VIS_ONLY queue;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000182
183template <class _Tp, class _Container>
Howard Hinnant33be35e2012-09-14 00:39:16 +0000184_LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000185bool
186operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
187
188template <class _Tp, class _Container>
Howard Hinnant33be35e2012-09-14 00:39:16 +0000189_LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000190bool
191operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
192
Marshall Clowa46f5ce2015-02-18 17:51:56 +0000193template <class _Tp, class _Container /*= deque<_Tp>*/>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000194class _LIBCPP_TYPE_VIS_ONLY queue
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000195{
196public:
197 typedef _Container container_type;
198 typedef typename container_type::value_type value_type;
199 typedef typename container_type::reference reference;
200 typedef typename container_type::const_reference const_reference;
201 typedef typename container_type::size_type size_type;
Marshall Clowed77ffb2016-03-14 17:58:11 +0000202 static_assert((is_same<_Tp, value_type>::value), "" );
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000203
204protected:
205 container_type c;
206
207public:
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000208 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant6a094412011-06-04 21:32:33 +0000209 queue()
210 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
211 : c() {}
212
213 _LIBCPP_INLINE_VISIBILITY
214 queue(const queue& __q) : c(__q.c) {}
215
216#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
217 _LIBCPP_INLINE_VISIBILITY
218 queue(queue&& __q)
219 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000220 : c(_VSTD::move(__q.c)) {}
Howard Hinnant6a094412011-06-04 21:32:33 +0000221#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
222
223 _LIBCPP_INLINE_VISIBILITY
224 queue& operator=(const queue& __q) {c = __q.c; return *this;}
225
226#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
227 _LIBCPP_INLINE_VISIBILITY
228 queue& operator=(queue&& __q)
229 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000230 {c = _VSTD::move(__q.c); return *this;}
Howard Hinnant6a094412011-06-04 21:32:33 +0000231#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
232
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000233 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000234 explicit queue(const container_type& __c) : c(__c) {}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000235#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000236 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant0949eed2011-06-30 21:18:19 +0000237 explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000238#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000239 template <class _Alloc>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000240 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000241 explicit queue(const _Alloc& __a,
242 typename enable_if<uses_allocator<container_type,
243 _Alloc>::value>::type* = 0)
244 : c(__a) {}
245 template <class _Alloc>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000246 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000247 queue(const queue& __q, const _Alloc& __a,
248 typename enable_if<uses_allocator<container_type,
249 _Alloc>::value>::type* = 0)
250 : c(__q.c, __a) {}
251 template <class _Alloc>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000252 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000253 queue(const container_type& __c, const _Alloc& __a,
254 typename enable_if<uses_allocator<container_type,
255 _Alloc>::value>::type* = 0)
256 : c(__c, __a) {}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000257#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000258 template <class _Alloc>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000259 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000260 queue(container_type&& __c, const _Alloc& __a,
261 typename enable_if<uses_allocator<container_type,
262 _Alloc>::value>::type* = 0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000263 : c(_VSTD::move(__c), __a) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000264 template <class _Alloc>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000265 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000266 queue(queue&& __q, const _Alloc& __a,
267 typename enable_if<uses_allocator<container_type,
268 _Alloc>::value>::type* = 0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000269 : c(_VSTD::move(__q.c), __a) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000270
Howard Hinnant73d21a42010-09-04 23:28:19 +0000271#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000272
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000273 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000274 bool empty() const {return c.empty();}
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000275 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000276 size_type size() const {return c.size();}
277
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000278 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000279 reference front() {return c.front();}
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000280 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000281 const_reference front() const {return c.front();}
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000282 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000283 reference back() {return c.back();}
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000284 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000285 const_reference back() const {return c.back();}
286
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000287 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000288 void push(const value_type& __v) {c.push_back(__v);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000289#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000290 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant0949eed2011-06-30 21:18:19 +0000291 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000292#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000293 template <class... _Args>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000294 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier3816ef92016-07-21 03:20:17 +0000295 reference emplace(_Args&&... __args)
296 { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000297#endif // _LIBCPP_HAS_NO_VARIADICS
298#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000299 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000300 void pop() {c.pop_front();}
301
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000302 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000303 void swap(queue& __q)
Howard Hinnant6a094412011-06-04 21:32:33 +0000304 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000305 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000306 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000307 swap(c, __q.c);
308 }
309
310 template <class _T1, class _C1>
311 friend
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000312 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000313 bool
314 operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
Howard Hinnant324bb032010-08-22 00:02:43 +0000315
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000316 template <class _T1, class _C1>
317 friend
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000318 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000319 bool
320 operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
321};
322
323template <class _Tp, class _Container>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000324inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000325bool
326operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
327{
328 return __x.c == __y.c;
329}
330
331template <class _Tp, class _Container>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000332inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000333bool
334operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
335{
336 return __x.c < __y.c;
337}
338
339template <class _Tp, class _Container>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000340inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000341bool
342operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
343{
344 return !(__x == __y);
345}
346
347template <class _Tp, class _Container>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000348inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000349bool
350operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
351{
352 return __y < __x;
353}
354
355template <class _Tp, class _Container>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000356inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000357bool
358operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
359{
360 return !(__x < __y);
361}
362
363template <class _Tp, class _Container>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000364inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000365bool
366operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
367{
368 return !(__y < __x);
369}
370
371template <class _Tp, class _Container>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000372inline _LIBCPP_INLINE_VISIBILITY
Eric Fiselier8f1e73d2016-04-21 23:38:59 +0000373typename enable_if<
374 __is_swappable<_Container>::value,
375 void
376>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000377swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
Howard Hinnant6a094412011-06-04 21:32:33 +0000378 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000379{
380 __x.swap(__y);
381}
382
383template <class _Tp, class _Container, class _Alloc>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000384struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<queue<_Tp, _Container>, _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000385 : public uses_allocator<_Container, _Alloc>
386{
387};
388
389template <class _Tp, class _Container = vector<_Tp>,
390 class _Compare = less<typename _Container::value_type> >
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000391class _LIBCPP_TYPE_VIS_ONLY priority_queue
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000392{
393public:
394 typedef _Container container_type;
395 typedef _Compare value_compare;
396 typedef typename container_type::value_type value_type;
397 typedef typename container_type::reference reference;
398 typedef typename container_type::const_reference const_reference;
399 typedef typename container_type::size_type size_type;
Marshall Clowed77ffb2016-03-14 17:58:11 +0000400 static_assert((is_same<_Tp, value_type>::value), "" );
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000401
402protected:
403 container_type c;
404 value_compare comp;
405
406public:
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000407 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant6a094412011-06-04 21:32:33 +0000408 priority_queue()
409 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
410 is_nothrow_default_constructible<value_compare>::value)
411 : c(), comp() {}
412
413 _LIBCPP_INLINE_VISIBILITY
414 priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
415
416#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
417 _LIBCPP_INLINE_VISIBILITY
418 priority_queue(priority_queue&& __q)
419 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
420 is_nothrow_move_constructible<value_compare>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000421 : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
Howard Hinnant6a094412011-06-04 21:32:33 +0000422#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
423
424 _LIBCPP_INLINE_VISIBILITY
425 priority_queue& operator=(const priority_queue& __q)
426 {c = __q.c; comp = __q.comp; return *this;}
427
428#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
429 _LIBCPP_INLINE_VISIBILITY
430 priority_queue& operator=(priority_queue&& __q)
431 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
432 is_nothrow_move_assignable<value_compare>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000433 {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
Howard Hinnant6a094412011-06-04 21:32:33 +0000434#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
435
436 _LIBCPP_INLINE_VISIBILITY
437 explicit priority_queue(const value_compare& __comp)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000438 : c(), comp(__comp) {}
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000439 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000440 priority_queue(const value_compare& __comp, const container_type& __c);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000441#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000442 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000443 explicit priority_queue(const value_compare& __comp, container_type&& __c);
444#endif
445 template <class _InputIter>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000446 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000447 priority_queue(_InputIter __f, _InputIter __l,
448 const value_compare& __comp = value_compare());
449 template <class _InputIter>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000450 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000451 priority_queue(_InputIter __f, _InputIter __l,
452 const value_compare& __comp, const container_type& __c);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000453#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000454 template <class _InputIter>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000456 priority_queue(_InputIter __f, _InputIter __l,
457 const value_compare& __comp, container_type&& __c);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000458#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000459 template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000461 explicit priority_queue(const _Alloc& __a,
462 typename enable_if<uses_allocator<container_type,
463 _Alloc>::value>::type* = 0);
464 template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000465 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000466 priority_queue(const value_compare& __comp, const _Alloc& __a,
467 typename enable_if<uses_allocator<container_type,
468 _Alloc>::value>::type* = 0);
469 template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000470 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000471 priority_queue(const value_compare& __comp, const container_type& __c,
472 const _Alloc& __a,
473 typename enable_if<uses_allocator<container_type,
474 _Alloc>::value>::type* = 0);
475 template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000476 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000477 priority_queue(const priority_queue& __q, const _Alloc& __a,
478 typename enable_if<uses_allocator<container_type,
479 _Alloc>::value>::type* = 0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000480#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000481 template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000482 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000483 priority_queue(const value_compare& __comp, container_type&& __c,
484 const _Alloc& __a,
485 typename enable_if<uses_allocator<container_type,
486 _Alloc>::value>::type* = 0);
487 template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000488 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489 priority_queue(priority_queue&& __q, const _Alloc& __a,
490 typename enable_if<uses_allocator<container_type,
491 _Alloc>::value>::type* = 0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000492#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000493
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000494 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000495 bool empty() const {return c.empty();}
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000496 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000497 size_type size() const {return c.size();}
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000498 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000499 const_reference top() const {return c.front();}
500
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000501 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000502 void push(const value_type& __v);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000503#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000504 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000505 void push(value_type&& __v);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000506#ifndef _LIBCPP_HAS_NO_VARIADICS
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000507 template <class... _Args> _LIBCPP_INLINE_VISIBILITY void emplace(_Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000508#endif
509#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000510 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000511 void pop();
512
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000513 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant6a094412011-06-04 21:32:33 +0000514 void swap(priority_queue& __q)
515 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
516 __is_nothrow_swappable<value_compare>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000517};
518
519template <class _Tp, class _Container, class _Compare>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000520inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000521priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
522 const container_type& __c)
523 : c(__c),
524 comp(__comp)
525{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000526 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000527}
528
Howard Hinnant73d21a42010-09-04 23:28:19 +0000529#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000530
531template <class _Tp, class _Container, class _Compare>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000532inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000533priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
534 container_type&& __c)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000535 : c(_VSTD::move(__c)),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000536 comp(__comp)
537{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000538 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000539}
540
Howard Hinnant73d21a42010-09-04 23:28:19 +0000541#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000542
543template <class _Tp, class _Container, class _Compare>
544template <class _InputIter>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000545inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000546priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
547 const value_compare& __comp)
548 : c(__f, __l),
549 comp(__comp)
550{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000551 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000552}
553
554template <class _Tp, class _Container, class _Compare>
555template <class _InputIter>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000556inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000557priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
558 const value_compare& __comp,
559 const container_type& __c)
560 : c(__c),
561 comp(__comp)
562{
563 c.insert(c.end(), __f, __l);
Howard Hinnant0949eed2011-06-30 21:18:19 +0000564 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000565}
566
Howard Hinnant73d21a42010-09-04 23:28:19 +0000567#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000568
569template <class _Tp, class _Container, class _Compare>
570template <class _InputIter>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000571inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000572priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
573 const value_compare& __comp,
574 container_type&& __c)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000575 : c(_VSTD::move(__c)),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000576 comp(__comp)
577{
578 c.insert(c.end(), __f, __l);
Howard Hinnant0949eed2011-06-30 21:18:19 +0000579 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000580}
581
Howard Hinnant73d21a42010-09-04 23:28:19 +0000582#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583
584template <class _Tp, class _Container, class _Compare>
585template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000586inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000587priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
588 typename enable_if<uses_allocator<container_type,
589 _Alloc>::value>::type*)
590 : c(__a)
591{
592}
593
594template <class _Tp, class _Container, class _Compare>
595template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000596inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000597priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
598 const _Alloc& __a,
599 typename enable_if<uses_allocator<container_type,
600 _Alloc>::value>::type*)
601 : c(__a),
602 comp(__comp)
603{
604}
605
606template <class _Tp, class _Container, class _Compare>
607template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000608inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000609priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
610 const container_type& __c,
611 const _Alloc& __a,
612 typename enable_if<uses_allocator<container_type,
613 _Alloc>::value>::type*)
614 : c(__c, __a),
615 comp(__comp)
616{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000617 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000618}
619
620template <class _Tp, class _Container, class _Compare>
621template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000622inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000623priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
624 const _Alloc& __a,
625 typename enable_if<uses_allocator<container_type,
626 _Alloc>::value>::type*)
627 : c(__q.c, __a),
628 comp(__q.comp)
629{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000630 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000631}
632
Howard Hinnant73d21a42010-09-04 23:28:19 +0000633#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000634
635template <class _Tp, class _Container, class _Compare>
636template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000637inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000638priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
639 container_type&& __c,
640 const _Alloc& __a,
641 typename enable_if<uses_allocator<container_type,
642 _Alloc>::value>::type*)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000643 : c(_VSTD::move(__c), __a),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000644 comp(__comp)
645{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000646 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000647}
648
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000649template <class _Tp, class _Container, class _Compare>
650template <class _Alloc>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000651inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000652priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
653 const _Alloc& __a,
654 typename enable_if<uses_allocator<container_type,
655 _Alloc>::value>::type*)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000656 : c(_VSTD::move(__q.c), __a),
657 comp(_VSTD::move(__q.comp))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000658{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000659 _VSTD::make_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000660}
661
Howard Hinnant73d21a42010-09-04 23:28:19 +0000662#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000663
664template <class _Tp, class _Container, class _Compare>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000665inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000666void
667priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
668{
669 c.push_back(__v);
Howard Hinnant0949eed2011-06-30 21:18:19 +0000670 _VSTD::push_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000671}
672
Howard Hinnant73d21a42010-09-04 23:28:19 +0000673#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000674
675template <class _Tp, class _Container, class _Compare>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000676inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000677void
678priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
679{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000680 c.push_back(_VSTD::move(__v));
681 _VSTD::push_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000682}
683
Howard Hinnant73d21a42010-09-04 23:28:19 +0000684#ifndef _LIBCPP_HAS_NO_VARIADICS
685
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000686template <class _Tp, class _Container, class _Compare>
687template <class... _Args>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000688inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000689void
690priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
691{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000692 c.emplace_back(_VSTD::forward<_Args>(__args)...);
693 _VSTD::push_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000694}
695
Howard Hinnant73d21a42010-09-04 23:28:19 +0000696#endif // _LIBCPP_HAS_NO_VARIADICS
697#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000698
699template <class _Tp, class _Container, class _Compare>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000700inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000701void
702priority_queue<_Tp, _Container, _Compare>::pop()
703{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000704 _VSTD::pop_heap(c.begin(), c.end(), comp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000705 c.pop_back();
706}
707
708template <class _Tp, class _Container, class _Compare>
Evgeniy Stepanov9341a8a2016-04-22 01:04:55 +0000709inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000710void
711priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
Howard Hinnant6a094412011-06-04 21:32:33 +0000712 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
713 __is_nothrow_swappable<value_compare>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000714{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000715 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000716 swap(c, __q.c);
717 swap(comp, __q.comp);
718}
719
720template <class _Tp, class _Container, class _Compare>
Howard Hinnantb9af2ea2010-09-22 18:02:38 +0000721inline _LIBCPP_INLINE_VISIBILITY
Eric Fiselier8f1e73d2016-04-21 23:38:59 +0000722typename enable_if<
723 __is_swappable<_Container>::value
724 && __is_swappable<_Compare>::value,
725 void
726>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000727swap(priority_queue<_Tp, _Container, _Compare>& __x,
728 priority_queue<_Tp, _Container, _Compare>& __y)
Howard Hinnant6a094412011-06-04 21:32:33 +0000729 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000730{
731 __x.swap(__y);
732}
733
734template <class _Tp, class _Container, class _Compare, class _Alloc>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000735struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000736 : public uses_allocator<_Container, _Alloc>
737{
738};
739
740_LIBCPP_END_NAMESPACE_STD
741
742#endif // _LIBCPP_QUEUE