1 | // Stack implementation -*- C++ -*- |
---|---|

2 | |

3 | // Copyright (C) 2001-2018 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 | #if __cplusplus >= 201103L |

62 | # include <bits/uses_allocator.h> |

63 | #endif |

64 | |

65 | namespace std _GLIBCXX_VISIBILITY(default) |

66 | { |

67 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

68 | |

69 | /** |

70 | * @brief A standard container giving FILO behavior. |

71 | * |

72 | * @ingroup sequences |

73 | * |

74 | * @tparam _Tp Type of element. |

75 | * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>. |

76 | * |

77 | * Meets many of the requirements of a |

78 | * <a href="tables.html#65">container</a>, |

79 | * but does not define anything to do with iterators. Very few of the |

80 | * other standard container interfaces are defined. |

81 | * |

82 | * This is not a true container, but an @e adaptor. It holds |

83 | * another container, and provides a wrapper interface to that |

84 | * container. The wrapper is what enforces strict |

85 | * first-in-last-out %stack behavior. |

86 | * |

87 | * The second template parameter defines the type of the underlying |

88 | * sequence/container. It defaults to std::deque, but it can be |

89 | * any type that supports @c back, @c push_back, and @c pop_back, |

90 | * such as std::list, std::vector, or an appropriate user-defined |

91 | * type. |

92 | * |

93 | * Members not found in @a normal containers are @c container_type, |

94 | * which is a typedef for the second Sequence parameter, and @c |

95 | * push, @c pop, and @c top, which are standard %stack/FILO |

96 | * operations. |

97 | */ |

98 | template<typename _Tp, typename _Sequence = deque<_Tp> > |

99 | class stack |

100 | { |

101 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

102 | // concept requirements |

103 | typedef typename _Sequence::value_type _Sequence_value_type; |

104 | # if __cplusplus < 201103L |

105 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |

106 | __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) |

107 | # endif |

108 | __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) |

109 | #endif |

110 | |

111 | template<typename _Tp1, typename _Seq1> |

112 | friend bool |

113 | operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); |

114 | |

115 | template<typename _Tp1, typename _Seq1> |

116 | friend bool |

117 | operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); |

118 | |

119 | #if __cplusplus >= 201103L |

120 | template<typename _Alloc> |

121 | using _Uses = typename |

122 | enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; |

123 | #endif |

124 | |

125 | public: |

126 | typedef typename _Sequence::value_type value_type; |

127 | typedef typename _Sequence::reference reference; |

128 | typedef typename _Sequence::const_reference const_reference; |

129 | typedef typename _Sequence::size_type size_type; |

130 | typedef _Sequence container_type; |

131 | |

132 | protected: |

133 | // See queue::c for notes on this name. |

134 | _Sequence c; |

135 | |

136 | public: |

137 | // XXX removed old def ctor, added def arg to this one to match 14882 |

138 | /** |

139 | * @brief Default constructor creates no elements. |

140 | */ |

141 | #if __cplusplus < 201103L |

142 | explicit |

143 | stack(const _Sequence& __c = _Sequence()) |

144 | : c(__c) { } |

145 | #else |

146 | template<typename _Seq = _Sequence, typename _Requires = typename |

147 | enable_if<is_default_constructible<_Seq>::value>::type> |

148 | stack() |

149 | : c() { } |

150 | |

151 | explicit |

152 | stack(const _Sequence& __c) |

153 | : c(__c) { } |

154 | |

155 | explicit |

156 | stack(_Sequence&& __c) |

157 | : c(std::move(__c)) { } |

158 | |

159 | template<typename _Alloc, typename _Requires = _Uses<_Alloc>> |

160 | explicit |

161 | stack(const _Alloc& __a) |

162 | : c(__a) { } |

163 | |

164 | template<typename _Alloc, typename _Requires = _Uses<_Alloc>> |

165 | stack(const _Sequence& __c, const _Alloc& __a) |

166 | : c(__c, __a) { } |

167 | |

168 | template<typename _Alloc, typename _Requires = _Uses<_Alloc>> |

169 | stack(_Sequence&& __c, const _Alloc& __a) |

170 | : c(std::move(__c), __a) { } |

171 | |

172 | template<typename _Alloc, typename _Requires = _Uses<_Alloc>> |

173 | stack(const stack& __q, const _Alloc& __a) |

174 | : c(__q.c, __a) { } |

175 | |

176 | template<typename _Alloc, typename _Requires = _Uses<_Alloc>> |

177 | stack(stack&& __q, const _Alloc& __a) |

178 | : c(std::move(__q.c), __a) { } |

179 | #endif |

180 | |

181 | /** |

182 | * Returns true if the %stack is empty. |

183 | */ |

184 | bool |

185 | empty() const |

186 | { return c.empty(); } |

187 | |

188 | /** Returns the number of elements in the %stack. */ |

189 | size_type |

190 | size() const |

191 | { return c.size(); } |

192 | |

193 | /** |

194 | * Returns a read/write reference to the data at the first |

195 | * element of the %stack. |

196 | */ |

197 | reference |

198 | top() |

199 | { |

200 | __glibcxx_requires_nonempty(); |

201 | return c.back(); |

202 | } |

203 | |

204 | /** |

205 | * Returns a read-only (constant) reference to the data at the first |

206 | * element of the %stack. |

207 | */ |

