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 // 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 3, 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 // 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.
20 
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/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
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.
38  *
39  *
40  * Copyright (c) 1996,1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
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.
50  */
51 
52 /** @file stl_stack.h
53  * This is an internal header file, included by other library headers.
54  * You should not attempt to use it directly.
55  */
56 
57 #ifndef _STL_STACK_H
58 #define _STL_STACK_H 1
59 
60 #include <bits/concept_check.h>
61 #include <debug/debug.h>
62 
63 _GLIBCXX_BEGIN_NAMESPACE(std)
64 
65  /**
66  * @brief A standard container giving FILO behavior.
67  *
68  * @ingroup sequences
69  *
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.
74  *
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.
79  *
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
84  * type.
85  *
86  * Members not found in "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
89  * operations.
90  */
91  template<typename _Tp, typename _Sequence = deque<_Tp> >
92  class stack
93  {
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)
99 
100  template<typename _Tp1, typename _Seq1>
101  friend bool
103 
104  template<typename _Tp1, typename _Seq1>
105  friend bool
106  operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
107 
108  public:
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;
114 
115  protected:
116  // See queue::c for notes on this name.
117  _Sequence c;
118 
119  public:
120  // XXX removed old def ctor, added def arg to this one to match 14882
121  /**
122  * @brief Default constructor creates no elements.
123  */
124 #ifndef __GXX_EXPERIMENTAL_CXX0X__
125  explicit
126  stack(const _Sequence& __c = _Sequence())
127  : c(__c) { }
128 #else
129  explicit
130  stack(const _Sequence& __c)
131  : c(__c) { }
132 
133  explicit
134  stack(_Sequence&& __c = _Sequence())
135  : c(std::move(__c)) { }
136 #endif
137 
138  /**
139  * Returns true if the %stack is empty.
140  */
141  bool
142  empty() const
143  { return c.empty(); }
144 
145  /** Returns the number of elements in the %stack. */
146  size_type
147  size() const
148  { return c.size(); }
149 
150  /**
151  * Returns a read/write reference to the data at the first
152  * element of the %stack.
153  */
154  reference
155  top()
156  {
157  __glibcxx_requires_nonempty();
158  return c.back();
159  }
160 
161  /**
162  * Returns a read-only (constant) reference to the data at the first
163  * element of the %stack.
164  */
165  const_reference
166  top() const
167  {
168  __glibcxx_requires_nonempty();
169  return c.back();
170  }
171 
172  /**
173  * @brief Add data to the top of the %stack.
174  * @param x Data to be added.
175  *
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.
180  */
181  void
182  push(const value_type& __x)
183  { c.push_back(__x); }
184 
185 #ifdef __GXX_EXPERIMENTAL_CXX0X__
186  void
187  push(value_type&& __x)
188  { c.push_back(std::move(__x)); }
189 
190  template<typename... _Args>
191  void
192  emplace(_Args&&... __args)
193  { c.emplace_back(std::forward<_Args>(__args)...); }
194 #endif
195 
196  /**
197  * @brief Removes first element.
198  *
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.
202  *
203  * Note that no data is returned, and if the first element's
204  * data is needed, it should be retrieved before pop() is
205  * called.
206  */
207  void
208  pop()
209  {
210  __glibcxx_requires_nonempty();
211  c.pop_back();
212  }
213 
214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
215  void
216  swap(stack&& __s)
217  { c.swap(__s.c); }
218 #endif
219  };
220 
221  /**
222  * @brief Stack equality comparison.
223  * @param x A %stack.
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.
226  *
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
231  * equal.
232  */
233  template<typename _Tp, typename _Seq>
234  inline bool
236  { return __x.c == __y.c; }
237 
238  /**
239  * @brief Stack ordering relation.
240  * @param x A %stack.
241  * @param y A %stack of the same type as @a x.
242  * @return True iff @a x is lexicographically less than @a y.
243  *
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
249  * determination.
250  */
251  template<typename _Tp, typename _Seq>
252  inline bool
253  operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
254  { return __x.c < __y.c; }
255 
256  /// Based on operator==
257  template<typename _Tp, typename _Seq>
258  inline bool
260  { return !(__x == __y); }
261 
262  /// Based on operator<
263  template<typename _Tp, typename _Seq>
264  inline bool
266  { return __y < __x; }
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
278  { return !(__x < __y); }
279 
280 #ifdef __GXX_EXPERIMENTAL_CXX0X__
281  template<typename _Tp, typename _Seq>
282  inline void
283  swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
284  { __x.swap(__y); }
285 
286  template<typename _Tp, typename _Seq>
287  inline void
288  swap(stack<_Tp, _Seq>&& __x, stack<_Tp, _Seq>& __y)
289  { __x.swap(__y); }
290 
291  template<typename _Tp, typename _Seq>
292  inline void
293  swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>&& __y)
294  { __x.swap(__y); }
295 #endif
296 
297 _GLIBCXX_END_NAMESPACE
298 
299 #endif /* _STL_STACK_H */
const_reference top() const
Definition: stl_stack.h:166
A standard container giving FILO behavior.
Definition: stl_stack.h:92
bool operator>(const stack< _Tp, _Seq > &__x, const stack< _Tp, _Seq > &__y)
Based on operator<.
Definition: stl_stack.h:265
void pop()
Removes first element.
Definition: stl_stack.h:208
void push(const value_type &__x)
Add data to the top of the stack.
Definition: stl_stack.h:182
stack(const _Sequence &__c)
Default constructor creates no elements.
Definition: stl_stack.h:130
bool operator==(const stack< _Tp, _Seq > &__x, const stack< _Tp, _Seq > &__y)
Stack equality comparison.
Definition: stl_stack.h:235
reference top()
Definition: stl_stack.h:155
bool empty() const
Definition: stl_stack.h:142
bool operator!=(const stack< _Tp, _Seq > &__x, const stack< _Tp, _Seq > &__y)
Based on operator==.
Definition: stl_stack.h:259
bool operator>=(const stack< _Tp, _Seq > &__x, const stack< _Tp, _Seq > &__y)
Based on operator<.
Definition: stl_stack.h:277
size_type size() const
Definition: stl_stack.h:147