1 // Queue implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
29 * Hewlett-Packard Company
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
40 * Copyright (c) 1996,1997
41 * Silicon Graphics Computer Systems, Inc.
43 * Permission to use, copy, modify, distribute and sell this software
44 * and its documentation for any purpose is hereby granted without fee,
45 * provided that the above copyright notice appear in all copies and
46 * that both that copyright notice and this permission notice appear
47 * in supporting documentation. Silicon Graphics makes no
48 * representations about the suitability of this software for any
49 * purpose. It is provided "as is" without express or implied warranty.
53 * This is an internal header file, included by other library headers.
54 * You should not attempt to use it directly.
58 #define _STL_QUEUE_H 1
60 #include <bits/concept_check.h>
61 #include <debug/debug.h>
63 _GLIBCXX_BEGIN_NAMESPACE(std)
66 * @brief A standard container giving FIFO behavior.
70 * Meets many of the requirements of a
71 * <a href="tables.html#65">container</a>,
72 * but does not define anything to do with iterators. Very few of the
73 * other standard container interfaces are defined.
75 * This is not a true container, but an @e adaptor. It holds another
76 * container, and provides a wrapper interface to that container. The
77 * wrapper is what enforces strict first-in-first-out %queue behavior.
79 * The second template parameter defines the type of the underlying
80 * sequence/container. It defaults to std::deque, but it can be any type
81 * that supports @c front, @c back, @c push_back, and @c pop_front,
82 * such as std::list or an appropriate user-defined type.
84 * Members not found in "normal" containers are @c container_type,
85 * which is a typedef for the second Sequence parameter, and @c push and
86 * @c pop, which are standard %queue/FIFO operations.
88 template<typename _Tp, typename _Sequence = deque<_Tp> >
91 // concept requirements
92 typedef typename _Sequence::value_type _Sequence_value_type;
93 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
94 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
95 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
96 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
98 template<typename _Tp1, typename _Seq1>
100 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
102 template<typename _Tp1, typename _Seq1>
104 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
107 typedef typename _Sequence::value_type value_type;
108 typedef typename _Sequence::reference reference;
109 typedef typename _Sequence::const_reference const_reference;
110 typedef typename _Sequence::size_type size_type;
111 typedef _Sequence container_type;
115 * 'c' is the underlying container. Maintainers wondering why
116 * this isn't uglified as per style guidelines should note that
117 * this name is specified in the standard, [23.2.3.1]. (Why?
118 * Presumably for the same reason that it's protected instead
119 * of private: to allow derivation. But none of the other
120 * containers allow for derivation. Odd.)
126 * @brief Default constructor creates no elements.
128 #ifndef __GXX_EXPERIMENTAL_CXX0X__
130 queue(const _Sequence& __c = _Sequence())
134 queue(const _Sequence& __c)
138 queue(_Sequence&& __c = _Sequence())
139 : c(std::move(__c)) { }
142 : c(std::move(__q.c)) { }
145 operator=(queue&& __q)
147 c = std::move(__q.c);
153 * Returns true if the %queue is empty.
157 { return c.empty(); }
159 /** Returns the number of elements in the %queue. */
165 * Returns a read/write reference to the data at the first
166 * element of the %queue.
171 __glibcxx_requires_nonempty();
176 * Returns a read-only (constant) reference to the data at the first
177 * element of the %queue.
182 __glibcxx_requires_nonempty();
187 * Returns a read/write reference to the data at the last
188 * element of the %queue.
193 __glibcxx_requires_nonempty();
198 * Returns a read-only (constant) reference to the data at the last
199 * element of the %queue.
204 __glibcxx_requires_nonempty();
209 * @brief Add data to the end of the %queue.
210 * @param x Data to be added.
212 * This is a typical %queue operation. The function creates an
213 * element at the end of the %queue and assigns the given data
214 * to it. The time complexity of the operation depends on the
215 * underlying sequence.
218 push(const value_type& __x)
219 { c.push_back(__x); }
221 #ifdef __GXX_EXPERIMENTAL_CXX0X__
223 push(value_type&& __x)
224 { c.push_back(std::move(__x)); }
226 template<typename... _Args>
228 emplace(_Args&&... __args)
229 { c.emplace_back(std::forward<_Args>(__args)...); }
233 * @brief Removes first element.
235 * This is a typical %queue operation. It shrinks the %queue by one.
236 * The time complexity of the operation depends on the underlying
239 * Note that no data is returned, and if the first element's
240 * data is needed, it should be retrieved before pop() is
246 __glibcxx_requires_nonempty();
250 #ifdef __GXX_EXPERIMENTAL_CXX0X__
258 * @brief Queue equality comparison.
260 * @param y A %queue of the same type as @a x.
261 * @return True iff the size and elements of the queues are equal.
263 * This is an equivalence relation. Complexity and semantics depend on the
264 * underlying sequence type, but the expected rules are: this relation is
265 * linear in the size of the sequences, and queues are considered equivalent
266 * if their sequences compare equal.
268 template<typename _Tp, typename _Seq>
270 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
271 { return __x.c == __y.c; }
274 * @brief Queue ordering relation.
276 * @param y A %queue of the same type as @a x.
277 * @return True iff @a x is lexicographically less than @a y.
279 * This is an total ordering relation. Complexity and semantics
280 * depend on the underlying sequence type, but the expected rules
281 * are: this relation is linear in the size of the sequences, the
282 * elements must be comparable with @c <, and
283 * std::lexicographical_compare() is usually used to make the
286 template<typename _Tp, typename _Seq>
288 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
289 { return __x.c < __y.c; }
291 /// Based on operator==
292 template<typename _Tp, typename _Seq>
294 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
295 { return !(__x == __y); }
297 /// Based on operator<
298 template<typename _Tp, typename _Seq>
300 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
301 { return __y < __x; }
303 /// Based on operator<
304 template<typename _Tp, typename _Seq>
306 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
307 { return !(__y < __x); }
309 /// Based on operator<
310 template<typename _Tp, typename _Seq>
312 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
313 { return !(__x < __y); }
315 #ifdef __GXX_EXPERIMENTAL_CXX0X__
316 template<typename _Tp, typename _Seq>
318 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
321 template<typename _Tp, typename _Seq>
323 swap(queue<_Tp, _Seq>&& __x, queue<_Tp, _Seq>& __y)
326 template<typename _Tp, typename _Seq>
328 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>&& __y)
333 * @brief A standard container automatically sorting its contents.
337 * This is not a true container, but an @e adaptor. It holds
338 * another container, and provides a wrapper interface to that
339 * container. The wrapper is what enforces priority-based sorting
340 * and %queue behavior. Very few of the standard container/sequence
341 * interface requirements are met (e.g., iterators).
343 * The second template parameter defines the type of the underlying
344 * sequence/container. It defaults to std::vector, but it can be
345 * any type that supports @c front(), @c push_back, @c pop_back,
346 * and random-access iterators, such as std::deque or an
347 * appropriate user-defined type.
349 * The third template parameter supplies the means of making
350 * priority comparisons. It defaults to @c less<value_type> but
351 * can be anything defining a strict weak ordering.
353 * Members not found in "normal" containers are @c container_type,
354 * which is a typedef for the second Sequence parameter, and @c
355 * push, @c pop, and @c top, which are standard %queue operations.
357 * @note No equality/comparison operators are provided for
360 * @note Sorting of the elements takes place as they are added to,
361 * and removed from, the %priority_queue using the
362 * %priority_queue's member functions. If you access the elements
363 * by other means, and change their data such that the sorting
364 * order would be different, the %priority_queue will not re-sort
365 * the elements for you. (How could it know to do so?)
367 template<typename _Tp, typename _Sequence = vector<_Tp>,
368 typename _Compare = less<typename _Sequence::value_type> >
371 // concept requirements
372 typedef typename _Sequence::value_type _Sequence_value_type;
373 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
374 __glibcxx_class_requires(_Sequence, _SequenceConcept)
375 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
376 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
377 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
378 _BinaryFunctionConcept)
381 typedef typename _Sequence::value_type value_type;
382 typedef typename _Sequence::reference reference;
383 typedef typename _Sequence::const_reference const_reference;
384 typedef typename _Sequence::size_type size_type;
385 typedef _Sequence container_type;
388 // See queue::c for notes on these names.
394 * @brief Default constructor creates no elements.
396 #ifndef __GXX_EXPERIMENTAL_CXX0X__
398 priority_queue(const _Compare& __x = _Compare(),
399 const _Sequence& __s = _Sequence())
401 { std::make_heap(c.begin(), c.end(), comp); }
404 priority_queue(const _Compare& __x,
405 const _Sequence& __s)
407 { std::make_heap(c.begin(), c.end(), comp); }
410 priority_queue(const _Compare& __x = _Compare(),
411 _Sequence&& __s = _Sequence())
412 : c(std::move(__s)), comp(__x)
413 { std::make_heap(c.begin(), c.end(), comp); }
417 * @brief Builds a %queue from a range.
418 * @param first An input iterator.
419 * @param last An input iterator.
420 * @param x A comparison functor describing a strict weak ordering.
421 * @param s An initial sequence with which to start.
423 * Begins by copying @a s, inserting a copy of the elements
424 * from @a [first,last) into the copy of @a s, then ordering
425 * the copy according to @a x.
427 * For more information on function objects, see the
428 * documentation on @link functors functor base
431 #ifndef __GXX_EXPERIMENTAL_CXX0X__
432 template<typename _InputIterator>
433 priority_queue(_InputIterator __first, _InputIterator __last,
434 const _Compare& __x = _Compare(),
435 const _Sequence& __s = _Sequence())
438 __glibcxx_requires_valid_range(__first, __last);
439 c.insert(c.end(), __first, __last);
440 std::make_heap(c.begin(), c.end(), comp);
443 template<typename _InputIterator>
444 priority_queue(_InputIterator __first, _InputIterator __last,
446 const _Sequence& __s)
449 __glibcxx_requires_valid_range(__first, __last);
450 c.insert(c.end(), __first, __last);
451 std::make_heap(c.begin(), c.end(), comp);
454 template<typename _InputIterator>
455 priority_queue(_InputIterator __first, _InputIterator __last,
456 const _Compare& __x = _Compare(),
457 _Sequence&& __s = _Sequence())
458 : c(std::move(__s)), comp(__x)
460 __glibcxx_requires_valid_range(__first, __last);
461 c.insert(c.end(), __first, __last);
462 std::make_heap(c.begin(), c.end(), comp);
465 priority_queue(priority_queue&& __pq)
466 : c(std::move(__pq.c)), comp(std::move(__pq.comp)) { }
469 operator=(priority_queue&& __pq)
471 c = std::move(__pq.c);
472 comp = std::move(__pq.comp);
478 * Returns true if the %queue is empty.
482 { return c.empty(); }
484 /** Returns the number of elements in the %queue. */
490 * Returns a read-only (constant) reference to the data at the first
491 * element of the %queue.
496 __glibcxx_requires_nonempty();
501 * @brief Add data to the %queue.
502 * @param x Data to be added.
504 * This is a typical %queue operation.
505 * The time complexity of the operation depends on the underlying
509 push(const value_type& __x)
512 std::push_heap(c.begin(), c.end(), comp);
515 #ifdef __GXX_EXPERIMENTAL_CXX0X__
517 push(value_type&& __x)
519 c.push_back(std::move(__x));
520 std::push_heap(c.begin(), c.end(), comp);
523 template<typename... _Args>
525 emplace(_Args&&... __args)
527 c.emplace_back(std::forward<_Args>(__args)...);
528 std::push_heap(c.begin(), c.end(), comp);
533 * @brief Removes first element.
535 * This is a typical %queue operation. It shrinks the %queue
536 * by one. The time complexity of the operation depends on the
537 * underlying sequence.
539 * Note that no data is returned, and if the first element's
540 * data is needed, it should be retrieved before pop() is
546 __glibcxx_requires_nonempty();
547 std::pop_heap(c.begin(), c.end(), comp);
551 #ifdef __GXX_EXPERIMENTAL_CXX0X__
553 swap(priority_queue&& __pq)
557 swap(comp, __pq.comp);
562 // No equality/comparison operators are provided for priority_queue.
564 #ifdef __GXX_EXPERIMENTAL_CXX0X__
565 template<typename _Tp, typename _Sequence, typename _Compare>
567 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
568 priority_queue<_Tp, _Sequence, _Compare>& __y)
571 template<typename _Tp, typename _Sequence, typename _Compare>
573 swap(priority_queue<_Tp, _Sequence, _Compare>&& __x,
574 priority_queue<_Tp, _Sequence, _Compare>& __y)
577 template<typename _Tp, typename _Sequence, typename _Compare>
579 swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
580 priority_queue<_Tp, _Sequence, _Compare>&& __y)
584 _GLIBCXX_END_NAMESPACE
586 #endif /* _STL_QUEUE_H */