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