00001 // Stack implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 2, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 /* 00032 * 00033 * Copyright (c) 1994 00034 * Hewlett-Packard Company 00035 * 00036 * Permission to use, copy, modify, distribute and sell this software 00037 * and its documentation for any purpose is hereby granted without fee, 00038 * provided that the above copyright notice appear in all copies and 00039 * that both that copyright notice and this permission notice appear 00040 * in supporting documentation. Hewlett-Packard Company makes no 00041 * representations about the suitability of this software for any 00042 * purpose. It is provided "as is" without express or implied warranty. 00043 * 00044 * 00045 * Copyright (c) 1996,1997 00046 * Silicon Graphics Computer Systems, Inc. 00047 * 00048 * Permission to use, copy, modify, distribute and sell this software 00049 * and its documentation for any purpose is hereby granted without fee, 00050 * provided that the above copyright notice appear in all copies and 00051 * that both that copyright notice and this permission notice appear 00052 * in supporting documentation. Silicon Graphics makes no 00053 * representations about the suitability of this software for any 00054 * purpose. It is provided "as is" without express or implied warranty. 00055 */ 00056 00057 /** @file stl_stack.h 00058 * This is an internal header file, included by other library headers. 00059 * You should not attempt to use it directly. 00060 */ 00061 00062 #ifndef _STL_STACK_H 00063 #define _STL_STACK_H 1 00064 00065 #include <bits/concept_check.h> 00066 #include <debug/debug.h> 00067 00068 _GLIBCXX_BEGIN_NAMESPACE(std) 00069 00070 /** 00071 * @brief A standard container giving FILO behavior. 00072 * 00073 * @ingroup Containers 00074 * @ingroup Sequences 00075 * 00076 * Meets many of the requirements of a 00077 * <a href="tables.html#65">container</a>, 00078 * but does not define anything to do with iterators. Very few of the 00079 * other standard container interfaces are defined. 00080 * 00081 * This is not a true container, but an @e adaptor. It holds 00082 * another container, and provides a wrapper interface to that 00083 * container. The wrapper is what enforces strict 00084 * first-in-last-out %stack behavior. 00085 * 00086 * The second template parameter defines the type of the underlying 00087 * sequence/container. It defaults to std::deque, but it can be 00088 * any type that supports @c back, @c push_back, and @c pop_front, 00089 * such as std::list, std::vector, or an appropriate user-defined 00090 * type. 00091 * 00092 * Members not found in "normal" containers are @c container_type, 00093 * which is a typedef for the second Sequence parameter, and @c 00094 * push, @c pop, and @c top, which are standard %stack/FILO 00095 * operations. 00096 */ 00097 template<typename _Tp, typename _Sequence = deque<_Tp> > 00098 class stack 00099 { 00100 // concept requirements 00101 typedef typename _Sequence::value_type _Sequence_value_type; 00102 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00103 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 00104 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00105 00106 template<typename _Tp1, typename _Seq1> 00107 friend bool 00108 operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 00109 00110 template<typename _Tp1, typename _Seq1> 00111 friend bool 00112 operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 00113 00114 public: 00115 typedef typename _Sequence::value_type value_type; 00116 typedef typename _Sequence::reference reference; 00117 typedef typename _Sequence::const_reference const_reference; 00118 typedef typename _Sequence::size_type size_type; 00119 typedef _Sequence container_type; 00120 00121 protected: 00122 // See queue::c for notes on this name. 00123 _Sequence c; 00124 00125 public: 00126 // XXX removed old def ctor, added def arg to this one to match 14882 00127 /** 00128 * @brief Default constructor creates no elements. 00129 */ 00130 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00131 explicit 00132 stack(const _Sequence& __c = _Sequence()) 00133 : c(__c) { } 00134 #else 00135 explicit 00136 stack(const _Sequence& __c) 00137 : c(__c) { } 00138 00139 explicit 00140 stack(_Sequence&& __c = _Sequence()) 00141 : c(std::move(__c)) { } 00142 #endif 00143 00144 /** 00145 * Returns true if the %stack is empty. 00146 */ 00147 bool 00148 empty() const 00149 { return c.empty(); } 00150 00151 /** Returns the number of elements in the %stack. */ 00152 size_type 00153 size() const 00154 { return c.size(); } 00155 00156 /** 00157 * Returns a read/write reference to the data at the first 00158 * element of the %stack. 00159 */ 00160 reference 00161 top() 00162 { 00163 __glibcxx_requires_nonempty(); 00164 return c.back(); 00165 } 00166 00167 /** 00168 * Returns a read-only (constant) reference to the data at the first 00169 * element of the %stack. 00170 */ 00171 const_reference 00172 top() const 00173 { 00174 __glibcxx_requires_nonempty(); 00175 return c.back(); 00176 } 00177 00178 /** 00179 * @brief Add data to the top of the %stack. 00180 * @param x Data to be added. 00181 * 00182 * This is a typical %stack operation. The function creates an 00183 * element at the top of the %stack and assigns the given data 00184 * to it. The time complexity of the operation depends on the 00185 * underlying sequence. 00186 */ 00187 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00188 void 00189 push(const value_type& __x) 00190 { c.push_back(__x); } 00191 #else 00192 // NB: DR 756. 00193 template<typename... _Args> 00194 void 00195 push(_Args&&... __args) 00196 { c.push_back(std::forward<_Args>(__args)...); } 00197 #endif 00198 00199 /** 00200 * @brief Removes first element. 00201 * 00202 * This is a typical %stack operation. It shrinks the %stack 00203 * by one. The time complexity of the operation depends on the 00204 * underlying sequence. 00205 * 00206 * Note that no data is returned, and if the first element's 00207 * data is needed, it should be retrieved before pop() is 00208 * called. 00209 */ 00210 void 00211 pop() 00212 { 00213 __glibcxx_requires_nonempty(); 00214 c.pop_back(); 00215 } 00216 00217 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00218 void 00219 swap(stack&& __s) 00220 { c.swap(__s.c); } 00221 #endif 00222 }; 00223 00224 /** 00225 * @brief Stack equality comparison. 00226 * @param x A %stack. 00227 * @param y A %stack of the same type as @a x. 00228 * @return True iff the size and elements of the stacks are equal. 00229 * 00230 * This is an equivalence relation. Complexity and semantics 00231 * depend on the underlying sequence type, but the expected rules 00232 * are: this relation is linear in the size of the sequences, and 00233 * stacks are considered equivalent if their sequences compare 00234 * equal. 00235 */ 00236 template<typename _Tp, typename _Seq> 00237 inline bool 00238 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00239 { return __x.c == __y.c; } 00240 00241 /** 00242 * @brief Stack ordering relation. 00243 * @param x A %stack. 00244 * @param y A %stack of the same type as @a x. 00245 * @return True iff @a x is lexicographically less than @a y. 00246 * 00247 * This is an total ordering relation. Complexity and semantics 00248 * depend on the underlying sequence type, but the expected rules 00249 * are: this relation is linear in the size of the sequences, the 00250 * elements must be comparable with @c <, and 00251 * std::lexicographical_compare() is usually used to make the 00252 * determination. 00253 */ 00254 template<typename _Tp, typename _Seq> 00255 inline bool 00256 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00257 { return __x.c < __y.c; } 00258 00259 /// Based on operator== 00260 template<typename _Tp, typename _Seq> 00261 inline bool 00262 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00263 { return !(__x == __y); } 00264 00265 /// Based on operator< 00266 template<typename _Tp, typename _Seq> 00267 inline bool 00268 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00269 { return __y < __x; } 00270 00271 /// Based on operator< 00272 template<typename _Tp, typename _Seq> 00273 inline bool 00274 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00275 { return !(__y < __x); } 00276 00277 /// Based on operator< 00278 template<typename _Tp, typename _Seq> 00279 inline bool 00280 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 00281 { return !(__x < __y); } 00282 00283 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00284 template<typename _Tp, typename _Seq> 00285 inline void 00286 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y) 00287 { __x.swap(__y); } 00288 00289 template<typename _Tp, typename _Seq> 00290 inline void 00291 swap(stack<_Tp, _Seq>&& __x, stack<_Tp, _Seq>& __y) 00292 { __x.swap(__y); } 00293 00294 template<typename _Tp, typename _Seq> 00295 inline void 00296 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>&& __y) 00297 { __x.swap(__y); } 00298 #endif 00299 00300 _GLIBCXX_END_NAMESPACE 00301 00302 #endif /* _STL_STACK_H */