1 // Stack implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996,1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56 /** @file stl_stack.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61 #ifndef _STACK_H 62 #define _STACK_H 1 63 64 #include <bits/concept_check.h> 65 #include <debug/debug.h> 66 67 namespace std 68 { 69 // Forward declarations of operators == and <, needed for friend 70 // declaration. 71 template<typename _Tp, typename _Sequence = deque<_Tp> > 72 class stack; 73 74 template<typename _Tp, typename _Seq> 75 inline bool 76 operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y); 77 78 template<typename _Tp, typename _Seq> 79 inline bool 80 operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y); 81 82 /** 83 * @brief A standard container giving FILO behavior. 84 * 85 * @ingroup Containers 86 * @ingroup Sequences 87 * 88 * Meets many of the requirements of a 89 * <a href="tables.html#65">container</a>, 90 * but does not define anything to do with iterators. Very few of the 91 * other standard container interfaces are defined. 92 * 93 * This is not a true container, but an @e adaptor. It holds 94 * another container, and provides a wrapper interface to that 95 * container. The wrapper is what enforces strict 96 * first-in-last-out %stack behavior. 97 * 98 * The second template parameter defines the type of the underlying 99 * sequence/container. It defaults to std::deque, but it can be 100 * any type that supports @c back, @c push_back, and @c pop_front, 101 * such as std::list, std::vector, or an appropriate user-defined 102 * type. 103 * 104 * Members not found in "normal" containers are @c container_type, 105 * which is a typedef for the second Sequence parameter, and @c 106 * push, @c pop, and @c top, which are standard %stack/FILO 107 * operations. 108 */ 109 template<typename _Tp, typename _Sequence> 110 class stack 111 { 112 // concept requirements 113 typedef typename _Sequence::value_type _Sequence_value_type; 114 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 115 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 116 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 117 118 template<typename _Tp1, typename _Seq1> 119 friend bool 120 operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 121 122 template<typename _Tp1, typename _Seq1> 123 friend bool 124 operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 125 126 public: 127 typedef typename _Sequence::value_type value_type; 128 typedef typename _Sequence::reference reference; 129 typedef typename _Sequence::const_reference const_reference; 130 typedef typename _Sequence::size_type size_type; 131 typedef _Sequence container_type; 132 133 protected: 134 // See queue::c for notes on this name. 135 _Sequence c; 136 137 public: 138 // XXX removed old def ctor, added def arg to this one to match 14882 139 /** 140 * @brief Default constructor creates no elements. 141 */ 142 explicit 143 stack(const _Sequence& __c = _Sequence()) 144 : c(__c) {} 145 146 /** 147 * Returns true if the %stack is empty. 148 */ 149 bool 150 empty() const 151 { return c.empty(); } 152 153 /** Returns the number of elements in the %stack. */ 154 size_type 155 size() const 156 { return c.size(); } 157 158 /** 159 * Returns a read/write reference to the data at the first 160 * element of the %stack. 161 */ 162 reference 163 top() 164 { 165 __glibcxx_requires_nonempty(); 166 return c.back(); 167 } 168 169 /** 170 * Returns a read-only (constant) reference to the data at the first 171 * element of the %stack. 172 */ 173 const_reference 174 top() const 175 { 176 __glibcxx_requires_nonempty(); 177 return c.back(); 178 } 179 180 /** 181 * @brief Add data to the top of the %stack. 182 * @param x Data to be added. 183 * 184 * This is a typical %stack operation. The function creates an 185 * element at the top of the %stack and assigns the given data 186 * to it. The time complexity of the operation depends on the 187 * underlying sequence. 188 */ 189 void 190 push(const value_type& __x) 191 { c.push_back(__x); } 192 193 /** 194 * @brief Removes first element. 195 * 196 * This is a typical %stack operation. It shrinks the %stack 197 * by one. The time complexity of the operation depends on the 198 * underlying sequence. 199 * 200 * Note that no data is returned, and if the first element's 201 * data is needed, it should be retrieved before pop() is 202 * called. 203 */ 204 void 205 pop() 206 { 207 __glibcxx_requires_nonempty(); 208 c.pop_back(); 209 } 210 }; 211 212 /** 213 * @brief Stack equality comparison. 214 * @param x A %stack. 215 * @param y A %stack of the same type as @a x. 216 * @return True iff the size and elements of the stacks are equal. 217 * 218 * This is an equivalence relation. Complexity and semantics 219 * depend on the underlying sequence type, but the expected rules 220 * are: this relation is linear in the size of the sequences, and 221 * stacks are considered equivalent if their sequences compare 222 * equal. 223 */ 224 template<typename _Tp, typename _Seq> 225 inline bool 226 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 227 { return __x.c == __y.c; } 228 229 /** 230 * @brief Stack ordering relation. 231 * @param x A %stack. 232 * @param y A %stack of the same type as @a x. 233 * @return True iff @a x is lexicographically less than @a y. 234 * 235 * This is an total ordering 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, the 238 * elements must be comparable with @c <, and 239 * std::lexicographical_compare() is usually used to make the 240 * determination. 241 */ 242 template<typename _Tp, typename _Seq> 243 inline bool 244 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 245 { return __x.c < __y.c; } 246 247 /// Based on operator== 248 template<typename _Tp, typename _Seq> 249 inline bool 250 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 251 { return !(__x == __y); } 252 253 /// Based on operator< 254 template<typename _Tp, typename _Seq> 255 inline bool 256 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 257 { return __y < __x; } 258 259 /// Based on operator< 260 template<typename _Tp, typename _Seq> 261 inline bool 262 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 263 { return !(__y < __x); } 264 265 /// Based on operator< 266 template<typename _Tp, typename _Seq> 267 inline bool 268 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 269 { return !(__x < __y); } 270 } // namespace std 271 272 #endif /* _STACK_H */ 273