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