OSDN Git Service

73c8bbd5d4607de49881ba7259c7ca80285de765
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_stack.h
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     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       stack(const _Sequence& __c = _Sequence())
130       : 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       empty() const
146       { return c.empty(); }
147
148       /**  Returns the number of elements in the %stack.  */
149       size_type
150       size() const
151       { 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       top()
159       {
160         __glibcxx_requires_nonempty();
161         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       push(const value_type& __x)
186       { 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       pop()
212       {
213         __glibcxx_requires_nonempty();
214         c.pop_back();
215       }
216
217 #ifdef __GXX_EXPERIMENTAL_CXX0X__
218       void
219       swap(stack& __s)
220       {
221         using std::swap;
222         swap(c, __s.c);
223       }
224 #endif
225     };
226
227   /**
228    *  @brief  Stack equality comparison.
229    *  @param  x  A %stack.
230    *  @param  y  A %stack of the same type as @a x.
231    *  @return  True iff the size and elements of the stacks are equal.
232    *
233    *  This is an equivalence relation.  Complexity and semantics
234    *  depend on the underlying sequence type, but the expected rules
235    *  are: this relation is linear in the size of the sequences, and
236    *  stacks are considered equivalent if their sequences compare
237    *  equal.
238   */
239   template<typename _Tp, typename _Seq>
240     inline bool
241     operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
242     { return __x.c == __y.c; }
243
244   /**
245    *  @brief  Stack ordering relation.
246    *  @param  x  A %stack.
247    *  @param  y  A %stack of the same type as @a x.
248    *  @return  True iff @a x is lexicographically less than @a y.
249    *
250    *  This is an total ordering relation.  Complexity and semantics
251    *  depend on the underlying sequence type, but the expected rules
252    *  are: this relation is linear in the size of the sequences, the
253    *  elements must be comparable with @c <, and
254    *  std::lexicographical_compare() is usually used to make the
255    *  determination.
256   */
257   template<typename _Tp, typename _Seq>
258     inline bool
259     operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
260     { return __x.c < __y.c; }
261
262   /// Based on operator==
263   template<typename _Tp, typename _Seq>
264     inline bool
265     operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
266     { return !(__x == __y); }
267
268   /// Based on operator<
269   template<typename _Tp, typename _Seq>
270     inline bool
271     operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
272     { return __y < __x; }
273
274   /// Based on operator<
275   template<typename _Tp, typename _Seq>
276     inline bool
277     operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
278     { return !(__y < __x); }
279
280   /// Based on operator<
281   template<typename _Tp, typename _Seq>
282     inline bool
283     operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
284     { return !(__x < __y); }
285
286 #ifdef __GXX_EXPERIMENTAL_CXX0X__
287   template<typename _Tp, typename _Seq>
288     inline void
289     swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
290     { __x.swap(__y); }
291
292   template<typename _Tp, typename _Seq, typename _Alloc>
293     struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
294     : public uses_allocator<_Seq, _Alloc>::type { };
295 #endif
296
297 _GLIBCXX_END_NAMESPACE_VERSION
298 } // namespace
299
300 #endif /* _STL_STACK_H */