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