1 // Queue implementation -*- C++ -*-
3 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
57 #define _STL_QUEUE_H 1
59 #include <bits/concept_check.h>
60 #include <debug/debug.h>
61 #if __cplusplus >= 201103L
62 # include <bits/uses_allocator.h>
65 namespace std
_GLIBCXX_VISIBILITY(default)
67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
70 * @brief A standard container giving FIFO behavior.
74 * @tparam _Tp Type of element.
75 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>.
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.
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.
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.
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.
95 template<typename _Tp
, typename _Sequence
= deque
<_Tp
> >
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
)
105 template<typename _Tp1
, typename _Seq1
>
107 operator==(const queue
<_Tp1
, _Seq1
>&, const queue
<_Tp1
, _Seq1
>&);
109 template<typename _Tp1
, typename _Seq1
>
111 operator<(const queue
<_Tp1
, _Seq1
>&, const queue
<_Tp1
, _Seq1
>&);
114 typedef typename
_Sequence::value_type value_type
;
115 typedef typename
_Sequence::reference reference
;
116 typedef typename
_Sequence::const_reference const_reference
;
117 typedef typename
_Sequence::size_type size_type
;
118 typedef _Sequence container_type
;
122 * 'c' is the underlying container. Maintainers wondering why
123 * this isn't uglified as per style guidelines should note that
124 * this name is specified in the standard, [23.2.3.1]. (Why?
125 * Presumably for the same reason that it's protected instead
126 * of private: to allow derivation. But none of the other
127 * containers allow for derivation. Odd.)
133 * @brief Default constructor creates no elements.
135 #if __cplusplus < 201103L
137 queue(const _Sequence
& __c
= _Sequence())
141 queue(const _Sequence
& __c
)
145 queue(_Sequence
&& __c
= _Sequence())
146 : c(std::move(__c
)) { }
150 * Returns true if the %queue is empty.
154 { return c
.empty(); }
156 /** Returns the number of elements in the %queue. */
162 * Returns a read/write reference to the data at the first
163 * element of the %queue.
168 __glibcxx_requires_nonempty();
173 * Returns a read-only (constant) reference to the data at the first
174 * element of the %queue.
179 __glibcxx_requires_nonempty();
184 * Returns a read/write reference to the data at the last
185 * element of the %queue.
190 __glibcxx_requires_nonempty();
195 * Returns a read-only (constant) reference to the data at the last
196 * element of the %queue.
201 __glibcxx_requires_nonempty();
206 * @brief Add data to the end of the %queue.
207 * @param __x Data to be added.
209 * This is a typical %queue operation. The function creates an
210 * element at the end of the %queue and assigns the given data
211 * to it. The time complexity of the operation depends on the
212 * underlying sequence.
215 push(const value_type
& __x
)
216 { c
.push_back(__x
); }
218 #if __cplusplus >= 201103L
220 push(value_type
&& __x
)
221 { c
.push_back(std::move(__x
)); }
223 template<typename
... _Args
>
225 emplace(_Args
&&... __args
)
226 { c
.emplace_back(std::forward
<_Args
>(__args
)...); }
230 * @brief Removes first element.
232 * This is a typical %queue operation. It shrinks the %queue by one.
233 * The time complexity of the operation depends on the underlying
236 * Note that no data is returned, and if the first element's
237 * data is needed, it should be retrieved before pop() is
243 __glibcxx_requires_nonempty();
247 #if __cplusplus >= 201103L
250 noexcept(noexcept(swap(c
, __q
.c
)))
259 * @brief Queue equality comparison.
260 * @param __x A %queue.
261 * @param __y A %queue of the same type as @a __x.
262 * @return True iff the size and elements of the queues are equal.
264 * This is an equivalence relation. Complexity and semantics depend on the
265 * underlying sequence type, but the expected rules are: this relation is
266 * linear in the size of the sequences, and queues are considered equivalent
267 * if their sequences compare equal.
269 template<typename _Tp
, typename _Seq
>
271 operator==(const queue
<_Tp
, _Seq
>& __x
, const queue
<_Tp
, _Seq
>& __y
)
272 { return __x
.c
== __y
.c
; }
275 * @brief Queue ordering relation.
276 * @param __x A %queue.
277 * @param __y A %queue of the same type as @a x.
278 * @return True iff @a __x is lexicographically less than @a __y.
280 * This is an total ordering relation. Complexity and semantics
281 * depend on the underlying sequence type, but the expected rules
282 * are: this relation is linear in the size of the sequences, the
283 * elements must be comparable with @c <, and
284 * std::lexicographical_compare() is usually used to make the
287 template<typename _Tp
, typename _Seq
>
289 operator<(const queue
<_Tp
, _Seq
>& __x
, const queue
<_Tp
, _Seq
>& __y
)
290 { return __x
.c
< __y
.c
; }
292 /// Based on operator==
293 template<typename _Tp
, typename _Seq
>
295 operator!=(const queue
<_Tp
, _Seq
>& __x
, const queue
<_Tp
, _Seq
>& __y
)
296 { return !(__x
== __y
); }
298 /// Based on operator<
299 template<typename _Tp
, typename _Seq
>
301 operator>(const queue
<_Tp
, _Seq
>& __x
, const queue
<_Tp
, _Seq
>& __y
)
302 { return __y
< __x
; }
304 /// Based on operator<
305 template<typename _Tp
, typename _Seq
>
307 operator<=(const queue
<_Tp
, _Seq
>& __x
, const queue
<_Tp
, _Seq
>& __y
)
308 { return !(__y
< __x
); }
310 /// Based on operator<
311 template<typename _Tp
, typename _Seq
>
313 operator>=(const queue
<_Tp
, _Seq
>& __x
, const queue
<_Tp
, _Seq
>& __y
)
314 { return !(__x
< __y
); }
316 #if __cplusplus >= 201103L
317 template<typename _Tp
, typename _Seq
>
319 swap(queue
<_Tp
, _Seq
>& __x
, queue
<_Tp
, _Seq
>& __y
)
320 noexcept(noexcept(__x
.swap(__y
)))
323 template<typename _Tp
, typename _Seq
, typename _Alloc
>
324 struct uses_allocator
<queue
<_Tp
, _Seq
>, _Alloc
>
325 : public uses_allocator
<_Seq
, _Alloc
>::type
{ };
329 * @brief A standard container automatically sorting its contents.
333 * @tparam _Tp Type of element.
334 * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>.
335 * @tparam _Compare Comparison function object type, defaults to
336 * less<_Sequence::value_type>.
338 * This is not a true container, but an @e adaptor. It holds
339 * another container, and provides a wrapper interface to that
340 * container. The wrapper is what enforces priority-based sorting
341 * and %queue behavior. Very few of the standard container/sequence
342 * interface requirements are met (e.g., iterators).
344 * The second template parameter defines the type of the underlying
345 * sequence/container. It defaults to std::vector, but it can be
346 * any type that supports @c front(), @c push_back, @c pop_back,
347 * and random-access iterators, such as std::deque or an
348 * appropriate user-defined type.
350 * The third template parameter supplies the means of making
351 * priority comparisons. It defaults to @c less<value_type> but
352 * can be anything defining a strict weak ordering.
354 * Members not found in @a normal containers are @c container_type,
355 * which is a typedef for the second Sequence parameter, and @c
356 * push, @c pop, and @c top, which are standard %queue operations.
358 * @note No equality/comparison operators are provided for
361 * @note Sorting of the elements takes place as they are added to,
362 * and removed from, the %priority_queue using the
363 * %priority_queue's member functions. If you access the elements
364 * by other means, and change their data such that the sorting
365 * order would be different, the %priority_queue will not re-sort
366 * the elements for you. (How could it know to do so?)
368 template<typename _Tp
, typename _Sequence
= vector
<_Tp
>,
369 typename _Compare
= less
<typename
_Sequence::value_type
> >
372 // concept requirements
373 typedef typename
_Sequence::value_type _Sequence_value_type
;
374 __glibcxx_class_requires(_Tp
, _SGIAssignableConcept
)
375 __glibcxx_class_requires(_Sequence
, _SequenceConcept
)
376 __glibcxx_class_requires(_Sequence
, _RandomAccessContainerConcept
)
377 __glibcxx_class_requires2(_Tp
, _Sequence_value_type
, _SameTypeConcept
)
378 __glibcxx_class_requires4(_Compare
, bool, _Tp
, _Tp
,
379 _BinaryFunctionConcept
)
382 typedef typename
_Sequence::value_type value_type
;
383 typedef typename
_Sequence::reference reference
;
384 typedef typename
_Sequence::const_reference const_reference
;
385 typedef typename
_Sequence::size_type size_type
;
386 typedef _Sequence container_type
;
389 // See queue::c for notes on these names.
395 * @brief Default constructor creates no elements.
397 #if __cplusplus < 201103L
399 priority_queue(const _Compare
& __x
= _Compare(),
400 const _Sequence
& __s
= _Sequence())
402 { std::make_heap(c
.begin(), c
.end(), comp
); }
405 priority_queue(const _Compare
& __x
,
406 const _Sequence
& __s
)
408 { std::make_heap(c
.begin(), c
.end(), comp
); }
411 priority_queue(const _Compare
& __x
= _Compare(),
412 _Sequence
&& __s
= _Sequence())
413 : c(std::move(__s
)), comp(__x
)
414 { std::make_heap(c
.begin(), c
.end(), comp
); }
418 * @brief Builds a %queue from a range.
419 * @param __first An input iterator.
420 * @param __last An input iterator.
421 * @param __x A comparison functor describing a strict weak ordering.
422 * @param __s An initial sequence with which to start.
424 * Begins by copying @a __s, inserting a copy of the elements
425 * from @a [first,last) into the copy of @a __s, then ordering
426 * the copy according to @a __x.
428 * For more information on function objects, see the
429 * documentation on @link functors functor base
432 #if __cplusplus < 201103L
433 template<typename _InputIterator
>
434 priority_queue(_InputIterator __first
, _InputIterator __last
,
435 const _Compare
& __x
= _Compare(),
436 const _Sequence
& __s
= _Sequence())
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
,
447 const _Sequence
& __s
)
450 __glibcxx_requires_valid_range(__first
, __last
);
451 c
.insert(c
.end(), __first
, __last
);
452 std::make_heap(c
.begin(), c
.end(), comp
);
455 template<typename _InputIterator
>
456 priority_queue(_InputIterator __first
, _InputIterator __last
,
457 const _Compare
& __x
= _Compare(),
458 _Sequence
&& __s
= _Sequence())
459 : c(std::move(__s
)), comp(__x
)
461 __glibcxx_requires_valid_range(__first
, __last
);
462 c
.insert(c
.end(), __first
, __last
);
463 std::make_heap(c
.begin(), c
.end(), 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 #if __cplusplus >= 201103L
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 #if __cplusplus >= 201103L
543 swap(priority_queue
& __pq
)
544 noexcept(noexcept(swap(c
, __pq
.c
)) && noexcept(swap(comp
, __pq
.comp
)))
548 swap(comp
, __pq
.comp
);
553 // No equality/comparison operators are provided for priority_queue.
555 #if __cplusplus >= 201103L
556 template<typename _Tp
, typename _Sequence
, typename _Compare
>
558 swap(priority_queue
<_Tp
, _Sequence
, _Compare
>& __x
,
559 priority_queue
<_Tp
, _Sequence
, _Compare
>& __y
)
560 noexcept(noexcept(__x
.swap(__y
)))
563 template<typename _Tp
, typename _Sequence
, typename _Compare
,
565 struct uses_allocator
<priority_queue
<_Tp
, _Sequence
, _Compare
>, _Alloc
>
566 : public uses_allocator
<_Sequence
, _Alloc
>::type
{ };
569 _GLIBCXX_END_NAMESPACE_VERSION
572 #endif /* _STL_QUEUE_H */