Branch data Line data Source code
1 : : // Stack implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4 : : // 2010, 2011
5 : : // Free Software Foundation, Inc.
6 : : //
7 : : // This file is part of the GNU ISO C++ Library. This library is free
8 : : // software; you can redistribute it and/or modify it under the
9 : : // terms of the GNU General Public License as published by the
10 : : // Free Software Foundation; either version 3, or (at your option)
11 : : // any later version.
12 : :
13 : : // This library is distributed in the hope that it will be useful,
14 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : : // GNU General Public License for more details.
17 : :
18 : : // Under Section 7 of GPL version 3, you are granted additional
19 : : // permissions described in the GCC Runtime Library Exception, version
20 : : // 3.1, as published by the Free Software Foundation.
21 : :
22 : : // You should have received a copy of the GNU General Public License and
23 : : // a copy of the GCC Runtime Library Exception along with this program;
24 : : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 : : // <http://www.gnu.org/licenses/>.
26 : :
27 : : /*
28 : : *
29 : : * Copyright (c) 1994
30 : : * Hewlett-Packard Company
31 : : *
32 : : * Permission to use, copy, modify, distribute and sell this software
33 : : * and its documentation for any purpose is hereby granted without fee,
34 : : * provided that the above copyright notice appear in all copies and
35 : : * that both that copyright notice and this permission notice appear
36 : : * in supporting documentation. Hewlett-Packard Company makes no
37 : : * representations about the suitability of this software for any
38 : : * purpose. It is provided "as is" without express or implied warranty.
39 : : *
40 : : *
41 : : * Copyright (c) 1996,1997
42 : : * Silicon Graphics Computer Systems, Inc.
43 : : *
44 : : * Permission to use, copy, modify, distribute and sell this software
45 : : * and its documentation for any purpose is hereby granted without fee,
46 : : * provided that the above copyright notice appear in all copies and
47 : : * that both that copyright notice and this permission notice appear
48 : : * in supporting documentation. Silicon Graphics makes no
49 : : * representations about the suitability of this software for any
50 : : * purpose. It is provided "as is" without express or implied warranty.
51 : : */
52 : :
53 : : /** @file bits/stl_stack.h
54 : : * This is an internal header file, included by other library headers.
55 : : * Do not attempt to use it directly. @headername{stack}
56 : : */
57 : :
58 : : #ifndef _STL_STACK_H
59 : : #define _STL_STACK_H 1
60 : :
61 : : #include <bits/concept_check.h>
62 : : #include <debug/debug.h>
63 : :
64 : : namespace std _GLIBCXX_VISIBILITY(default)
65 : : {
66 : : _GLIBCXX_BEGIN_NAMESPACE_VERSION
67 : :
68 : : /**
69 : : * @brief A standard container giving FILO behavior.
70 : : *
71 : : * @ingroup sequences
72 : : *
73 : : * Meets many of the requirements of a
74 : : * <a href="tables.html#65">container</a>,
75 : : * but does not define anything to do with iterators. Very few of the
76 : : * other standard container interfaces are defined.
77 : : *
78 : : * This is not a true container, but an @e adaptor. It holds
79 : : * another container, and provides a wrapper interface to that
80 : : * container. The wrapper is what enforces strict
81 : : * first-in-last-out %stack behavior.
82 : : *
83 : : * The second template parameter defines the type of the underlying
84 : : * sequence/container. It defaults to std::deque, but it can be
85 : : * any type that supports @c back, @c push_back, and @c pop_front,
86 : : * such as std::list, std::vector, or an appropriate user-defined
87 : : * type.
88 : : *
89 : : * Members not found in @a normal containers are @c container_type,
90 : : * which is a typedef for the second Sequence parameter, and @c
91 : : * push, @c pop, and @c top, which are standard %stack/FILO
92 : : * operations.
93 : : */
94 : : template<typename _Tp, typename _Sequence = deque<_Tp> >
95 : 1490737 : class stack
96 : : {
97 : : // concept requirements
98 : : typedef typename _Sequence::value_type _Sequence_value_type;
99 : : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
100 : : __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
101 : : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
102 : :
103 : : template<typename _Tp1, typename _Seq1>
104 : : friend bool
105 : : operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
106 : :
107 : : template<typename _Tp1, typename _Seq1>
108 : : friend bool
109 : : operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
110 : :
111 : : public:
112 : : typedef typename _Sequence::value_type value_type;
113 : : typedef typename _Sequence::reference reference;
114 : : typedef typename _Sequence::const_reference const_reference;
115 : : typedef typename _Sequence::size_type size_type;
116 : : typedef _Sequence container_type;
117 : :
118 : : protected:
119 : : // See queue::c for notes on this name.
120 : : _Sequence c;
121 : :
122 : : public:
123 : : // XXX removed old def ctor, added def arg to this one to match 14882
124 : : /**
125 : : * @brief Default constructor creates no elements.
126 : : */
127 : : #ifndef __GXX_EXPERIMENTAL_CXX0X__
128 : : explicit
129 : 1494391 : stack(const _Sequence& __c = _Sequence())
130 : 1494391 : : c(__c) { }
131 : : #else
132 : : explicit
133 : : stack(const _Sequence& __c)
134 : : : c(__c) { }
135 : :
136 : : explicit
137 : : stack(_Sequence&& __c = _Sequence())
138 : : : c(std::move(__c)) { }
139 : : #endif
140 : :
141 : : /**
142 : : * Returns true if the %stack is empty.
143 : : */
144 : : bool
145 : 41636693 : empty() const
146 : 41636693 : { return c.empty(); }
147 : :
148 : : /** Returns the number of elements in the %stack. */
149 : : size_type
150 : 201702 : size() const
151 : 201702 : { return c.size(); }
152 : :
153 : : /**
154 : : * Returns a read/write reference to the data at the first
155 : : * element of the %stack.
156 : : */
157 : : reference
158 : 40858051 : top()
159 : : {
160 : : __glibcxx_requires_nonempty();
161 : 40858051 : return c.back();
162 : : }
163 : :
164 : : /**
165 : : * Returns a read-only (constant) reference to the data at the first
166 : : * element of the %stack.
167 : : */
168 : : const_reference
169 : : top() const
170 : : {
171 : : __glibcxx_requires_nonempty();
172 : : return c.back();
173 : : }
174 : :
175 : : /**
176 : : * @brief Add data to the top of the %stack.
177 : : * @param __x Data to be added.
178 : : *
179 : : * This is a typical %stack operation. The function creates an
180 : : * element at the top of the %stack and assigns the given data
181 : : * to it. The time complexity of the operation depends on the
182 : : * underlying sequence.
183 : : */
184 : : void
185 : 41473260 : push(const value_type& __x)
186 : 41473260 : { c.push_back(__x); }
187 : :
188 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
189 : : void
190 : : push(value_type&& __x)
191 : : { c.push_back(std::move(__x)); }
192 : :
193 : : template<typename... _Args>
194 : : void
195 : : emplace(_Args&&... __args)
196 : : { c.emplace_back(std::forward<_Args>(__args)...); }
197 : : #endif
198 : :
199 : : /**
200 : : * @brief Removes first element.
201 : : *
202 : : * This is a typical %stack operation. It shrinks the %stack
203 : : * by one. The time complexity of the operation depends on the
204 : : * underlying sequence.
205 : : *
206 : : * Note that no data is returned, and if the first element's
207 : : * data is needed, it should be retrieved before pop() is
208 : : * called.
209 : : */
210 : : void
211 : 41473245 : pop()
212 : : {
213 : : __glibcxx_requires_nonempty();
214 : 41473245 : c.pop_back();
215 : 41473245 : }
216 : :
217 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
218 : : void
219 : : swap(stack& __s)
220 : : noexcept(noexcept(swap(c, __s.c)))
221 : : {
222 : : using std::swap;
223 : : swap(c, __s.c);
224 : : }
225 : : #endif
226 : : };
227 : :
228 : : /**
229 : : * @brief Stack equality comparison.
230 : : * @param __x A %stack.
231 : : * @param __y A %stack of the same type as @a __x.
232 : : * @return True iff the size and elements of the stacks are equal.
233 : : *
234 : : * This is an equivalence relation. Complexity and semantics
235 : : * depend on the underlying sequence type, but the expected rules
236 : : * are: this relation is linear in the size of the sequences, and
237 : : * stacks are considered equivalent if their sequences compare
238 : : * equal.
239 : : */
240 : : template<typename _Tp, typename _Seq>
241 : : inline bool
242 : : operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
243 : : { return __x.c == __y.c; }
244 : :
245 : : /**
246 : : * @brief Stack ordering relation.
247 : : * @param __x A %stack.
248 : : * @param __y A %stack of the same type as @a x.
249 : : * @return True iff @a x is lexicographically less than @a __y.
250 : : *
251 : : * This is an total ordering relation. Complexity and semantics
252 : : * depend on the underlying sequence type, but the expected rules
253 : : * are: this relation is linear in the size of the sequences, the
254 : : * elements must be comparable with @c <, and
255 : : * std::lexicographical_compare() is usually used to make the
256 : : * determination.
257 : : */
258 : : template<typename _Tp, typename _Seq>
259 : : inline bool
260 : : operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
261 : : { return __x.c < __y.c; }
262 : :
263 : : /// Based on operator==
264 : : template<typename _Tp, typename _Seq>
265 : : inline bool
266 : : operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
267 : : { return !(__x == __y); }
268 : :
269 : : /// Based on operator<
270 : : template<typename _Tp, typename _Seq>
271 : : inline bool
272 : : operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
273 : : { return __y < __x; }
274 : :
275 : : /// Based on operator<
276 : : template<typename _Tp, typename _Seq>
277 : : inline bool
278 : : operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
279 : : { return !(__y < __x); }
280 : :
281 : : /// Based on operator<
282 : : template<typename _Tp, typename _Seq>
283 : : inline bool
284 : : operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
285 : : { return !(__x < __y); }
286 : :
287 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
288 : : template<typename _Tp, typename _Seq>
289 : : inline void
290 : : swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
291 : : noexcept(noexcept(__x.swap(__y)))
292 : : { __x.swap(__y); }
293 : :
294 : : template<typename _Tp, typename _Seq, typename _Alloc>
295 : : struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
296 : : : public uses_allocator<_Seq, _Alloc>::type { };
297 : : #endif
298 : :
299 : : _GLIBCXX_END_NAMESPACE_VERSION
300 : : } // namespace
301 : :
302 : : #endif /* _STL_STACK_H */
|
