libstdc++
stl_stack.h
Go to the documentation of this file.
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 */