208 | const_reference |

209 | top() const |

210 | { |

211 | __glibcxx_requires_nonempty(); |

212 | return c.back(); |

213 | } |

214 | |

215 | /** |

216 | * @brief Add data to the top of the %stack. |

217 | * @param __x Data to be added. |

218 | * |

219 | * This is a typical %stack operation. The function creates an |

220 | * element at the top of the %stack and assigns the given data |

221 | * to it. The time complexity of the operation depends on the |

222 | * underlying sequence. |

223 | */ |

224 | void |

225 | push(const value_type& __x) |

226 | { c.push_back(__x); } |

227 | |

228 | #if __cplusplus >= 201103L |

229 | void |

230 | push(value_type&& __x) |

231 | { c.push_back(std::move(__x)); } |

232 | |

233 | #if __cplusplus > 201402L |

234 | template<typename... _Args> |

235 | decltype(auto) |

236 | emplace(_Args&&... __args) |

237 | { return c.emplace_back(std::forward<_Args>(__args)...); } |

238 | #else |

239 | template<typename... _Args> |

240 | void |

241 | emplace(_Args&&... __args) |

242 | { c.emplace_back(std::forward<_Args>(__args)...); } |

243 | #endif |

244 | #endif |

245 | |

246 | /** |

247 | * @brief Removes first element. |

248 | * |

249 | * This is a typical %stack operation. It shrinks the %stack |

250 | * by one. The time complexity of the operation depends on the |

251 | * underlying sequence. |

252 | * |

253 | * Note that no data is returned, and if the first element's |

254 | * data is needed, it should be retrieved before pop() is |

255 | * called. |

256 | */ |

257 | void |

258 | pop() |

259 | { |

260 | __glibcxx_requires_nonempty(); |

261 | c.pop_back(); |

262 | } |

263 | |

264 | #if __cplusplus >= 201103L |

265 | void |

266 | swap(stack& __s) |

267 | #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 |

268 | noexcept(__is_nothrow_swappable<_Sequence>::value) |

269 | #else |

270 | noexcept(__is_nothrow_swappable<_Tp>::value) |

271 | #endif |

272 | { |

273 | using std::swap; |

274 | swap(c, __s.c); |

275 | } |

276 | #endif // __cplusplus >= 201103L |

277 | }; |

278 | |

279 | /** |

280 | * @brief Stack equality comparison. |

281 | * @param __x A %stack. |

282 | * @param __y A %stack of the same type as @a __x. |

283 | * @return True iff the size and elements of the stacks are equal. |

284 | * |

285 | * This is an equivalence relation. Complexity and semantics |

286 | * depend on the underlying sequence type, but the expected rules |

287 | * are: this relation is linear in the size of the sequences, and |

288 | * stacks are considered equivalent if their sequences compare |

289 | * equal. |

290 | */ |

291 | template<typename _Tp, typename _Seq> |

292 | inline bool |

293 | operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) |

294 | { return __x.c == __y.c; } |

295 | |

296 | /** |

297 | * @brief Stack ordering relation. |

298 | * @param __x A %stack. |

299 | * @param __y A %stack of the same type as @a x. |

300 | * @return True iff @a x is lexicographically less than @a __y. |

301 | * |

302 | * This is an total ordering relation. Complexity and semantics |

303 | * depend on the underlying sequence type, but the expected rules |

304 | * are: this relation is linear in the size of the sequences, the |

305 | * elements must be comparable with @c <, and |

306 | * std::lexicographical_compare() is usually used to make the |

307 | * determination. |

308 | */ |

309 | template<typename _Tp, typename _Seq> |

310 | inline bool |

311 | operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) |

312 | { return __x.c < __y.c; } |

313 | |

314 | /// Based on operator== |

315 | template<typename _Tp, typename _Seq> |

316 | inline bool |

317 | operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) |

318 | { return !(__x == __y); } |

319 | |

320 | /// Based on operator< |

321 | template<typename _Tp, typename _Seq> |

322 | inline bool |

323 | operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) |

324 | { return __y < __x; } |

325 | |

326 | /// Based on operator< |

327 | template<typename _Tp, typename _Seq> |

328 | inline bool |

329 | operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) |

330 | { return !(__y < __x); } |

331 | |

332 | /// Based on operator< |

333 | template<typename _Tp, typename _Seq> |

334 | inline bool |

335 | operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) |

336 | { return !(__x < __y); } |

337 | |

338 | #if __cplusplus >= 201103L |

339 | template<typename _Tp, typename _Seq> |

340 | inline |

341 | #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 |

342 | // Constrained free swap overload, see p0185r1 |

343 | typename enable_if<__is_swappable<_Seq>::value>::type |

344 | #else |

345 | void |

346 | #endif |

347 | swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y) |

348 | noexcept(noexcept(__x.swap(__y))) |

349 | { __x.swap(__y); } |

350 | |

351 | template<typename _Tp, typename _Seq, typename _Alloc> |

352 | struct uses_allocator<stack<_Tp, _Seq>, _Alloc> |

353 | : public uses_allocator<_Seq, _Alloc>::type { }; |

354 | #endif // __cplusplus >= 201103L |

355 | |

356 | _GLIBCXX_END_NAMESPACE_VERSION |

357 | } // namespace |

358 | |

359 | #endif /* _STL_STACK_H */ |

360 |