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