1 // Stack implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
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 3, or (at your option)
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.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
29 * Hewlett-Packard Company
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
40 * Copyright (c) 1996,1997
41 * Silicon Graphics Computer Systems, Inc.
43 * Permission to use, copy, modify, distribute and sell this software
44 * and its documentation for any purpose is hereby granted without fee,
45 * provided that the above copyright notice appear in all copies and
46 * that both that copyright notice and this permission notice appear
47 * in supporting documentation. Silicon Graphics makes no
48 * representations about the suitability of this software for any
49 * purpose. It is provided "as is" without express or implied warranty.
53 * This is an internal header file, included by other library headers.
54 * You should not attempt to use it directly.
58 #define _STL_STACK_H 1
60 #include <bits/concept_check.h>
61 #include <debug/debug.h>
63 _GLIBCXX_BEGIN_NAMESPACE(std
)
66 * @brief A standard container giving FILO behavior.
70 * Meets many of the requirements of a
71 * <a href="tables.html#65">container</a>,
72 * but does not define anything to do with iterators. Very few of the
73 * other standard container interfaces are defined.
75 * This is not a true container, but an @e adaptor. It holds
76 * another container, and provides a wrapper interface to that
77 * container. The wrapper is what enforces strict
78 * first-in-last-out %stack behavior.
80 * The second template parameter defines the type of the underlying
81 * sequence/container. It defaults to std::deque, but it can be
82 * any type that supports @c back, @c push_back, and @c pop_front,
83 * such as std::list, std::vector, or an appropriate user-defined
86 * Members not found in @a normal containers are @c container_type,
87 * which is a typedef for the second Sequence parameter, and @c
88 * push, @c pop, and @c top, which are standard %stack/FILO
91 template<typename _Tp
, typename _Sequence
= deque
<_Tp
> >
94 // concept requirements
95 typedef typename
_Sequence::value_type _Sequence_value_type
;
96 __glibcxx_class_requires(_Tp
, _SGIAssignableConcept
)
97 __glibcxx_class_requires(_Sequence
, _BackInsertionSequenceConcept
)
98 __glibcxx_class_requires2(_Tp
, _Sequence_value_type
, _SameTypeConcept
)
100 template<typename _Tp1
, typename _Seq1
>
102 operator==(const stack
<_Tp1
, _Seq1
>&, const stack
<_Tp1
, _Seq1
>&);
104 template<typename _Tp1
, typename _Seq1
>
106 operator<(const stack
<_Tp1
, _Seq1
>&, const stack
<_Tp1
, _Seq1
>&);
109 typedef typename
_Sequence::value_type value_type
;
110 typedef typename
_Sequence::reference reference
;
111 typedef typename
_Sequence::const_reference const_reference
;
112 typedef typename
_Sequence::size_type size_type
;
113 typedef _Sequence container_type
;
116 // See queue::c for notes on this name.
120 // XXX removed old def ctor, added def arg to this one to match 14882
122 * @brief Default constructor creates no elements.
124 #ifndef __GXX_EXPERIMENTAL_CXX0X__
126 stack(const _Sequence
& __c
= _Sequence())
130 stack(const _Sequence
& __c
)
134 stack(_Sequence
&& __c
= _Sequence())
135 : c(std::move(__c
)) { }
139 * Returns true if the %stack is empty.
143 { return c
.empty(); }
145 /** Returns the number of elements in the %stack. */
151 * Returns a read/write reference to the data at the first
152 * element of the %stack.
157 __glibcxx_requires_nonempty();
162 * Returns a read-only (constant) reference to the data at the first
163 * element of the %stack.
168 __glibcxx_requires_nonempty();
173 * @brief Add data to the top of the %stack.
174 * @param x Data to be added.
176 * This is a typical %stack operation. The function creates an
177 * element at the top of the %stack and assigns the given data
178 * to it. The time complexity of the operation depends on the
179 * underlying sequence.
182 push(const value_type
& __x
)
183 { c
.push_back(__x
); }
185 #ifdef __GXX_EXPERIMENTAL_CXX0X__
187 push(value_type
&& __x
)
188 { c
.push_back(std::move(__x
)); }
190 template<typename
... _Args
>
192 emplace(_Args
&&... __args
)
193 { c
.emplace_back(std::forward
<_Args
>(__args
)...); }
197 * @brief Removes first element.
199 * This is a typical %stack operation. It shrinks the %stack
200 * by one. The time complexity of the operation depends on the
201 * underlying sequence.
203 * Note that no data is returned, and if the first element's
204 * data is needed, it should be retrieved before pop() is
210 __glibcxx_requires_nonempty();
214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
222 * @brief Stack equality comparison.
224 * @param y A %stack of the same type as @a x.
225 * @return True iff the size and elements of the stacks are equal.
227 * This is an equivalence relation. Complexity and semantics
228 * depend on the underlying sequence type, but the expected rules
229 * are: this relation is linear in the size of the sequences, and
230 * stacks are considered equivalent if their sequences compare
233 template<typename _Tp
, typename _Seq
>
235 operator==(const stack
<_Tp
, _Seq
>& __x
, const stack
<_Tp
, _Seq
>& __y
)
236 { return __x
.c
== __y
.c
; }
239 * @brief Stack ordering relation.
241 * @param y A %stack of the same type as @a x.
242 * @return True iff @a x is lexicographically less than @a y.
244 * This is an total ordering relation. Complexity and semantics
245 * depend on the underlying sequence type, but the expected rules
246 * are: this relation is linear in the size of the sequences, the
247 * elements must be comparable with @c <, and
248 * std::lexicographical_compare() is usually used to make the
251 template<typename _Tp
, typename _Seq
>
253 operator<(const stack
<_Tp
, _Seq
>& __x
, const stack
<_Tp
, _Seq
>& __y
)
254 { return __x
.c
< __y
.c
; }
256 /// Based on operator==
257 template<typename _Tp
, typename _Seq
>
259 operator!=(const stack
<_Tp
, _Seq
>& __x
, const stack
<_Tp
, _Seq
>& __y
)
260 { return !(__x
== __y
); }
262 /// Based on operator<
263 template<typename _Tp
, typename _Seq
>
265 operator>(const stack
<_Tp
, _Seq
>& __x
, const stack
<_Tp
, _Seq
>& __y
)
266 { return __y
< __x
; }
268 /// Based on operator<
269 template<typename _Tp
, typename _Seq
>
271 operator<=(const stack
<_Tp
, _Seq
>& __x
, const stack
<_Tp
, _Seq
>& __y
)
272 { return !(__y
< __x
); }
274 /// Based on operator<
275 template<typename _Tp
, typename _Seq
>
277 operator>=(const stack
<_Tp
, _Seq
>& __x
, const stack
<_Tp
, _Seq
>& __y
)
278 { return !(__x
< __y
); }
280 #ifdef __GXX_EXPERIMENTAL_CXX0X__
281 template<typename _Tp
, typename _Seq
>
283 swap(stack
<_Tp
, _Seq
>& __x
, stack
<_Tp
, _Seq
>& __y
)
287 _GLIBCXX_END_NAMESPACE
289 #endif /* _STL_STACK_H */