libstdc++
|
00001 // Stack implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2019 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996,1997 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/stl_stack.h 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{stack} 00054 */ 00055 00056 #ifndef _STL_STACK_H 00057 #define _STL_STACK_H 1 00058 00059 #include <bits/concept_check.h> 00060 #include <debug/debug.h> 00061 #if __cplusplus >= 201103L 00062 # include <bits/uses_allocator.h> 00063 #endif 00064 00065 namespace std _GLIBCXX_VISIBILITY(default) 00066 { 00067 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00068 00069 /** 00070 * @brief A standard container giving FILO behavior. 00071 * 00072 * @ingroup sequences 00073 * 00074 * @tparam _Tp Type of element. 00075 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>. 00076 * 00077 * Meets many of the requirements of a 00078 * <a href="tables.html#65">container</a>, 00079 * but does not define anything to do with iterators. Very few of the 00080 * other standard container interfaces are defined. 00081 * 00082 * This is not a true container, but an @e adaptor. It holds 00083 * another container, and provides a wrapper interface to that 00084 * container. The wrapper is what enforces strict 00085 * first-in-last-out %stack behavior. 00086 * 00087 * The second template parameter defines the type of the underlying 00088 * sequence/container. It defaults to std::deque, but it can be 00089 * any type that supports @c back, @c push_back, and @c pop_back, 00090 * such as std::list, std::vector, or an appropriate user-defined 00091 * type. 00092 * 00093 * Members not found in @a normal containers are @c container_type, 00094 * which is a typedef for the second Sequence parameter, and @c 00095 * push, @c pop, and @c top, which are standard %stack/FILO 00096 * operations. 00097 */ 00098 template<typename _Tp, typename _Sequence = deque<_Tp> > 00099 class stack 00100 { 00101 #ifdef _GLIBCXX_CONCEPT_CHECKS 00102 // concept requirements 00103 typedef typename _Sequence::value_type _Sequence_value_type; 00104 # if __cplusplus < 201103L 00105 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00106 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 00107 # endif 00108 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00109 #endif 00110 00111 template<typename _Tp1, typename _Seq1> 00112 friend bool 00113 operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 00114 00115 template<typename _Tp1, typename _Seq1> 00116 friend bool 00117 operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 00118 00119 #if __cplusplus >= 201103L 00120 template<typename _Alloc> 00121 using _Uses = typename 00122 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; 00123 00124 #if __cplusplus >= 201703L 00125 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00126 // 2566. Requirements on the first template parameter of container 00127 // adaptors 00128 static_assert(is_same<_Tp, typename _Sequence::value_type>::value, 00129 "value_type must be the same as the underlying container"); 00130 #endif // C++17 00131 #endif // C++11 00132 00133 public: 00134 typedef typename _Sequence::value_type value_type; 00135 typedef typename _Sequence::reference reference; 00136 typedef typename _Sequence::const_reference const_reference; 00137 typedef typename _Sequence::size_type size_type; 00138 typedef _Sequence container_type; 00139 00140 protected: 00141 // See queue::c for notes on this name. 00142 _Sequence c; 00143 00144 public: 00145 // XXX removed old def ctor, added def arg to this one to match 14882 00146 /** 00147 * @brief Default constructor creates no elements. 00148 */ 00149 #if __cplusplus < 201103L 00150 explicit 00151 stack(const _Sequence& __c = _Sequence()) 00152 : c(__c) { } 00153 #else 00154 template<typename _Seq = _Sequence, typename _Requires = typename 00155 enable_if<is_default_constructible<_Seq>::value>::type> 00156 stack() 00157 : c() { } 00158 00159 explicit 00160 stack(const _Sequence& __c) 00161 : c(__c) { } 00162 00163 explicit 00164 stack(_Sequence&& __c) 00165 : c(std::move(__c)) { } 00166 00167 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 00168 explicit 00169 stack(const _Alloc& __a) 00170 : c(__a) { } 00171 00172 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 00173 stack(const _Sequence& __c, const _Alloc& __a) 00174 : c(__c, __a) { } 00175 00176 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 00177 stack(_Sequence&& __c, const _Alloc& __a) 00178 : c(std::move(__c), __a) { } 00179 00180 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 00181 stack(const stack& __q, const _Alloc& __a) 00182 : c(__q.c, __a) { } 00183 00184 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 00185 stack(stack&& __q, const _Alloc& __a) 00186 : c(std::move(__q.c), __a) { } 00187 #endif 00188 00189 /** 00190 * Returns true if the %stack is empty. 00191 */ 00192 _GLIBCXX_NODISCARD bool 00193 empty() const 00194 { return c.empty(); } 00195 00196 /** Returns the number of elements in the %stack. */ 00197 size_type 00198 size() const 00199 { return c.size(); } 00200 00201 /** 00202 * Returns a read/write reference to the data at the first 00203 * element of the %stack. 00204 */ 00205 reference 00206 top() 00207 { 00208 __glibcxx_requires_nonempty(); 00209 return c.back(); 00210 } 00211 00212 /** 00213 * Returns a read-only (constant) reference to the data at the first 00214 * element of the %stack. 00215 */ 00216 const_reference 00217 top() const 00218 { 00219 __glibcxx_requires_nonempty(); 00220 return c.back(); 00221 } 00222 00223 /** 00224 * @brief Add data to the top of the %stack. 00225 * @param __x Data to be added. 00226 * 00227 * This is a typical %stack operation. The function creates an 00228 * element at the top of the %stack and assigns the given data 00229 * to it. The time complexity of the operation depends on the 00230 * underlying sequence. 00231 */ 00232 void 00233 push(const value_type& __x) 00234 { c.push_back(__x); } 00235 00236 #if __cplusplus >= 201103L 00237 void 00238 push(value_type&& __x) 00239 { c.push_back(std::move(__x)); } 00240 00241 #if __cplusplus > 201402L 00242 template<typename... _Args> 00243 decltype(auto) 00244 emplace(_Args&&... __args) 00245 { return c.emplace_back(std::forward<_Args>(__args)...); } 00246 #else 00247 template<typename... _Args> 00248 void 00249 emplace(_Args&&... __args) 00250 { c.emplace_back(std::forward<_Args>(__args)...); } 00251 #endif 00252 #endif 00253 00254 /** 00255 * @brief Removes first element. 00256 * 00257 * This is a typical %stack operation. It shrinks the %stack 00258 * by one. The time complexity of the operation depends on the 00259 * underlying sequence. 00260 * 00261 * Note that no data is returned, and if the first element's 00262 * data is needed, it should be retrieved before pop() is 00263 * called. 00264 */ 00265 void 00266 pop() 00267 { 00268 __glibcxx_requires_nonempty(); 00269 c.pop_back(); 00270 } 00271 00272 #if __cplusplus >= 201103L 00273 void 00274 swap(stack& __s) 00275 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 00276 noexcept(__is_nothrow_swappable<_Sequence>::value) 00277 #else 00278 noexcept(__is_nothrow_swappable<_Tp>::value) 00279 #endif 00280 { 00281 using std::swap; 00282 swap(c, __s.c); 00283 } 00284 #endif // __cplusplus >= 201103L 00285 }; 00286 00287 #if __cpp_deduction_guides >= 201606 00288 template<typename _Container, 00289 typename = _RequireNotAllocator<_Container>> 00290 stack(_Container) -> stack<typename _Container::value_type, _Container>; 00291 00292 template<typename _Container, typename _Allocator, 00293 typename = _RequireNotAllocator<_Container>, 00294 typename = _RequireAllocator<_Allocator>> 00295 stack(_Container, _Allocator) 00296 -> stack<typename _Container::value_type, _Container>; 00297 #endif 00298 00299 /** 00300 * @brief Stack equality comparison. 00301 * @param __x A %stack. 00302 * @param __y A %stack of the same type as @a __x. 00303 * @return True iff the size and elements of the stacks are equal. 00304 * 00305 * This is an equivalence relation. Complexity and semantics 00306 * depend on the underlying sequence type, but the expected rules 00307 * are: this relation is linear in the size of the sequences, and 00308 * stacks are considered equivalent if their sequences compare 00309 * equal. 00310 */ 00311 template<typename _Tp, typename _Seq> 00312 inline bool 00313 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00314 { return __x.c == __y.c; } 00315 00316 /** 00317 * @brief Stack ordering relation. 00318 * @param __x A %stack. 00319 * @param __y A %stack of the same type as @a x. 00320 * @return True iff @a x is lexicographically less than @a __y. 00321 * 00322 * This is an total ordering relation. Complexity and semantics 00323 * depend on the underlying sequence type, but the expected rules 00324 * are: this relation is linear in the size of the sequences, the 00325 * elements must be comparable with @c <, and 00326 * std::lexicographical_compare() is usually used to make the 00327 * determination. 00328 */ 00329 template<typename _Tp, typename _Seq> 00330 inline bool 00331 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00332 { return __x.c < __y.c; } 00333 00334 /// Based on operator== 00335 template<typename _Tp, typename _Seq> 00336 inline bool 00337 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00338 { return !(__x == __y); } 00339 00340 /// Based on operator< 00341 template<typename _Tp, typename _Seq> 00342 inline bool 00343 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00344 { return __y < __x; } 00345 00346 /// Based on operator< 00347 template<typename _Tp, typename _Seq> 00348 inline bool 00349 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00350 { return !(__y < __x); } 00351 00352 /// Based on operator< 00353 template<typename _Tp, typename _Seq> 00354 inline bool 00355 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00356 { return !(__x < __y); } 00357 00358 #if __cplusplus >= 201103L 00359 template<typename _Tp, typename _Seq> 00360 inline 00361 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 00362 // Constrained free swap overload, see p0185r1 00363 typename enable_if<__is_swappable<_Seq>::value>::type 00364 #else 00365 void 00366 #endif 00367 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y) 00368 noexcept(noexcept(__x.swap(__y))) 00369 { __x.swap(__y); } 00370 00371 template<typename _Tp, typename _Seq, typename _Alloc> 00372 struct uses_allocator<stack<_Tp, _Seq>, _Alloc> 00373 : public uses_allocator<_Seq, _Alloc>::type { }; 00374 #endif // __cplusplus >= 201103L 00375 00376 _GLIBCXX_END_NAMESPACE_VERSION 00377 } // namespace 00378 00379 #endif /* _STL_STACK_H */