Line data Source code
1 : // Queue implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2018 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 3, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // Under Section 7 of GPL version 3, you are granted additional
17 : // permissions described in the GCC Runtime Library Exception, version
18 : // 3.1, as published by the Free Software Foundation.
19 :
20 : // You should have received a copy of the GNU General Public License and
21 : // a copy of the GCC Runtime Library Exception along with this program;
22 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : // <http://www.gnu.org/licenses/>.
24 :
25 : /*
26 : *
27 : * Copyright (c) 1994
28 : * Hewlett-Packard Company
29 : *
30 : * Permission to use, copy, modify, distribute and sell this software
31 : * and its documentation for any purpose is hereby granted without fee,
32 : * provided that the above copyright notice appear in all copies and
33 : * that both that copyright notice and this permission notice appear
34 : * in supporting documentation. Hewlett-Packard Company makes no
35 : * representations about the suitability of this software for any
36 : * purpose. It is provided "as is" without express or implied warranty.
37 : *
38 : *
39 : * Copyright (c) 1996,1997
40 : * Silicon Graphics Computer Systems, Inc.
41 : *
42 : * Permission to use, copy, modify, distribute and sell this software
43 : * and its documentation for any purpose is hereby granted without fee,
44 : * provided that the above copyright notice appear in all copies and
45 : * that both that copyright notice and this permission notice appear
46 : * in supporting documentation. Silicon Graphics makes no
47 : * representations about the suitability of this software for any
48 : * purpose. It is provided "as is" without express or implied warranty.
49 : */
50 :
51 : /** @file bits/stl_queue.h
52 : * This is an internal header file, included by other library headers.
53 : * Do not attempt to use it directly. @headername{queue}
54 : */
55 :
56 : #ifndef _STL_QUEUE_H
57 : #define _STL_QUEUE_H 1
58 :
59 : #include <bits/concept_check.h>
60 : #include <debug/debug.h>
61 : #if __cplusplus >= 201103L
62 : # include <bits/uses_allocator.h>
63 : #endif
64 :
65 : namespace std _GLIBCXX_VISIBILITY(default)
66 : {
67 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
68 :
69 : /**
70 : * @brief A standard container giving FIFO behavior.
71 : *
72 : * @ingroup sequences
73 : *
74 : * @tparam _Tp Type of element.
75 : * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>.
76 : *
77 : * Meets many of the requirements of a
78 : * <a href="tables.html#65">container</a>,
79 : * but does not define anything to do with iterators. Very few of the
80 : * other standard container interfaces are defined.
81 : *
82 : * This is not a true container, but an @e adaptor. It holds another
83 : * container, and provides a wrapper interface to that container. The
84 : * wrapper is what enforces strict first-in-first-out %queue behavior.
85 : *
86 : * The second template parameter defines the type of the underlying
87 : * sequence/container. It defaults to std::deque, but it can be any type
88 : * that supports @c front, @c back, @c push_back, and @c pop_front,
89 : * such as std::list or an appropriate user-defined type.
90 : *
91 : * Members not found in @a normal containers are @c container_type,
92 : * which is a typedef for the second Sequence parameter, and @c push and
93 : * @c pop, which are standard %queue/FIFO operations.
94 : */
95 : template<typename _Tp, typename _Sequence = deque<_Tp> >
96 : class queue
97 : {
98 : #ifdef _GLIBCXX_CONCEPT_CHECKS
99 : // concept requirements
100 : typedef typename _Sequence::value_type _Sequence_value_type;
101 : # if __cplusplus < 201103L
102 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
103 : # endif
104 : __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
105 : __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
106 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
107 : #endif
108 :
109 : template<typename _Tp1, typename _Seq1>
110 : friend bool
111 : operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
112 :
113 : template<typename _Tp1, typename _Seq1>
114 : friend bool
115 : operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
116 :
117 : #if __cplusplus >= 201103L
118 : template<typename _Alloc>
119 : using _Uses = typename
120 : enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
121 : #endif
122 :
123 : public:
124 : typedef typename _Sequence::value_type value_type;
125 : typedef typename _Sequence::reference reference;
126 : typedef typename _Sequence::const_reference const_reference;
127 : typedef typename _Sequence::size_type size_type;
128 : typedef _Sequence container_type;
129 :
130 : protected:
131 : /* Maintainers wondering why this isn't uglified as per style
132 : * guidelines should note that this name is specified in the standard,
133 : * C++98 [23.2.3.1].
134 : * (Why? Presumably for the same reason that it's protected instead
135 : * of private: to allow derivation. But none of the other
136 : * containers allow for derivation. Odd.)
137 : */
138 : /// @c c is the underlying container.
139 : _Sequence c;
140 :
141 : public:
142 : /**
143 : * @brief Default constructor creates no elements.
144 : */
145 : #if __cplusplus < 201103L
146 : explicit
147 : queue(const _Sequence& __c = _Sequence())
148 : : c(__c) { }
149 : #else
150 : template<typename _Seq = _Sequence, typename _Requires = typename
151 : enable_if<is_default_constructible<_Seq>::value>::type>
152 227 : queue()
153 227 : : c() { }
154 :
155 : explicit
156 : queue(const _Sequence& __c)
157 : : c(__c) { }
158 :
159 : explicit
160 : queue(_Sequence&& __c)
161 : : c(std::move(__c)) { }
162 :
163 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
164 : explicit
165 : queue(const _Alloc& __a)
166 : : c(__a) { }
167 :
168 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
169 : queue(const _Sequence& __c, const _Alloc& __a)
170 : : c(__c, __a) { }
171 :
172 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
173 : queue(_Sequence&& __c, const _Alloc& __a)
174 : : c(std::move(__c), __a) { }
175 :
176 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
177 : queue(const queue& __q, const _Alloc& __a)
178 : : c(__q.c, __a) { }
179 :
180 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
181 : queue(queue&& __q, const _Alloc& __a)
182 : : c(std::move(__q.c), __a) { }
183 : #endif
184 :
185 : /**
186 : * Returns true if the %queue is empty.
187 : */
188 : bool
189 : empty() const
190 : { return c.empty(); }
191 :
192 : /** Returns the number of elements in the %queue. */
193 : size_type
194 454 : size() const
195 454 : { return c.size(); }
196 :
197 : /**
198 : * Returns a read/write reference to the data at the first
199 : * element of the %queue.
200 : */
201 : reference
202 227 : front()
203 : {
204 : __glibcxx_requires_nonempty();
205 227 : return c.front();
206 : }
207 :
208 : /**
209 : * Returns a read-only (constant) reference to the data at the first
210 : * element of the %queue.
211 : */
212 : const_reference
213 : front() const
214 : {
215 : __glibcxx_requires_nonempty();
216 : return c.front();
217 : }
218 :
219 : /**
220 : * Returns a read/write reference to the data at the last
221 : * element of the %queue.
222 : */
223 : reference
224 : back()
225 : {
226 : __glibcxx_requires_nonempty();
227 : return c.back();
228 : }
229 :
230 : /**
231 : * Returns a read-only (constant) reference to the data at the last
232 : * element of the %queue.
233 : */
234 : const_reference
235 : back() const
236 : {
237 : __glibcxx_requires_nonempty();
238 : return c.back();
239 : }
240 :
241 : /**
242 : * @brief Add data to the end of the %queue.
243 : * @param __x Data to be added.
244 : *
245 : * This is a typical %queue operation. The function creates an
246 : * element at the end of the %queue and assigns the given data
247 : * to it. The time complexity of the operation depends on the
248 : * underlying sequence.
249 : */
250 : void
251 0 : push(const value_type& __x)
252 0 : { c.push_back(__x); }
253 :
254 : #if __cplusplus >= 201103L
255 : void
256 227 : push(value_type&& __x)
257 227 : { c.push_back(std::move(__x)); }
258 :
259 : #if __cplusplus > 201402L
260 : template<typename... _Args>
261 : decltype(auto)
262 : emplace(_Args&&... __args)
263 : { return c.emplace_back(std::forward<_Args>(__args)...); }
264 : #else
265 : template<typename... _Args>
266 : void
267 : emplace(_Args&&... __args)
268 : { c.emplace_back(std::forward<_Args>(__args)...); }
269 : #endif
270 : #endif
271 :
272 : /**
273 : * @brief Removes first element.
274 : *
275 : * This is a typical %queue operation. It shrinks the %queue by one.
276 : * The time complexity of the operation depends on the underlying
277 : * sequence.
278 : *
279 : * Note that no data is returned, and if the first element's
280 : * data is needed, it should be retrieved before pop() is
281 : * called.
282 : */
283 : void
284 227 : pop()
285 : {
286 : __glibcxx_requires_nonempty();
287 227 : c.pop_front();
288 227 : }
289 :
290 : #if __cplusplus >= 201103L
291 : void
292 : swap(queue& __q)
293 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
294 : noexcept(__is_nothrow_swappable<_Sequence>::value)
295 : #else
296 : noexcept(__is_nothrow_swappable<_Tp>::value)
297 : #endif
298 : {
299 : using std::swap;
300 : swap(c, __q.c);
301 : }
302 : #endif // __cplusplus >= 201103L
303 : };
304 :
305 : #if __cpp_deduction_guides >= 201606
306 : template<typename _Container,
307 : typename = enable_if_t<!__is_allocator<_Container>::value>>
308 : queue(_Container) -> queue<typename _Container::value_type, _Container>;
309 :
310 : template<typename _Container, typename _Allocator,
311 : typename = enable_if_t<!__is_allocator<_Container>::value>,
312 : typename = enable_if_t<__is_allocator<_Allocator>::value>>
313 : queue(_Container, _Allocator)
314 : -> queue<typename _Container::value_type, _Container>;
315 : #endif
316 :
317 : /**
318 : * @brief Queue equality comparison.
319 : * @param __x A %queue.
320 : * @param __y A %queue of the same type as @a __x.
321 : * @return True iff the size and elements of the queues are equal.
322 : *
323 : * This is an equivalence relation. Complexity and semantics depend on the
324 : * underlying sequence type, but the expected rules are: this relation is
325 : * linear in the size of the sequences, and queues are considered equivalent
326 : * if their sequences compare equal.
327 : */
328 : template<typename _Tp, typename _Seq>
329 : inline bool
330 : operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
331 : { return __x.c == __y.c; }
332 :
333 : /**
334 : * @brief Queue ordering relation.
335 : * @param __x A %queue.
336 : * @param __y A %queue of the same type as @a x.
337 : * @return True iff @a __x is lexicographically less than @a __y.
338 : *
339 : * This is an total ordering relation. Complexity and semantics
340 : * depend on the underlying sequence type, but the expected rules
341 : * are: this relation is linear in the size of the sequences, the
342 : * elements must be comparable with @c <, and
343 : * std::lexicographical_compare() is usually used to make the
344 : * determination.
345 : */
346 : template<typename _Tp, typename _Seq>
347 : inline bool
348 : operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
349 : { return __x.c < __y.c; }
350 :
351 : /// Based on operator==
352 : template<typename _Tp, typename _Seq>
353 : inline bool
354 : operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
355 : { return !(__x == __y); }
356 :
357 : /// Based on operator<
358 : template<typename _Tp, typename _Seq>
359 : inline bool
360 : operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
361 : { return __y < __x; }
362 :
363 : /// Based on operator<
364 : template<typename _Tp, typename _Seq>
365 : inline bool
366 : operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
367 : { return !(__y < __x); }
368 :
369 : /// Based on operator<
370 : template<typename _Tp, typename _Seq>
371 : inline bool
372 : operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
373 : { return !(__x < __y); }
374 :
375 : #if __cplusplus >= 201103L
376 : template<typename _Tp, typename _Seq>
377 : inline
378 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
379 : // Constrained free swap overload, see p0185r1
380 : typename enable_if<__is_swappable<_Seq>::value>::type
381 : #else
382 : void
383 : #endif
384 : swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
385 : noexcept(noexcept(__x.swap(__y)))
386 : { __x.swap(__y); }
387 :
388 : template<typename _Tp, typename _Seq, typename _Alloc>
389 : struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
390 : : public uses_allocator<_Seq, _Alloc>::type { };
391 : #endif // __cplusplus >= 201103L
392 :
393 : /**
394 : * @brief A standard container automatically sorting its contents.
395 : *
396 : * @ingroup sequences
397 : *
398 : * @tparam _Tp Type of element.
399 : * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>.
400 : * @tparam _Compare Comparison function object type, defaults to
401 : * less<_Sequence::value_type>.
402 : *
403 : * This is not a true container, but an @e adaptor. It holds
404 : * another container, and provides a wrapper interface to that
405 : * container. The wrapper is what enforces priority-based sorting
406 : * and %queue behavior. Very few of the standard container/sequence
407 : * interface requirements are met (e.g., iterators).
408 : *
409 : * The second template parameter defines the type of the underlying
410 : * sequence/container. It defaults to std::vector, but it can be
411 : * any type that supports @c front(), @c push_back, @c pop_back,
412 : * and random-access iterators, such as std::deque or an
413 : * appropriate user-defined type.
414 : *
415 : * The third template parameter supplies the means of making
416 : * priority comparisons. It defaults to @c less<value_type> but
417 : * can be anything defining a strict weak ordering.
418 : *
419 : * Members not found in @a normal containers are @c container_type,
420 : * which is a typedef for the second Sequence parameter, and @c
421 : * push, @c pop, and @c top, which are standard %queue operations.
422 : *
423 : * @note No equality/comparison operators are provided for
424 : * %priority_queue.
425 : *
426 : * @note Sorting of the elements takes place as they are added to,
427 : * and removed from, the %priority_queue using the
428 : * %priority_queue's member functions. If you access the elements
429 : * by other means, and change their data such that the sorting
430 : * order would be different, the %priority_queue will not re-sort
431 : * the elements for you. (How could it know to do so?)
432 : */
433 : template<typename _Tp, typename _Sequence = vector<_Tp>,
434 : typename _Compare = less<typename _Sequence::value_type> >
435 : class priority_queue
436 : {
437 : #ifdef _GLIBCXX_CONCEPT_CHECKS
438 : // concept requirements
439 : typedef typename _Sequence::value_type _Sequence_value_type;
440 : # if __cplusplus < 201103L
441 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
442 : # endif
443 : __glibcxx_class_requires(_Sequence, _SequenceConcept)
444 : __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
445 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
446 : __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
447 : _BinaryFunctionConcept)
448 : #endif
449 :
450 : #if __cplusplus >= 201103L
451 : template<typename _Alloc>
452 : using _Uses = typename
453 : enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
454 : #endif
455 :
456 : public:
457 : typedef typename _Sequence::value_type value_type;
458 : typedef typename _Sequence::reference reference;
459 : typedef typename _Sequence::const_reference const_reference;
460 : typedef typename _Sequence::size_type size_type;
461 : typedef _Sequence container_type;
462 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
463 : // DR 2684. priority_queue lacking comparator typedef
464 : typedef _Compare value_compare;
465 :
466 : protected:
467 : // See queue::c for notes on these names.
468 : _Sequence c;
469 : _Compare comp;
470 :
471 : public:
472 : /**
473 : * @brief Default constructor creates no elements.
474 : */
475 : #if __cplusplus < 201103L
476 : explicit
477 : priority_queue(const _Compare& __x = _Compare(),
478 : const _Sequence& __s = _Sequence())
479 : : c(__s), comp(__x)
480 : { std::make_heap(c.begin(), c.end(), comp); }
481 : #else
482 : template<typename _Seq = _Sequence, typename _Requires = typename
483 : enable_if<__and_<is_default_constructible<_Compare>,
484 : is_default_constructible<_Seq>>::value>::type>
485 52 : priority_queue()
486 52 : : c(), comp() { }
487 :
488 : explicit
489 : priority_queue(const _Compare& __x, const _Sequence& __s)
490 : : c(__s), comp(__x)
491 : { std::make_heap(c.begin(), c.end(), comp); }
492 :
493 : explicit
494 : priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
495 : : c(std::move(__s)), comp(__x)
496 : { std::make_heap(c.begin(), c.end(), comp); }
497 :
498 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
499 : explicit
500 : priority_queue(const _Alloc& __a)
501 : : c(__a), comp() { }
502 :
503 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
504 : priority_queue(const _Compare& __x, const _Alloc& __a)
505 : : c(__a), comp(__x) { }
506 :
507 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
508 : // 2537. Constructors [...] taking allocators should call make_heap
509 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
510 : priority_queue(const _Compare& __x, const _Sequence& __c,
511 : const _Alloc& __a)
512 : : c(__c, __a), comp(__x)
513 : { std::make_heap(c.begin(), c.end(), comp); }
514 :
515 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
516 : priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
517 : : c(std::move(__c), __a), comp(__x)
518 : { std::make_heap(c.begin(), c.end(), comp); }
519 :
520 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
521 : priority_queue(const priority_queue& __q, const _Alloc& __a)
522 : : c(__q.c, __a), comp(__q.comp) { }
523 :
524 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
525 : priority_queue(priority_queue&& __q, const _Alloc& __a)
526 : : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
527 : #endif
528 :
529 : /**
530 : * @brief Builds a %queue from a range.
531 : * @param __first An input iterator.
532 : * @param __last An input iterator.
533 : * @param __x A comparison functor describing a strict weak ordering.
534 : * @param __s An initial sequence with which to start.
535 : *
536 : * Begins by copying @a __s, inserting a copy of the elements
537 : * from @a [first,last) into the copy of @a __s, then ordering
538 : * the copy according to @a __x.
539 : *
540 : * For more information on function objects, see the
541 : * documentation on @link functors functor base
542 : * classes@endlink.
543 : */
544 : #if __cplusplus < 201103L
545 : template<typename _InputIterator>
546 : priority_queue(_InputIterator __first, _InputIterator __last,
547 : const _Compare& __x = _Compare(),
548 : const _Sequence& __s = _Sequence())
549 : : c(__s), comp(__x)
550 : {
551 : __glibcxx_requires_valid_range(__first, __last);
552 : c.insert(c.end(), __first, __last);
553 : std::make_heap(c.begin(), c.end(), comp);
554 : }
555 : #else
556 : template<typename _InputIterator>
557 : priority_queue(_InputIterator __first, _InputIterator __last,
558 : const _Compare& __x,
559 : const _Sequence& __s)
560 : : c(__s), comp(__x)
561 : {
562 : __glibcxx_requires_valid_range(__first, __last);
563 : c.insert(c.end(), __first, __last);
564 : std::make_heap(c.begin(), c.end(), comp);
565 : }
566 :
567 : template<typename _InputIterator>
568 : priority_queue(_InputIterator __first, _InputIterator __last,
569 : const _Compare& __x = _Compare(),
570 : _Sequence&& __s = _Sequence())
571 : : c(std::move(__s)), comp(__x)
572 : {
573 : __glibcxx_requires_valid_range(__first, __last);
574 : c.insert(c.end(), __first, __last);
575 : std::make_heap(c.begin(), c.end(), comp);
576 : }
577 : #endif
578 :
579 : /**
580 : * Returns true if the %queue is empty.
581 : */
582 : bool
583 : empty() const
584 : { return c.empty(); }
585 :
586 : /** Returns the number of elements in the %queue. */
587 : size_type
588 1073 : size() const
589 1073 : { return c.size(); }
590 :
591 : /**
592 : * Returns a read-only (constant) reference to the data at the first
593 : * element of the %queue.
594 : */
595 : const_reference
596 1073 : top() const
597 : {
598 : __glibcxx_requires_nonempty();
599 1073 : return c.front();
600 : }
601 :
602 : /**
603 : * @brief Add data to the %queue.
604 : * @param __x Data to be added.
605 : *
606 : * This is a typical %queue operation.
607 : * The time complexity of the operation depends on the underlying
608 : * sequence.
609 : */
610 : void
611 1073 : push(const value_type& __x)
612 : {
613 1073 : c.push_back(__x);
614 1073 : std::push_heap(c.begin(), c.end(), comp);
615 1073 : }
616 :
617 : #if __cplusplus >= 201103L
618 : void
619 : push(value_type&& __x)
620 : {
621 : c.push_back(std::move(__x));
622 : std::push_heap(c.begin(), c.end(), comp);
623 : }
624 :
625 : template<typename... _Args>
626 : void
627 : emplace(_Args&&... __args)
628 : {
629 : c.emplace_back(std::forward<_Args>(__args)...);
630 : std::push_heap(c.begin(), c.end(), comp);
631 : }
632 : #endif
633 :
634 : /**
635 : * @brief Removes first element.
636 : *
637 : * This is a typical %queue operation. It shrinks the %queue
638 : * by one. The time complexity of the operation depends on the
639 : * underlying sequence.
640 : *
641 : * Note that no data is returned, and if the first element's
642 : * data is needed, it should be retrieved before pop() is
643 : * called.
644 : */
645 : void
646 1073 : pop()
647 : {
648 : __glibcxx_requires_nonempty();
649 1073 : std::pop_heap(c.begin(), c.end(), comp);
650 1073 : c.pop_back();
651 1073 : }
652 :
653 : #if __cplusplus >= 201103L
654 : void
655 : swap(priority_queue& __pq)
656 : noexcept(__and_<
657 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
658 : __is_nothrow_swappable<_Sequence>,
659 : #else
660 : __is_nothrow_swappable<_Tp>,
661 : #endif
662 : __is_nothrow_swappable<_Compare>
663 : >::value)
664 : {
665 : using std::swap;
666 : swap(c, __pq.c);
667 : swap(comp, __pq.comp);
668 : }
669 : #endif // __cplusplus >= 201103L
670 : };
671 :
672 : #if __cpp_deduction_guides >= 201606
673 : template<typename _Compare, typename _Container,
674 : typename = enable_if_t<!__is_allocator<_Compare>::value>,
675 : typename = enable_if_t<!__is_allocator<_Container>::value>>
676 : priority_queue(_Compare, _Container)
677 : -> priority_queue<typename _Container::value_type, _Container, _Compare>;
678 :
679 : template<typename _InputIterator, typename _ValT
680 : = typename iterator_traits<_InputIterator>::value_type,
681 : typename _Compare = less<_ValT>,
682 : typename _Container = vector<_ValT>,
683 : typename = _RequireInputIter<_InputIterator>,
684 : typename = enable_if_t<!__is_allocator<_Compare>::value>,
685 : typename = enable_if_t<!__is_allocator<_Container>::value>>
686 : priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
687 : _Container = _Container())
688 : -> priority_queue<_ValT, _Container, _Compare>;
689 :
690 : template<typename _Compare, typename _Container, typename _Allocator,
691 : typename = enable_if_t<!__is_allocator<_Compare>::value>,
692 : typename = enable_if_t<!__is_allocator<_Container>::value>,
693 : typename = enable_if_t<__is_allocator<_Allocator>::value>>
694 : priority_queue(_Compare, _Container, _Allocator)
695 : -> priority_queue<typename _Container::value_type, _Container, _Compare>;
696 : #endif
697 :
698 : // No equality/comparison operators are provided for priority_queue.
699 :
700 : #if __cplusplus >= 201103L
701 : template<typename _Tp, typename _Sequence, typename _Compare>
702 : inline
703 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
704 : // Constrained free swap overload, see p0185r1
705 : typename enable_if<__and_<__is_swappable<_Sequence>,
706 : __is_swappable<_Compare>>::value>::type
707 : #else
708 : void
709 : #endif
710 : swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
711 : priority_queue<_Tp, _Sequence, _Compare>& __y)
712 : noexcept(noexcept(__x.swap(__y)))
713 : { __x.swap(__y); }
714 :
715 : template<typename _Tp, typename _Sequence, typename _Compare,
716 : typename _Alloc>
717 : struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
718 : : public uses_allocator<_Sequence, _Alloc>::type { };
719 : #endif // __cplusplus >= 201103L
720 :
721 : _GLIBCXX_END_NAMESPACE_VERSION
722 : } // namespace
723 :
724 : #endif /* _STL_QUEUE_H */
|
