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 @a 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
)
323 * @brief A standard container automatically sorting its contents.
327 * This is not a true container, but an @e adaptor. It holds
328 * another container, and provides a wrapper interface to that
329 * container. The wrapper is what enforces priority-based sorting
330 * and %queue behavior. Very few of the standard container/sequence
331 * interface requirements are met (e.g., iterators).
333 * The second template parameter defines the type of the underlying
334 * sequence/container. It defaults to std::vector, but it can be
335 * any type that supports @c front(), @c push_back, @c pop_back,
336 * and random-access iterators, such as std::deque or an
337 * appropriate user-defined type.
339 * The third template parameter supplies the means of making
340 * priority comparisons. It defaults to @c less<value_type> but
341 * can be anything defining a strict weak ordering.
343 * Members not found in @a normal containers are @c container_type,
344 * which is a typedef for the second Sequence parameter, and @c
345 * push, @c pop, and @c top, which are standard %queue operations.
347 * @note No equality/comparison operators are provided for
350 * @note Sorting of the elements takes place as they are added to,
351 * and removed from, the %priority_queue using the
352 * %priority_queue's member functions. If you access the elements
353 * by other means, and change their data such that the sorting
354 * order would be different, the %priority_queue will not re-sort
355 * the elements for you. (How could it know to do so?)
357 template<typename _Tp
, typename _Sequence
= vector
<_Tp
>,
358 typename _Compare
= less
<typename
_Sequence::value_type
> >
361 // concept requirements
362 typedef typename
_Sequence::value_type _Sequence_value_type
;
363 __glibcxx_class_requires(_Tp
, _SGIAssignableConcept
)
364 __glibcxx_class_requires(_Sequence
, _SequenceConcept
)
365 __glibcxx_class_requires(_Sequence
, _RandomAccessContainerConcept
)
366 __glibcxx_class_requires2(_Tp
, _Sequence_value_type
, _SameTypeConcept
)
367 __glibcxx_class_requires4(_Compare
, bool, _Tp
, _Tp
,
368 _BinaryFunctionConcept
)
371 typedef typename
_Sequence::value_type value_type
;
372 typedef typename
_Sequence::reference reference
;
373 typedef typename
_Sequence::const_reference const_reference
;
374 typedef typename
_Sequence::size_type size_type
;
375 typedef _Sequence container_type
;
378 // See queue::c for notes on these names.
384 * @brief Default constructor creates no elements.
386 #ifndef __GXX_EXPERIMENTAL_CXX0X__
388 priority_queue(const _Compare
& __x
= _Compare(),
389 const _Sequence
& __s
= _Sequence())
391 { std::make_heap(c
.begin(), c
.end(), comp
); }
394 priority_queue(const _Compare
& __x
,
395 const _Sequence
& __s
)
397 { std::make_heap(c
.begin(), c
.end(), comp
); }
400 priority_queue(const _Compare
& __x
= _Compare(),
401 _Sequence
&& __s
= _Sequence())
402 : c(std::move(__s
)), comp(__x
)
403 { std::make_heap(c
.begin(), c
.end(), comp
); }
407 * @brief Builds a %queue from a range.
408 * @param first An input iterator.
409 * @param last An input iterator.
410 * @param x A comparison functor describing a strict weak ordering.
411 * @param s An initial sequence with which to start.
413 * Begins by copying @a s, inserting a copy of the elements
414 * from @a [first,last) into the copy of @a s, then ordering
415 * the copy according to @a x.
417 * For more information on function objects, see the
418 * documentation on @link functors functor base
421 #ifndef __GXX_EXPERIMENTAL_CXX0X__
422 template<typename _InputIterator
>
423 priority_queue(_InputIterator __first
, _InputIterator __last
,
424 const _Compare
& __x
= _Compare(),
425 const _Sequence
& __s
= _Sequence())
428 __glibcxx_requires_valid_range(__first
, __last
);
429 c
.insert(c
.end(), __first
, __last
);
430 std::make_heap(c
.begin(), c
.end(), comp
);
433 template<typename _InputIterator
>
434 priority_queue(_InputIterator __first
, _InputIterator __last
,
436 const _Sequence
& __s
)
439 __glibcxx_requires_valid_range(__first
, __last
);
440 c
.insert(c
.end(), __first
, __last
);
441 std::make_heap(c
.begin(), c
.end(), comp
);
444 template<typename _InputIterator
>
445 priority_queue(_InputIterator __first
, _InputIterator __last
,
446 const _Compare
& __x
= _Compare(),
447 _Sequence
&& __s
= _Sequence())
448 : c(std::move(__s
)), comp(__x
)
450 __glibcxx_requires_valid_range(__first
, __last
);
451 c
.insert(c
.end(), __first
, __last
);
452 std::make_heap(c
.begin(), c
.end(), comp
);
455 priority_queue(priority_queue
&& __pq
)
456 : c(std::move(__pq
.c
)), comp(std::move(__pq
.comp
)) { }
459 operator=(priority_queue
&& __pq
)
461 c
= std::move(__pq
.c
);
462 comp
= std::move(__pq
.comp
);
468 * Returns true if the %queue is empty.
472 { return c
.empty(); }
474 /** Returns the number of elements in the %queue. */
480 * Returns a read-only (constant) reference to the data at the first
481 * element of the %queue.
486 __glibcxx_requires_nonempty();
491 * @brief Add data to the %queue.
492 * @param x Data to be added.
494 * This is a typical %queue operation.
495 * The time complexity of the operation depends on the underlying
499 push(const value_type
& __x
)
502 std::push_heap(c
.begin(), c
.end(), comp
);
505 #ifdef __GXX_EXPERIMENTAL_CXX0X__
507 push(value_type
&& __x
)
509 c
.push_back(std::move(__x
));
510 std::push_heap(c
.begin(), c
.end(), comp
);
513 template<typename
... _Args
>
515 emplace(_Args
&&... __args
)
517 c
.emplace_back(std::forward
<_Args
>(__args
)...);
518 std::push_heap(c
.begin(), c
.end(), comp
);
523 * @brief Removes first element.
525 * This is a typical %queue operation. It shrinks the %queue
526 * by one. The time complexity of the operation depends on the
527 * underlying sequence.
529 * Note that no data is returned, and if the first element's
530 * data is needed, it should be retrieved before pop() is
536 __glibcxx_requires_nonempty();
537 std::pop_heap(c
.begin(), c
.end(), comp
);
541 #ifdef __GXX_EXPERIMENTAL_CXX0X__
543 swap(priority_queue
& __pq
)
547 swap(comp
, __pq
.comp
);
552 // No equality/comparison operators are provided for priority_queue.
554 #ifdef __GXX_EXPERIMENTAL_CXX0X__
555 template<typename _Tp
, typename _Sequence
, typename _Compare
>
557 swap(priority_queue
<_Tp
, _Sequence
, _Compare
>& __x
,
558 priority_queue
<_Tp
, _Sequence
, _Compare
>& __y
)
562 _GLIBCXX_END_NAMESPACE
564 #endif /* _STL_QUEUE_H */