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  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 */