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