1// Stack implementation -*- C++ -*- 2 3// Copyright (C) 2001-2013 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 62namespace std _GLIBCXX_VISIBILITY(default) 63{ 64_GLIBCXX_BEGIN_NAMESPACE_VERSION 65 66 /** 67 * @brief A standard container giving FILO behavior. 68 * 69 * @ingroup sequences 70 * 71 * @tparam _Tp Type of element. 72 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>. 73 * 74 * Meets many of the requirements of a 75 * <a href="tables.html#65">container</a>, 76 * but does not define anything to do with iterators. Very few of the 77 * other standard container interfaces are defined. 78 * 79 * This is not a true container, but an @e adaptor. It holds 80 * another container, and provides a wrapper interface to that 81 * container. The wrapper is what enforces strict 82 * first-in-last-out %stack behavior. 83 * 84 * The second template parameter defines the type of the underlying 85 * sequence/container. It defaults to std::deque, but it can be 86 * any type that supports @c back, @c push_back, and @c pop_front, 87 * such as std::list, std::vector, or an appropriate user-defined 88 * type. 89 * 90 * Members not found in @a normal containers are @c container_type, 91 * which is a typedef for the second Sequence parameter, and @c 92 * push, @c pop, and @c top, which are standard %stack/FILO 93 * operations. 94 */ 95 template<typename _Tp, typename _Sequence = deque<_Tp> > 96 class stack 97 { 98 // concept requirements 99 typedef typename _Sequence::value_type _Sequence_value_type; 100 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 101 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 102 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 103 104 template<typename _Tp1, typename _Seq1> 105 friend bool 106 operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 107 108 template<typename _Tp1, typename _Seq1> 109 friend bool 110 operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 111 112 public: 113 typedef typename _Sequence::value_type value_type; 114 typedef typename _Sequence::reference reference; 115 typedef typename _Sequence::const_reference const_reference; 116 typedef typename _Sequence::size_type size_type; 117 typedef _Sequence container_type; 118 119 protected: 120 // See queue::c for notes on this name. 121 _Sequence c; 122 123 public: 124 // XXX removed old def ctor, added def arg to this one to match 14882 125 /** 126 * @brief Default constructor creates no elements. 127 */ 128#if __cplusplus < 201103L 129 explicit 130 stack(const _Sequence& __c = _Sequence()) 131 : c(__c) { } 132#else 133 explicit 134 stack(const _Sequence& __c) 135 : c(__c) { } 136 137 explicit 138 stack(_Sequence&& __c = _Sequence()) 139 : c(std::move(__c)) { } 140#endif 141 142 /** 143 * Returns true if the %stack is empty. 144 */ 145 bool 146 empty() const 147 { return c.empty(); } 148 149 /** Returns the number of elements in the %stack. */ 150 size_type 151 size() const 152 { return c.size(); } 153 154 /** 155 * Returns a read/write reference to the data at the first 156 * element of the %stack. 157 */ 158 reference 159 top() 160 { 161 __glibcxx_requires_nonempty(); 162 return c.back(); 163 } 164 165 /** 166 * Returns a read-only (constant) reference to the data at the first 167 * element of the %stack. 168 */ 169 const_reference 170 top() const 171 { 172 __glibcxx_requires_nonempty(); 173 return c.back(); 174 } 175 176 /** 177 * @brief Add data to the top of the %stack. 178 * @param __x Data to be added. 179 * 180 * This is a typical %stack operation. The function creates an 181 * element at the top of the %stack and assigns the given data 182 * to it. The time complexity of the operation depends on the 183 * underlying sequence. 184 */ 185 void 186 push(const value_type& __x) 187 { c.push_back(__x); } 188 189#if __cplusplus >= 201103L 190 void 191 push(value_type&& __x) 192 { c.push_back(std::move(__x)); } 193 194 template<typename... _Args> 195 void 196 emplace(_Args&&... __args) 197 { c.emplace_back(std::forward<_Args>(__args)...); } 198#endif 199 200 /** 201 * @brief Removes first element. 202 * 203 * This is a typical %stack operation. It shrinks the %stack 204 * by one. The time complexity of the operation depends on the 205 * underlying sequence. 206 * 207 * Note that no data is returned, and if the first element's 208 * data is needed, it should be retrieved before pop() is 209 * called. 210 */ 211 void 212 pop() 213 { 214 __glibcxx_requires_nonempty(); 215 c.pop_back(); 216 } 217 218#if __cplusplus >= 201103L 219 void 220 swap(stack& __s) 221 noexcept(noexcept(swap(c, __s.c))) 222 { 223 using std::swap; 224 swap(c, __s.c); 225 } 226#endif 227 }; 228 229 /** 230 * @brief Stack equality comparison. 231 * @param __x A %stack. 232 * @param __y A %stack of the same type as @a __x. 233 * @return True iff the size and elements of the stacks are equal. 234 * 235 * This is an equivalence relation. Complexity and semantics 236 * depend on the underlying sequence type, but the expected rules 237 * are: this relation is linear in the size of the sequences, and 238 * stacks are considered equivalent if their sequences compare 239 * equal. 240 */ 241 template<typename _Tp, typename _Seq> 242 inline bool 243 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 244 { return __x.c == __y.c; } 245 246 /** 247 * @brief Stack ordering relation. 248 * @param __x A %stack. 249 * @param __y A %stack of the same type as @a x. 250 * @return True iff @a x is lexicographically less than @a __y. 251 * 252 * This is an total ordering relation. Complexity and semantics 253 * depend on the underlying sequence type, but the expected rules 254 * are: this relation is linear in the size of the sequences, the 255 * elements must be comparable with @c <, and 256 * std::lexicographical_compare() is usually used to make the 257 * determination. 258 */ 259 template<typename _Tp, typename _Seq> 260 inline bool 261 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 262 { return __x.c < __y.c; } 263 264 /// Based on operator== 265 template<typename _Tp, typename _Seq> 266 inline bool 267 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 268 { return !(__x == __y); } 269 270 /// Based on operator< 271 template<typename _Tp, typename _Seq> 272 inline bool 273 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 274 { return __y < __x; } 275 276 /// Based on operator< 277 template<typename _Tp, typename _Seq> 278 inline bool 279 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 280 { return !(__y < __x); } 281 282 /// Based on operator< 283 template<typename _Tp, typename _Seq> 284 inline bool 285 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 286 { return !(__x < __y); } 287 288#if __cplusplus >= 201103L 289 template<typename _Tp, typename _Seq> 290 inline void 291 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y) 292 noexcept(noexcept(__x.swap(__y))) 293 { __x.swap(__y); } 294 295 template<typename _Tp, typename _Seq, typename _Alloc> 296 struct uses_allocator<stack<_Tp, _Seq>, _Alloc> 297 : public uses_allocator<_Seq, _Alloc>::type { }; 298#endif 299 300_GLIBCXX_END_NAMESPACE_VERSION 301} // namespace 302 303#endif /* _STL_STACK_H */ 304