1// Stack 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_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
65namespace 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 __cplusplus >= 201103L
120 template<typename _Alloc>
121 using _Uses = typename
122 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
123#endif
124
125 public:
126 typedef typename _Sequence::value_type value_type;
127 typedef typename _Sequence::reference reference;
128 typedef typename _Sequence::const_reference const_reference;
129 typedef typename _Sequence::size_type size_type;
130 typedef _Sequence container_type;
131
132 protected:
133 // See queue::c for notes on this name.
134 _Sequence c;
135
136 public:
137 // XXX removed old def ctor, added def arg to this one to match 14882
138 /**
139 * @brief Default constructor creates no elements.
140 */
141#if __cplusplus < 201103L
142 explicit
143 stack(const _Sequence& __c = _Sequence())
144 : c(__c) { }
145#else
146 template<typename _Seq = _Sequence, typename _Requires = typename
147 enable_if<is_default_constructible<_Seq>::value>::type>
148 stack()
149 : c() { }
150
151 explicit
152 stack(const _Sequence& __c)
153 : c(__c) { }
154
155 explicit
156 stack(_Sequence&& __c)
157 : c(std::move(__c)) { }
158
159 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
160 explicit
161 stack(const _Alloc& __a)
162 : c(__a) { }
163
164 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
165 stack(const _Sequence& __c, const _Alloc& __a)
166 : c(__c, __a) { }
167
168 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
169 stack(_Sequence&& __c, const _Alloc& __a)
170 : c(std::move(__c), __a) { }
171
172 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
173 stack(const stack& __q, const _Alloc& __a)
174 : c(__q.c, __a) { }
175
176 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
177 stack(stack&& __q, const _Alloc& __a)
178 : c(std::move(__q.c), __a) { }
179#endif
180
181 /**
182 * Returns true if the %stack is empty.
183 */
184 bool
185 empty() const
186 { return c.empty(); }
187
188 /** Returns the number of elements in the %stack. */
189 size_type
190 size() const
191 { return c.size(); }
192
193 /**
194 * Returns a read/write reference to the data at the first
195 * element of the %stack.
196 */
197 reference
198 top()
199 {
200 __glibcxx_requires_nonempty();
201 return c.back();
202 }
203
204 /**
205 * Returns a read-only (constant) reference to the data at the first
206 * element of the %stack.
207 */
208 const_reference
209 top() const
210 {
211 __glibcxx_requires_nonempty();
212 return c.back();
213 }
214
215 /**
216 * @brief Add data to the top of the %stack.
217 * @param __x Data to be added.
218 *
219 * This is a typical %stack operation. The function creates an
220 * element at the top of the %stack and assigns the given data
221 * to it. The time complexity of the operation depends on the
222 * underlying sequence.
223 */
224 void
225 push(const value_type& __x)
226 { c.push_back(__x); }
227
228#if __cplusplus >= 201103L
229 void
230 push(value_type&& __x)
231 { c.push_back(std::move(__x)); }
232
233#if __cplusplus > 201402L
234 template<typename... _Args>
235 decltype(auto)
236 emplace(_Args&&... __args)
237 { return c.emplace_back(std::forward<_Args>(__args)...); }
238#else
239 template<typename... _Args>
240 void
241 emplace(_Args&&... __args)
242 { c.emplace_back(std::forward<_Args>(__args)...); }
243#endif
244#endif
245
246 /**
247 * @brief Removes first element.
248 *
249 * This is a typical %stack operation. It shrinks the %stack
250 * by one. The time complexity of the operation depends on the
251 * underlying sequence.
252 *
253 * Note that no data is returned, and if the first element's
254 * data is needed, it should be retrieved before pop() is
255 * called.
256 */
257 void
258 pop()
259 {
260 __glibcxx_requires_nonempty();
261 c.pop_back();
262 }
263
264#if __cplusplus >= 201103L
265 void
266 swap(stack& __s)
267#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
268 noexcept(__is_nothrow_swappable<_Sequence>::value)
269#else
270 noexcept(__is_nothrow_swappable<_Tp>::value)
271#endif
272 {
273 using std::swap;
274 swap(c, __s.c);
275 }
276#endif // __cplusplus >= 201103L
277 };
278
279 /**
280 * @brief Stack equality comparison.
281 * @param __x A %stack.
282 * @param __y A %stack of the same type as @a __x.
283 * @return True iff the size and elements of the stacks are equal.
284 *
285 * This is an equivalence relation. Complexity and semantics
286 * depend on the underlying sequence type, but the expected rules
287 * are: this relation is linear in the size of the sequences, and
288 * stacks are considered equivalent if their sequences compare
289 * equal.
290 */
291 template<typename _Tp, typename _Seq>
292 inline bool
293 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
294 { return __x.c == __y.c; }
295
296 /**
297 * @brief Stack ordering relation.
298 * @param __x A %stack.
299 * @param __y A %stack of the same type as @a x.
300 * @return True iff @a x is lexicographically less than @a __y.
301 *
302 * This is an total ordering relation. Complexity and semantics
303 * depend on the underlying sequence type, but the expected rules
304 * are: this relation is linear in the size of the sequences, the
305 * elements must be comparable with @c <, and
306 * std::lexicographical_compare() is usually used to make the
307 * determination.
308 */
309 template<typename _Tp, typename _Seq>
310 inline bool
311 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
312 { return __x.c < __y.c; }
313
314 /// Based on operator==
315 template<typename _Tp, typename _Seq>
316 inline bool
317 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
318 { return !(__x == __y); }
319
320 /// Based on operator<
321 template<typename _Tp, typename _Seq>
322 inline bool
323 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
324 { return __y < __x; }
325
326 /// Based on operator<
327 template<typename _Tp, typename _Seq>
328 inline bool
329 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
330 { return !(__y < __x); }
331
332 /// Based on operator<
333 template<typename _Tp, typename _Seq>
334 inline bool
335 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
336 { return !(__x < __y); }
337
338#if __cplusplus >= 201103L
339 template<typename _Tp, typename _Seq>
340 inline
341#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
342 // Constrained free swap overload, see p0185r1
343 typename enable_if<__is_swappable<_Seq>::value>::type
344#else
345 void
346#endif
347 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
348 noexcept(noexcept(__x.swap(__y)))
349 { __x.swap(__y); }
350
351 template<typename _Tp, typename _Seq, typename _Alloc>
352 struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
353 : public uses_allocator<_Seq, _Alloc>::type { };
354#endif // __cplusplus >= 201103L
355
356_GLIBCXX_END_NAMESPACE_VERSION
357} // namespace
358
359#endif /* _STL_STACK_H */
360