1 // Stack implementation -*- C++ -*-
2
3 // Copyright (C) 2001-2020 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 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
174 explicit
175 stack(const _Alloc& __a)
176 : c(__a) { }
177
178 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
179 stack(const _Sequence& __c, const _Alloc& __a)
180 : c(__c, __a) { }
181
182 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
183 stack(_Sequence&& __c, const _Alloc& __a)
184 : c(std::move(__c), __a) { }
185
186 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
187 stack(const stack& __q, const _Alloc& __a)
188 : c(__q.c, __a) { }
189
190 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
191 stack(stack&& __q, const _Alloc& __a)
192 : c(std::move(__q.c), __a) { }
193 #endif
194
195 /**
196 * Returns true if the %stack is empty.
197 */
198 _GLIBCXX_NODISCARD bool
199 empty() const
200 { return c.empty(); }
201
202 /** Returns the number of elements in the %stack. */
203 size_type
204 size() const
205 { return c.size(); }
206
207 /**
208 * Returns a read/write reference to the data at the first
209 * element of the %stack.
210 */
211 reference
212 top()
213 {
214 __glibcxx_requires_nonempty();
215 return c.back();
216 }
217
218 /**
219 * Returns a read-only (constant) reference to the data at the first
220 * element of the %stack.
221 */
222 const_reference
223 top() const
224 {
225 __glibcxx_requires_nonempty();
226 return c.back();
227 }
228
229 /**
230 * @brief Add data to the top of the %stack.
231 * @param __x Data to be added.
232 *
233 * This is a typical %stack operation. The function creates an
234 * element at the top of the %stack and assigns the given data
235 * to it. The time complexity of the operation depends on the
236 * underlying sequence.
237 */
238 void
239 push(const value_type& __x)
240 { c.push_back(__x); }
241
242 #if __cplusplus >= 201103L
243 void
244 push(value_type&& __x)
245 { c.push_back(std::move(__x)); }
246
247 #if __cplusplus > 201402L
248 template<typename... _Args>
249 decltype(auto)
250 emplace(_Args&&... __args)
251 { return c.emplace_back(std::forward<_Args>(__args)...); }
252 #else
253 template<typename... _Args>
254 void
255 emplace(_Args&&... __args)
256 { c.emplace_back(std::forward<_Args>(__args)...); }
257 #endif
258 #endif
259
260 /**
261 * @brief Removes first element.
262 *
263 * This is a typical %stack operation. It shrinks the %stack
264 * by one. The time complexity of the operation depends on the
265 * underlying sequence.
266 *
267 * Note that no data is returned, and if the first element's
268 * data is needed, it should be retrieved before pop() is
269 * called.
270 */
271 void
272 pop()
273 {
274 __glibcxx_requires_nonempty();
275 c.pop_back();
276 }
277
278 #if __cplusplus >= 201103L
279 void
280 swap(stack& __s)
281 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
282 noexcept(__is_nothrow_swappable<_Sequence>::value)
283 #else
284 noexcept(__is_nothrow_swappable<_Tp>::value)
285 #endif
286 {
287 using std::swap;
288 swap(c, __s.c);
289 }
290 #endif // __cplusplus >= 201103L
291 };
292
293 #if __cpp_deduction_guides >= 201606
294 template<typename _Container,
295 typename = _RequireNotAllocator<_Container>>
296 stack(_Container) -> stack<typename _Container::value_type, _Container>;
297
298 template<typename _Container, typename _Allocator,
299 typename = _RequireNotAllocator<_Container>,
300 typename = _RequireAllocator<_Allocator>>
301 stack(_Container, _Allocator)
302 -> stack<typename _Container::value_type, _Container>;
303 #endif
304
305 /**
306 * @brief Stack equality comparison.
307 * @param __x A %stack.
308 * @param __y A %stack of the same type as @a __x.
309 * @return True iff the size and elements of the stacks are equal.
310 *
311 * This is an equivalence relation. Complexity and semantics
312 * depend on the underlying sequence type, but the expected rules
313 * are: this relation is linear in the size of the sequences, and
314 * stacks are considered equivalent if their sequences compare
315 * equal.
316 */
317 template<typename _Tp, typename _Seq>
318 inline bool
319 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
320 { return __x.c == __y.c; }
321
322 /**
323 * @brief Stack ordering relation.
324 * @param __x A %stack.
325 * @param __y A %stack of the same type as @a x.
326 * @return True iff @a x is lexicographically less than @a __y.
327 *
328 * This is an total ordering relation. Complexity and semantics
329 * depend on the underlying sequence type, but the expected rules
330 * are: this relation is linear in the size of the sequences, the
331 * elements must be comparable with @c <, and
332 * std::lexicographical_compare() is usually used to make the
333 * determination.
334 */
335 template<typename _Tp, typename _Seq>
336 inline bool
337 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
338 { return __x.c < __y.c; }
339
340 /// Based on operator==
341 template<typename _Tp, typename _Seq>
342 inline bool
343 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
344 { return !(__x == __y); }
345
346 /// Based on operator<
347 template<typename _Tp, typename _Seq>
348 inline bool
349 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
350 { return __y < __x; }
351
352 /// Based on operator<
353 template<typename _Tp, typename _Seq>
354 inline bool
355 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
356 { return !(__y < __x); }
357
358 /// Based on operator<
359 template<typename _Tp, typename _Seq>
360 inline bool
361 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
362 { return !(__x < __y); }
363
364 #if __cpp_lib_three_way_comparison
365 template<typename _Tp, three_way_comparable _Seq>
366 inline compare_three_way_result_t<_Seq>
367 operator<=>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
368 { return __x.c <=> __y.c; }
369 #endif
370
371 #if __cplusplus >= 201103L
372 template<typename _Tp, typename _Seq>
373 inline
374 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
375 // Constrained free swap overload, see p0185r1
376 typename enable_if<__is_swappable<_Seq>::value>::type
377 #else
378 void
379 #endif
380 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
381 noexcept(noexcept(__x.swap(__y)))
382 { __x.swap(__y); }
383
384 template<typename _Tp, typename _Seq, typename _Alloc>
385 struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
386 : public uses_allocator<_Seq, _Alloc>::type { };
387 #endif // __cplusplus >= 201103L
388
389 _GLIBCXX_END_NAMESPACE_VERSION
390 } // namespace
391
392 #endif /* _STL_STACK_H */
393