xref: /netbsd-src/external/gpl3/gcc/dist/libstdc++-v3/include/bits/stl_stack.h (revision b1e838363e3c6fc78a55519254d99869742dd33c)
1 // Stack implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2022 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_stack.h
52  *  This is an internal header file, included by other library headers.
53  *  Do not attempt to use it directly. @headername{stack}
54  */
55 
56 #ifndef _STL_STACK_H
57 #define _STL_STACK_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 FILO 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
83    *  another container, and provides a wrapper interface to that
84    *  container.  The wrapper is what enforces strict
85    *  first-in-last-out %stack behavior.
86    *
87    *  The second template parameter defines the type of the underlying
88    *  sequence/container.  It defaults to std::deque, but it can be
89    *  any type that supports @c back, @c push_back, and @c pop_back,
90    *  such as std::list, std::vector, or an appropriate user-defined
91    *  type.
92    *
93    *  Members not found in @a normal containers are @c container_type,
94    *  which is a typedef for the second Sequence parameter, and @c
95    *  push, @c pop, and @c top, which are standard %stack/FILO
96    *  operations.
97   */
98   template<typename _Tp, typename _Sequence = deque<_Tp> >
99     class stack
100     {
101 #ifdef _GLIBCXX_CONCEPT_CHECKS
102       // concept requirements
103       typedef typename _Sequence::value_type _Sequence_value_type;
104 # if __cplusplus < 201103L
105       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
106       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
107 # endif
108       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
109 #endif
110 
111       template<typename _Tp1, typename _Seq1>
112 	friend bool
113 	operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
114 
115       template<typename _Tp1, typename _Seq1>
116 	friend bool
117 	operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
118 
119 #if __cpp_lib_three_way_comparison
120       template<typename _Tp1, three_way_comparable _Seq1>
121 	friend compare_three_way_result_t<_Seq1>
122 	operator<=>(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
123 #endif
124 
125 #if __cplusplus >= 201103L
126       template<typename _Alloc>
127 	using _Uses = typename
128 	  enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
129 
130 #if __cplusplus >= 201703L
131       // _GLIBCXX_RESOLVE_LIB_DEFECTS
132       // 2566. Requirements on the first template parameter of container
133       // adaptors
134       static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
135 	  "value_type must be the same as the underlying container");
136 #endif // C++17
137 #endif // C++11
138 
139     public:
140       typedef typename _Sequence::value_type		value_type;
141       typedef typename _Sequence::reference		reference;
142       typedef typename _Sequence::const_reference	const_reference;
143       typedef typename _Sequence::size_type		size_type;
144       typedef	       _Sequence			container_type;
145 
146     protected:
147       //  See queue::c for notes on this name.
148       _Sequence c;
149 
150     public:
151       // XXX removed old def ctor, added def arg to this one to match 14882
152       /**
153        *  @brief  Default constructor creates no elements.
154        */
155 #if __cplusplus < 201103L
156       explicit
157       stack(const _Sequence& __c = _Sequence())
158       : c(__c) { }
159 #else
160       template<typename _Seq = _Sequence, typename _Requires = typename
161 	       enable_if<is_default_constructible<_Seq>::value>::type>
162 	stack()
163 	: c() { }
164 
165       explicit
166       stack(const _Sequence& __c)
167       : c(__c) { }
168 
169       explicit
170       stack(_Sequence&& __c)
171       : c(std::move(__c)) { }
172 
173 #if __cplusplus > 202002L
174 #define __cpp_lib_adaptor_iterator_pair_constructor 202106L
175 
176       template<typename _InputIterator,
177 	       typename = _RequireInputIter<_InputIterator>>
178 	stack(_InputIterator __first, _InputIterator __last)
179 	: c(__first, __last) { }
180 #endif
181 
182 
183       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
184 	explicit
185 	stack(const _Alloc& __a)
186 	: c(__a) { }
187 
188       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
189 	stack(const _Sequence& __c, const _Alloc& __a)
190 	: c(__c, __a) { }
191 
192       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
193 	stack(_Sequence&& __c, const _Alloc& __a)
194 	: c(std::move(__c), __a) { }
195 
196       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
197 	stack(const stack& __q, const _Alloc& __a)
198 	: c(__q.c, __a) { }
199 
200       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
201 	stack(stack&& __q, const _Alloc& __a)
202 	: c(std::move(__q.c), __a) { }
203 
204 #if __cplusplus > 202002L
205       template<typename _InputIterator, typename _Alloc,
206 	       typename = _RequireInputIter<_InputIterator>,
207 	       typename = _Uses<_Alloc>>
208 	stack(_InputIterator __first, _InputIterator __last, const _Alloc& __a)
209 	: c(__first, __last, __a) { }
210 #endif
211 #endif
212 
213       /**
214        *  Returns true if the %stack is empty.
215        */
216       _GLIBCXX_NODISCARD bool
217       empty() const
218       { return c.empty(); }
219 
220       /**  Returns the number of elements in the %stack.  */
221       _GLIBCXX_NODISCARD
222       size_type
223       size() const
224       { return c.size(); }
225 
226       /**
227        *  Returns a read/write reference to the data at the first
228        *  element of the %stack.
229        */
230       _GLIBCXX_NODISCARD
231       reference
232       top()
233       {
234 	__glibcxx_requires_nonempty();
235 	return c.back();
236       }
237 
238       /**
239        *  Returns a read-only (constant) reference to the data at the first
240        *  element of the %stack.
241        */
242       _GLIBCXX_NODISCARD
243       const_reference
244       top() const
245       {
246 	__glibcxx_requires_nonempty();
247 	return c.back();
248       }
249 
250       /**
251        *  @brief  Add data to the top of the %stack.
252        *  @param  __x  Data to be added.
253        *
254        *  This is a typical %stack operation.  The function creates an
255        *  element at the top of the %stack and assigns the given data
256        *  to it.  The time complexity of the operation depends on the
257        *  underlying sequence.
258        */
259       void
260       push(const value_type& __x)
261       { c.push_back(__x); }
262 
263 #if __cplusplus >= 201103L
264       void
265       push(value_type&& __x)
266       { c.push_back(std::move(__x)); }
267 
268 #if __cplusplus > 201402L
269       template<typename... _Args>
270 	decltype(auto)
271 	emplace(_Args&&... __args)
272 	{ return c.emplace_back(std::forward<_Args>(__args)...); }
273 #else
274       template<typename... _Args>
275 	void
276 	emplace(_Args&&... __args)
277 	{ c.emplace_back(std::forward<_Args>(__args)...); }
278 #endif
279 #endif
280 
281       /**
282        *  @brief  Removes first element.
283        *
284        *  This is a typical %stack operation.  It shrinks the %stack
285        *  by one.  The time complexity of the operation depends on the
286        *  underlying sequence.
287        *
288        *  Note that no data is returned, and if the first element's
289        *  data is needed, it should be retrieved before pop() is
290        *  called.
291        */
292       void
293       pop()
294       {
295 	__glibcxx_requires_nonempty();
296 	c.pop_back();
297       }
298 
299 #if __cplusplus >= 201103L
300       void
301       swap(stack& __s)
302 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
303       noexcept(__is_nothrow_swappable<_Sequence>::value)
304 #else
305       noexcept(__is_nothrow_swappable<_Tp>::value)
306 #endif
307       {
308 	using std::swap;
309 	swap(c, __s.c);
310       }
311 #endif // __cplusplus >= 201103L
312     };
313 
314 #if __cpp_deduction_guides >= 201606
315   template<typename _Container,
316 	   typename = _RequireNotAllocator<_Container>>
317     stack(_Container) -> stack<typename _Container::value_type, _Container>;
318 
319   template<typename _Container, typename _Allocator,
320 	   typename = _RequireNotAllocator<_Container>>
321     stack(_Container, _Allocator)
322     -> stack<typename _Container::value_type, _Container>;
323 
324 #ifdef __cpp_lib_adaptor_iterator_pair_constructor
325   template<typename _InputIterator,
326 	   typename _ValT
327 	     = typename iterator_traits<_InputIterator>::value_type,
328 	   typename = _RequireInputIter<_InputIterator>>
329     stack(_InputIterator, _InputIterator) -> stack<_ValT>;
330 
331   template<typename _InputIterator, typename _Allocator,
332 	   typename _ValT
333 	     = typename iterator_traits<_InputIterator>::value_type,
334 	   typename = _RequireInputIter<_InputIterator>,
335 	   typename = _RequireAllocator<_Allocator>>
336     stack(_InputIterator, _InputIterator, _Allocator)
337     -> stack<_ValT, deque<_ValT, _Allocator>>;
338 #endif
339 #endif
340 
341   /**
342    *  @brief  Stack equality comparison.
343    *  @param  __x  A %stack.
344    *  @param  __y  A %stack of the same type as @a __x.
345    *  @return  True iff the size and elements of the stacks are equal.
346    *
347    *  This is an equivalence relation.  Complexity and semantics
348    *  depend on the underlying sequence type, but the expected rules
349    *  are: this relation is linear in the size of the sequences, and
350    *  stacks are considered equivalent if their sequences compare
351    *  equal.
352   */
353   template<typename _Tp, typename _Seq>
354     _GLIBCXX_NODISCARD
355     inline bool
356     operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
357     { return __x.c == __y.c; }
358 
359   /**
360    *  @brief  Stack ordering relation.
361    *  @param  __x  A %stack.
362    *  @param  __y  A %stack of the same type as @a x.
363    *  @return  True iff @a x is lexicographically less than @a __y.
364    *
365    *  This is an total ordering relation.  Complexity and semantics
366    *  depend on the underlying sequence type, but the expected rules
367    *  are: this relation is linear in the size of the sequences, the
368    *  elements must be comparable with @c <, and
369    *  std::lexicographical_compare() is usually used to make the
370    *  determination.
371   */
372   template<typename _Tp, typename _Seq>
373     _GLIBCXX_NODISCARD
374     inline bool
375     operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
376     { return __x.c < __y.c; }
377 
378   /// Based on operator==
379   template<typename _Tp, typename _Seq>
380     _GLIBCXX_NODISCARD
381     inline bool
382     operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
383     { return !(__x == __y); }
384 
385   /// Based on operator<
386   template<typename _Tp, typename _Seq>
387     _GLIBCXX_NODISCARD
388     inline bool
389     operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
390     { return __y < __x; }
391 
392   /// Based on operator<
393   template<typename _Tp, typename _Seq>
394     _GLIBCXX_NODISCARD
395     inline bool
396     operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
397     { return !(__y < __x); }
398 
399   /// Based on operator<
400   template<typename _Tp, typename _Seq>
401     _GLIBCXX_NODISCARD
402     inline bool
403     operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
404     { return !(__x < __y); }
405 
406 #if __cpp_lib_three_way_comparison
407   template<typename _Tp, three_way_comparable _Seq>
408     [[nodiscard]]
409     inline compare_three_way_result_t<_Seq>
410     operator<=>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
411     { return __x.c <=> __y.c; }
412 #endif
413 
414 #if __cplusplus >= 201103L
415   template<typename _Tp, typename _Seq>
416     inline
417 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
418     // Constrained free swap overload, see p0185r1
419     typename enable_if<__is_swappable<_Seq>::value>::type
420 #else
421     void
422 #endif
423     swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
424     noexcept(noexcept(__x.swap(__y)))
425     { __x.swap(__y); }
426 
427   template<typename _Tp, typename _Seq, typename _Alloc>
428     struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
429     : public uses_allocator<_Seq, _Alloc>::type { };
430 #endif // __cplusplus >= 201103L
431 
432 _GLIBCXX_END_NAMESPACE_VERSION
433 } // namespace
434 
435 #endif /* _STL_STACK_H */
436