stl_queue.h source code [include/c++/7/bits/stl

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

Clang Project