Line data Source code
1 : // Queue implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2019 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 0 : 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 :
122 : #if __cplusplus >= 201703L
123 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
124 : // 2566. Requirements on the first template parameter of container
125 : // adaptors
126 : static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
127 : "value_type must be the same as the underlying container");
128 : #endif // C++17
129 : #endif // C++11
130 :
131 : public:
132 : typedef typename _Sequence::value_type value_type;
133 : typedef typename _Sequence::reference reference;
134 : typedef typename _Sequence::const_reference const_reference;
135 : typedef typename _Sequence::size_type size_type;
136 : typedef _Sequence container_type;
137 :
138 : protected:
139 : /* Maintainers wondering why this isn't uglified as per style
140 : * guidelines should note that this name is specified in the standard,
141 : * C++98 [23.2.3.1].
142 : * (Why? Presumably for the same reason that it's protected instead
143 : * of private: to allow derivation. But none of the other
144 : * containers allow for derivation. Odd.)
145 : */
146 : /// @c c is the underlying container.
147 : _Sequence c;
148 :
149 : public:
150 : /**
151 : * @brief Default constructor creates no elements.
152 : */
153 : #if __cplusplus < 201103L
154 : explicit
155 : queue(const _Sequence& __c = _Sequence())
156 : : c(__c) { }
157 : #else
158 : template<typename _Seq = _Sequence, typename _Requires = typename
159 : enable_if<is_default_constructible<_Seq>::value>::type>
160 0 : queue()
161 0 : : c() { }
162 :
163 : explicit
164 : queue(const _Sequence& __c)
165 : : c(__c) { }
166 :
167 : explicit
168 : queue(_Sequence&& __c)
169 : : c(std::move(__c)) { }
170 :
171 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
172 : explicit
173 : queue(const _Alloc& __a)
174 : : c(__a) { }
175 :
176 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
177 : queue(const _Sequence& __c, const _Alloc& __a)
178 : : c(__c, __a) { }
179 :
180 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
181 : queue(_Sequence&& __c, const _Alloc& __a)
182 : : c(std::move(__c), __a) { }
183 :
184 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
185 : queue(const queue& __q, const _Alloc& __a)
186 : : c(__q.c, __a) { }
187 :
188 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
189 : queue(queue&& __q, const _Alloc& __a)
190 : : c(std::move(__q.c), __a) { }
191 : #endif
192 :
193 : /**
194 : * Returns true if the %queue is empty.
195 : */
196 : _GLIBCXX_NODISCARD bool
197 0 : empty() const
198 0 : { return c.empty(); }
199 :
200 : /** Returns the number of elements in the %queue. */
201 : size_type
202 : size() const
203 : { return c.size(); }
204 :
205 : /**
206 : * Returns a read/write reference to the data at the first
207 : * element of the %queue.
208 : */
209 : reference
210 0 : front()
211 : {
212 : __glibcxx_requires_nonempty();
213 0 : return c.front();
214 : }
215 :
216 : /**
217 : * Returns a read-only (constant) reference to the data at the first
218 : * element of the %queue.
219 : */
220 : const_reference
221 : front() const
222 : {
223 : __glibcxx_requires_nonempty();
224 : return c.front();
225 : }
226 :
227 : /**
228 : * Returns a read/write reference to the data at the last
229 : * element of the %queue.
230 : */
231 : reference
232 : back()
233 : {
234 : __glibcxx_requires_nonempty();
235 : return c.back();
236 : }
237 :
238 : /**
239 : * Returns a read-only (constant) reference to the data at the last
240 : * element of the %queue.
241 : */
242 : const_reference
243 : back() const
244 : {
245 : __glibcxx_requires_nonempty();
246 : return c.back();
247 : }
248 :
249 : /**
250 : * @brief Add data to the end of the %queue.
251 : * @param __x Data to be added.
252 : *
253 : * This is a typical %queue operation. The function creates an
254 : * element at the end of the %queue and assigns the given data
255 : * to it. The time complexity of the operation depends on the
256 : * underlying sequence.
257 : */
258 : void
259 0 : push(const value_type& __x)
260 0 : { c.push_back(__x); }
261 :
262 : #if __cplusplus >= 201103L
263 : void
264 0 : push(value_type&& __x)
265 0 : { c.push_back(std::move(__x)); }
266 :
267 : #if __cplusplus > 201402L
268 : template<typename... _Args>
269 : decltype(auto)
270 : emplace(_Args&&... __args)
271 : { return c.emplace_back(std::forward<_Args>(__args)...); }
272 : #else
273 : template<typename... _Args>
274 : void
275 : emplace(_Args&&... __args)
276 : { c.emplace_back(std::forward<_Args>(__args)...); }
277 : #endif
278 : #endif
279 :
280 : /**
281 : * @brief Removes first element.
282 : *
283 : * This is a typical %queue operation. It shrinks the %queue by one.
284 : * The time complexity of the operation depends on the underlying
285 : * sequence.
286 : *
287 : * Note that no data is returned, and if the first element's
288 : * data is needed, it should be retrieved before pop() is
289 : * called.
290 : */
291 : void
292 0 : pop()
293 : {
294 : __glibcxx_requires_nonempty();
295 0 : c.pop_front();
296 : }
297 :
298 : #if __cplusplus >= 201103L
299 : void
300 : swap(queue& __q)
301 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
302 : noexcept(__is_nothrow_swappable<_Sequence>::value)
303 : #else
304 : noexcept(__is_nothrow_swappable<_Tp>::value)
305 : #endif
306 : {
307 : using std::swap;
308 : swap(c, __q.c);
309 : }
310 : #endif // __cplusplus >= 201103L
311 : };
312 :
313 : #if __cpp_deduction_guides >= 201606
314 : template<typename _Container,
315 : typename = _RequireNotAllocator<_Container>>
316 : queue(_Container) -> queue<typename _Container::value_type, _Container>;
317 :
318 : template<typename _Container, typename _Allocator,
319 : typename = _RequireNotAllocator<_Container>,
320 : typename = _RequireAllocator<_Allocator>>
321 : queue(_Container, _Allocator)
322 : -> queue<typename _Container::value_type, _Container>;
323 : #endif
324 :
325 : /**
326 : * @brief Queue equality comparison.
327 : * @param __x A %queue.
328 : * @param __y A %queue of the same type as @a __x.
329 : * @return True iff the size and elements of the queues are equal.
330 : *
331 : * This is an equivalence relation. Complexity and semantics depend on the
332 : * underlying sequence type, but the expected rules are: this relation is
333 : * linear in the size of the sequences, and queues are considered equivalent
334 : * if their sequences compare equal.
335 : */
336 : template<typename _Tp, typename _Seq>
337 : inline bool
338 : operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
339 : { return __x.c == __y.c; }
340 :
341 : /**
342 : * @brief Queue ordering relation.
343 : * @param __x A %queue.
344 : * @param __y A %queue of the same type as @a x.
345 : * @return True iff @a __x is lexicographically less than @a __y.
346 : *
347 : * This is an total ordering relation. Complexity and semantics
348 : * depend on the underlying sequence type, but the expected rules
349 : * are: this relation is linear in the size of the sequences, the
350 : * elements must be comparable with @c <, and
351 : * std::lexicographical_compare() is usually used to make the
352 : * determination.
353 : */
354 : template<typename _Tp, typename _Seq>
355 : inline bool
356 : operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
357 : { return __x.c < __y.c; }
358 :
359 : /// Based on operator==
360 : template<typename _Tp, typename _Seq>
361 : inline bool
362 : operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
363 : { return !(__x == __y); }
364 :
365 : /// Based on operator<
366 : template<typename _Tp, typename _Seq>
367 : inline bool
368 : operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
369 : { return __y < __x; }
370 :
371 : /// Based on operator<
372 : template<typename _Tp, typename _Seq>
373 : inline bool
374 : operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
375 : { return !(__y < __x); }
376 :
377 : /// Based on operator<
378 : template<typename _Tp, typename _Seq>
379 : inline bool
380 : operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
381 : { return !(__x < __y); }
382 :
383 : #if __cplusplus >= 201103L
384 : template<typename _Tp, typename _Seq>
385 : inline
386 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
387 : // Constrained free swap overload, see p0185r1
388 : typename enable_if<__is_swappable<_Seq>::value>::type
389 : #else
390 : void
391 : #endif
392 : swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
393 : noexcept(noexcept(__x.swap(__y)))
394 : { __x.swap(__y); }
395 :
396 : template<typename _Tp, typename _Seq, typename _Alloc>
397 : struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
398 : : public uses_allocator<_Seq, _Alloc>::type { };
399 : #endif // __cplusplus >= 201103L
400 :
401 : /**
402 : * @brief A standard container automatically sorting its contents.
403 : *
404 : * @ingroup sequences
405 : *
406 : * @tparam _Tp Type of element.
407 : * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>.
408 : * @tparam _Compare Comparison function object type, defaults to
409 : * less<_Sequence::value_type>.
410 : *
411 : * This is not a true container, but an @e adaptor. It holds
412 : * another container, and provides a wrapper interface to that
413 : * container. The wrapper is what enforces priority-based sorting
414 : * and %queue behavior. Very few of the standard container/sequence
415 : * interface requirements are met (e.g., iterators).
416 : *
417 : * The second template parameter defines the type of the underlying
418 : * sequence/container. It defaults to std::vector, but it can be
419 : * any type that supports @c front(), @c push_back, @c pop_back,
420 : * and random-access iterators, such as std::deque or an
421 : * appropriate user-defined type.
422 : *
423 : * The third template parameter supplies the means of making
424 : * priority comparisons. It defaults to @c less<value_type> but
425 : * can be anything defining a strict weak ordering.
426 : *
427 : * Members not found in @a normal containers are @c container_type,
428 : * which is a typedef for the second Sequence parameter, and @c
429 : * push, @c pop, and @c top, which are standard %queue operations.
430 : *
431 : * @note No equality/comparison operators are provided for
432 : * %priority_queue.
433 : *
434 : * @note Sorting of the elements takes place as they are added to,
435 : * and removed from, the %priority_queue using the
436 : * %priority_queue's member functions. If you access the elements
437 : * by other means, and change their data such that the sorting
438 : * order would be different, the %priority_queue will not re-sort
439 : * the elements for you. (How could it know to do so?)
440 : */
441 : template<typename _Tp, typename _Sequence = vector<_Tp>,
442 : typename _Compare = less<typename _Sequence::value_type> >
443 : class priority_queue
444 : {
445 : #ifdef _GLIBCXX_CONCEPT_CHECKS
446 : // concept requirements
447 : typedef typename _Sequence::value_type _Sequence_value_type;
448 : # if __cplusplus < 201103L
449 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
450 : # endif
451 : __glibcxx_class_requires(_Sequence, _SequenceConcept)
452 : __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
453 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
454 : __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
455 : _BinaryFunctionConcept)
456 : #endif
457 :
458 : #if __cplusplus >= 201103L
459 : template<typename _Alloc>
460 : using _Uses = typename
461 : enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
462 :
463 : #if __cplusplus >= 201703L
464 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
465 : // 2566. Requirements on the first template parameter of container
466 : // adaptors
467 : static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
468 : "value_type must be the same as the underlying container");
469 : #endif // C++17
470 : #endif // C++11
471 :
472 : public:
473 : typedef typename _Sequence::value_type value_type;
474 : typedef typename _Sequence::reference reference;
475 : typedef typename _Sequence::const_reference const_reference;
476 : typedef typename _Sequence::size_type size_type;
477 : typedef _Sequence container_type;
478 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
479 : // DR 2684. priority_queue lacking comparator typedef
480 : typedef _Compare value_compare;
481 :
482 : protected:
483 : // See queue::c for notes on these names.
484 : _Sequence c;
485 : _Compare comp;
486 :
487 : public:
488 : /**
489 : * @brief Default constructor creates no elements.
490 : */
491 : #if __cplusplus < 201103L
492 : explicit
493 : priority_queue(const _Compare& __x = _Compare(),
494 : const _Sequence& __s = _Sequence())
495 : : c(__s), comp(__x)
496 : { std::make_heap(c.begin(), c.end(), comp); }
497 : #else
498 : template<typename _Seq = _Sequence, typename _Requires = typename
499 : enable_if<__and_<is_default_constructible<_Compare>,
500 : is_default_constructible<_Seq>>::value>::type>
501 : priority_queue()
502 : : c(), comp() { }
503 :
504 : explicit
505 : priority_queue(const _Compare& __x, const _Sequence& __s)
506 : : c(__s), comp(__x)
507 : { std::make_heap(c.begin(), c.end(), comp); }
508 :
509 : explicit
510 : priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
511 : : c(std::move(__s)), comp(__x)
512 : { std::make_heap(c.begin(), c.end(), comp); }
513 :
514 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
515 : explicit
516 : priority_queue(const _Alloc& __a)
517 : : c(__a), comp() { }
518 :
519 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
520 : priority_queue(const _Compare& __x, const _Alloc& __a)
521 : : c(__a), comp(__x) { }
522 :
523 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
524 : // 2537. Constructors [...] taking allocators should call make_heap
525 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
526 : priority_queue(const _Compare& __x, const _Sequence& __c,
527 : const _Alloc& __a)
528 : : c(__c, __a), comp(__x)
529 : { std::make_heap(c.begin(), c.end(), comp); }
530 :
531 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
532 : priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
533 : : c(std::move(__c), __a), comp(__x)
534 : { std::make_heap(c.begin(), c.end(), comp); }
535 :
536 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
537 : priority_queue(const priority_queue& __q, const _Alloc& __a)
538 : : c(__q.c, __a), comp(__q.comp) { }
539 :
540 : template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
541 : priority_queue(priority_queue&& __q, const _Alloc& __a)
542 : : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { }
543 : #endif
544 :
545 : /**
546 : * @brief Builds a %queue from a range.
547 : * @param __first An input iterator.
548 : * @param __last An input iterator.
549 : * @param __x A comparison functor describing a strict weak ordering.
550 : * @param __s An initial sequence with which to start.
551 : *
552 : * Begins by copying @a __s, inserting a copy of the elements
553 : * from @a [first,last) into the copy of @a __s, then ordering
554 : * the copy according to @a __x.
555 : *
556 : * For more information on function objects, see the
557 : * documentation on @link functors functor base
558 : * classes@endlink.
559 : */
560 : #if __cplusplus < 201103L
561 : template<typename _InputIterator>
562 : priority_queue(_InputIterator __first, _InputIterator __last,
563 : const _Compare& __x = _Compare(),
564 : const _Sequence& __s = _Sequence())
565 : : c(__s), comp(__x)
566 : {
567 : __glibcxx_requires_valid_range(__first, __last);
568 : c.insert(c.end(), __first, __last);
569 : std::make_heap(c.begin(), c.end(), comp);
570 : }
571 : #else
572 : template<typename _InputIterator>
573 : priority_queue(_InputIterator __first, _InputIterator __last,
574 : const _Compare& __x,
575 : const _Sequence& __s)
576 : : c(__s), comp(__x)
577 : {
578 : __glibcxx_requires_valid_range(__first, __last);
579 : c.insert(c.end(), __first, __last);
580 : std::make_heap(c.begin(), c.end(), comp);
581 : }
582 :
583 : template<typename _InputIterator>
584 : priority_queue(_InputIterator __first, _InputIterator __last,
585 : const _Compare& __x = _Compare(),
586 : _Sequence&& __s = _Sequence())
587 : : c(std::move(__s)), comp(__x)
588 : {
589 : __glibcxx_requires_valid_range(__first, __last);
590 : c.insert(c.end(), __first, __last);
591 : std::make_heap(c.begin(), c.end(), comp);
592 : }
593 : #endif
594 :
595 : /**
596 : * Returns true if the %queue is empty.
597 : */
598 : _GLIBCXX_NODISCARD bool
599 : empty() const
600 : { return c.empty(); }
601 :
602 : /** Returns the number of elements in the %queue. */
603 : size_type
604 : size() const
605 : { return c.size(); }
606 :
607 : /**
608 : * Returns a read-only (constant) reference to the data at the first
609 : * element of the %queue.
610 : */
611 : const_reference
612 : top() const
613 : {
614 : __glibcxx_requires_nonempty();
615 : return c.front();
616 : }
617 :
618 : /**
619 : * @brief Add data to the %queue.
620 : * @param __x Data to be added.
621 : *
622 : * This is a typical %queue operation.
623 : * The time complexity of the operation depends on the underlying
624 : * sequence.
625 : */
626 : void
627 : push(const value_type& __x)
628 : {
629 : c.push_back(__x);
630 : std::push_heap(c.begin(), c.end(), comp);
631 : }
632 :
633 : #if __cplusplus >= 201103L
634 : void
635 : push(value_type&& __x)
636 : {
637 : c.push_back(std::move(__x));
638 : std::push_heap(c.begin(), c.end(), comp);
639 : }
640 :
641 : template<typename... _Args>
642 : void
643 : emplace(_Args&&... __args)
644 : {
645 : c.emplace_back(std::forward<_Args>(__args)...);
646 : std::push_heap(c.begin(), c.end(), comp);
647 : }
648 : #endif
649 :
650 : /**
651 : * @brief Removes first element.
652 : *
653 : * This is a typical %queue operation. It shrinks the %queue
654 : * by one. The time complexity of the operation depends on the
655 : * underlying sequence.
656 : *
657 : * Note that no data is returned, and if the first element's
658 : * data is needed, it should be retrieved before pop() is
659 : * called.
660 : */
661 : void
662 : pop()
663 : {
664 : __glibcxx_requires_nonempty();
665 : std::pop_heap(c.begin(), c.end(), comp);
666 : c.pop_back();
667 : }
668 :
669 : #if __cplusplus >= 201103L
670 : void
671 : swap(priority_queue& __pq)
672 : noexcept(__and_<
673 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
674 : __is_nothrow_swappable<_Sequence>,
675 : #else
676 : __is_nothrow_swappable<_Tp>,
677 : #endif
678 : __is_nothrow_swappable<_Compare>
679 : >::value)
680 : {
681 : using std::swap;
682 : swap(c, __pq.c);
683 : swap(comp, __pq.comp);
684 : }
685 : #endif // __cplusplus >= 201103L
686 : };
687 :
688 : #if __cpp_deduction_guides >= 201606
689 : template<typename _Compare, typename _Container,
690 : typename = _RequireNotAllocator<_Compare>,
691 : typename = _RequireNotAllocator<_Container>>
692 : priority_queue(_Compare, _Container)
693 : -> priority_queue<typename _Container::value_type, _Container, _Compare>;
694 :
695 : template<typename _InputIterator, typename _ValT
696 : = typename iterator_traits<_InputIterator>::value_type,
697 : typename _Compare = less<_ValT>,
698 : typename _Container = vector<_ValT>,
699 : typename = _RequireInputIter<_InputIterator>,
700 : typename = _RequireNotAllocator<_Compare>,
701 : typename = _RequireNotAllocator<_Container>>
702 : priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
703 : _Container = _Container())
704 : -> priority_queue<_ValT, _Container, _Compare>;
705 :
706 : template<typename _Compare, typename _Container, typename _Allocator,
707 : typename = _RequireNotAllocator<_Compare>,
708 : typename = _RequireNotAllocator<_Container>,
709 : typename = _RequireAllocator<_Allocator>>
710 : priority_queue(_Compare, _Container, _Allocator)
711 : -> priority_queue<typename _Container::value_type, _Container, _Compare>;
712 : #endif
713 :
714 : // No equality/comparison operators are provided for priority_queue.
715 :
716 : #if __cplusplus >= 201103L
717 : template<typename _Tp, typename _Sequence, typename _Compare>
718 : inline
719 : #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
720 : // Constrained free swap overload, see p0185r1
721 : typename enable_if<__and_<__is_swappable<_Sequence>,
722 : __is_swappable<_Compare>>::value>::type
723 : #else
724 : void
725 : #endif
726 : swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
727 : priority_queue<_Tp, _Sequence, _Compare>& __y)
728 : noexcept(noexcept(__x.swap(__y)))
729 : { __x.swap(__y); }
730 :
731 : template<typename _Tp, typename _Sequence, typename _Compare,
732 : typename _Alloc>
733 : struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
734 : : public uses_allocator<_Sequence, _Alloc>::type { };
735 : #endif // __cplusplus >= 201103L
736 :
737 : _GLIBCXX_END_NAMESPACE_VERSION
738 : } // namespace
739 :
740 : #endif /* _STL_QUEUE_H */
|
