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 { 221 using std::swap; 222 swap(c, __s.c); 223 } 224 #endif 225 }; 226 227 /** 228 * @brief Stack equality comparison. 229 * @param x A %stack. 230 * @param y A %stack of the same type as @a x. 231 * @return True iff the size and elements of the stacks are equal. 232 * 233 * This is an equivalence relation. Complexity and semantics 234 * depend on the underlying sequence type, but the expected rules 235 * are: this relation is linear in the size of the sequences, and 236 * stacks are considered equivalent if their sequences compare 237 * equal. 238 */ 239 template<typename _Tp, typename _Seq> 240 inline bool 241 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 242 { return __x.c == __y.c; } 243 244 /** 245 * @brief Stack ordering relation. 246 * @param x A %stack. 247 * @param y A %stack of the same type as @a x. 248 * @return True iff @a x is lexicographically less than @a y. 249 * 250 * This is an total ordering relation. Complexity and semantics 251 * depend on the underlying sequence type, but the expected rules 252 * are: this relation is linear in the size of the sequences, the 253 * elements must be comparable with @c <, and 254 * std::lexicographical_compare() is usually used to make the 255 * determination. 256 */ 257 template<typename _Tp, typename _Seq> 258 inline bool 259 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 260 { return __x.c < __y.c; } 261 262 /// Based on operator== 263 template<typename _Tp, typename _Seq> 264 inline bool 265 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 266 { return !(__x == __y); } 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 277 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 278 { return !(__y < __x); } 279 280 /// Based on operator< 281 template<typename _Tp, typename _Seq> 282 inline bool 283 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 284 { return !(__x < __y); } 285 286 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 287 template<typename _Tp, typename _Seq> 288 inline void 289 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y) 290 { __x.swap(__y); } 291 292 template<typename _Tp, typename _Seq, typename _Alloc> 293 struct uses_allocator<stack<_Tp, _Seq>, _Alloc> 294 : public uses_allocator<_Seq, _Alloc>::type { }; 295 #endif 296 297 _GLIBCXX_END_NAMESPACE_VERSION 298 } // namespace 299 300 #endif /* _STL_STACK_H */ 301