Clang Project

include/c++/7/bits/stl_stack.h
1// Stack implementation -*- C++ -*-
2
3// Copyright (C) 2001-2017 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation.  Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose.  It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation.  Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose.  It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_stack.h
52 *  This is an internal header file, included by other library headers.
53 *  Do not attempt to use it directly. @headername{stack}
54 */
55
56#ifndef _STL_STACK_H
57#define _STL_STACK_H 1
58
59#include <bits/concept_check.h>
60#include <debug/debug.h>
61#if __cplusplus >= 201103L
62# include <bits/uses_allocator.h>
63#endif
64
65namespace std _GLIBCXX_VISIBILITY(default)
66{
67_GLIBCXX_BEGIN_NAMESPACE_VERSION
68
69  /**
70   *  @brief  A standard container giving FILO behavior.
71   *
72   *  @ingroup sequences
73   *
74   *  @tparam _Tp  Type of element.
75   *  @tparam _Sequence  Type of underlying sequence, defaults to deque<_Tp>.
76   *
77   *  Meets many of the requirements of a
78   *  <a href="tables.html#65">container</a>,
79   *  but does not define anything to do with iterators.  Very few of the
80   *  other standard container interfaces are defined.
81   *
82   *  This is not a true container, but an @e adaptor.  It holds
83   *  another container, and provides a wrapper interface to that
84   *  container.  The wrapper is what enforces strict
85   *  first-in-last-out %stack behavior.
86   *
87   *  The second template parameter defines the type of the underlying
88   *  sequence/container.  It defaults to std::deque, but it can be
89   *  any type that supports @c back, @c push_back, and @c pop_back,
90   *  such as std::list, std::vector, or an appropriate user-defined
91   *  type.
92   *
93   *  Members not found in @a normal containers are @c container_type,
94   *  which is a typedef for the second Sequence parameter, and @c
95   *  push, @c pop, and @c top, which are standard %stack/FILO
96   *  operations.
97  */
98  template<typename _Tp, typename _Sequence = deque<_Tp> >
99    class stack
100    {
101#ifdef _GLIBCXX_CONCEPT_CHECKS
102      // concept requirements
103      typedef typename _Sequence::value_type _Sequence_value_type;
104# if __cplusplus < 201103L
105      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
106      __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
107# endif
108      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
109#endif
110
111      template<typename _Tp1, typename _Seq1>
112 friend bool
113 operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
114
115      template<typename _Tp1, typename _Seq1>
116 friend bool
117 operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
118
119#if __cplusplus >= 201103L
120      template<typename _Alloc>
121 using _Uses = typename
122   enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
123#endif
124
125    public:
126      typedef typename _Sequence::value_type value_type;
127      typedef typename _Sequence::reference reference;
128      typedef typename _Sequence::const_reference const_reference;
129      typedef typename _Sequence::size_type size_type;
130      typedef        _Sequence container_type;
131
132    protected:
133      //  See queue::c for notes on this name.
134      _Sequence c;
135
136    public:
137      // XXX removed old def ctor, added def arg to this one to match 14882
138      /**
139       *  @brief  Default constructor creates no elements.
140       */
141#if __cplusplus < 201103L
142      explicit
143      stack(const _Sequence& __c = _Sequence())
144      : c(__c) { }
145#else
146      template<typename _Seq = _Sequence, typename _Requires = typename
147        enable_if<is_default_constructible<_Seq>::value>::type>
148 stack()
149 : c() { }
150
151      explicit
152      stack(const _Sequence& __c)
153      : c(__c) { }
154
155      explicit
156      stack(_Sequence&& __c)
157      : c(std::move(__c)) { }
158
159      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
160 explicit
161 stack(const _Alloc& __a)
162 : c(__a) { }
163
164      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
165 stack(const _Sequence& __c, const _Alloc& __a)
166 : c(__c, __a) { }
167
168      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
169 stack(_Sequence&& __c, const _Alloc& __a)
170 : c(std::move(__c), __a) { }
171
172      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
173 stack(const stack& __q, const _Alloc& __a)
174 : c(__q.c, __a) { }
175
176      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
177 stack(stack&& __q, const _Alloc& __a)
178 : c(std::move(__q.c), __a) { }
179#endif
180
181      /**
182       *  Returns true if the %stack is empty.
183       */
184      bool
185      empty() const
186      { return c.empty(); }
187
188      /**  Returns the number of elements in the %stack.  */
189      size_type
190      size() const
191      { return c.size(); }
192
193      /**
194       *  Returns a read/write reference to the data at the first
195       *  element of the %stack.
196       */
197      reference
198      top()
199      {
200 __glibcxx_requires_nonempty();
201 return c.back();
202      }
203
204      /**
205       *  Returns a read-only (constant) reference to the data at the first
206       *  element of the %stack.
207       */
208      const_reference
209      top() const
210      {
211 __glibcxx_requires_nonempty();
212 return c.back();
213      }
214
215      /**
216       *  @brief  Add data to the top of the %stack.
217       *  @param  __x  Data to be added.
218       *
219       *  This is a typical %stack operation.  The function creates an
220       *  element at the top of the %stack and assigns the given data
221       *  to it.  The time complexity of the operation depends on the
222       *  underlying sequence.
223       */
224      void
225      push(const value_type& __x)
226      { c.push_back(__x); }
227
228#if __cplusplus >= 201103L
229      void
230      push(value_type&& __x)
231      { c.push_back(std::move(__x)); }
232
233#if __cplusplus > 201402L
234      template<typename... _Args>
235 decltype(auto)
236 emplace(_Args&&... __args)
237 { return c.emplace_back(std::forward<_Args>(__args)...); }
238#else
239      template<typename... _Args>
240 void
241 emplace(_Args&&... __args)
242 { c.emplace_back(std::forward<_Args>(__args)...); }
243#endif
244#endif
245
246      /**
247       *  @brief  Removes first element.
248       *
249       *  This is a typical %stack operation.  It shrinks the %stack
250       *  by one.  The time complexity of the operation depends on the
251       *  underlying sequence.
252       *
253       *  Note that no data is returned, and if the first element's
254       *  data is needed, it should be retrieved before pop() is
255       *  called.
256       */
257      void
258      pop()
259      {
260 __glibcxx_requires_nonempty();
261 c.pop_back();
262      }
263
264#if __cplusplus >= 201103L
265      void
266      swap(stack& __s)
267#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
268      noexcept(__is_nothrow_swappable<_Sequence>::value)
269#else
270      noexcept(__is_nothrow_swappable<_Tp>::value)
271#endif
272      {
273 using std::swap;
274 swap(c, __s.c);
275      }
276#endif // __cplusplus >= 201103L
277    };
278
279  /**
280   *  @brief  Stack equality comparison.
281   *  @param  __x  A %stack.
282   *  @param  __y  A %stack of the same type as @a __x.
283   *  @return  True iff the size and elements of the stacks are equal.
284   *
285   *  This is an equivalence relation.  Complexity and semantics
286   *  depend on the underlying sequence type, but the expected rules
287   *  are: this relation is linear in the size of the sequences, and
288   *  stacks are considered equivalent if their sequences compare
289   *  equal.
290  */
291  template<typename _Tp, typename _Seq>
292    inline bool
293    operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
294    { return __x.c == __y.c; }
295
296  /**
297   *  @brief  Stack ordering relation.
298   *  @param  __x  A %stack.
299   *  @param  __y  A %stack of the same type as @a x.
300   *  @return  True iff @a x is lexicographically less than @a __y.
301   *
302   *  This is an total ordering relation.  Complexity and semantics
303   *  depend on the underlying sequence type, but the expected rules
304   *  are: this relation is linear in the size of the sequences, the
305   *  elements must be comparable with @c <, and
306   *  std::lexicographical_compare() is usually used to make the
307   *  determination.
308  */
309  template<typename _Tp, typename _Seq>
310    inline bool
311    operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
312    { return __x.c < __y.c; }
313
314  /// Based on operator==
315  template<typename _Tp, typename _Seq>
316    inline bool
317    operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
318    { return !(__x == __y); }
319
320  /// Based on operator<
321  template<typename _Tp, typename _Seq>
322    inline bool
323    operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
324    { return __y < __x; }
325
326  /// Based on operator<
327  template<typename _Tp, typename _Seq>
328    inline bool
329    operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
330    { return !(__y < __x); }
331
332  /// Based on operator<
333  template<typename _Tp, typename _Seq>
334    inline bool
335    operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
336    { return !(__x < __y); }
337
338#if __cplusplus >= 201103L
339  template<typename _Tp, typename _Seq>
340    inline
341#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
342    // Constrained free swap overload, see p0185r1
343    typename enable_if<__is_swappable<_Seq>::value>::type
344#else
345    void
346#endif
347    swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
348    noexcept(noexcept(__x.swap(__y)))
349    { __x.swap(__y); }
350
351  template<typename _Tp, typename _Seq, typename _Alloc>
352    struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
353    : public uses_allocator<_Seq, _Alloc>::type { };
354#endif // __cplusplus >= 201103L
355
356_GLIBCXX_END_NAMESPACE_VERSION
357} // namespace
358
359#endif /* _STL_STACK_H */
360
std::stack::c
std::stack::empty
std::stack::size
std::stack::top
std::stack::top
std::stack::push
std::stack::push
std::stack::emplace
std::stack::pop
std::stack::swap
CodeThinker, Enjoy your reading code