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