blob: a4a76e5178b40fe7f44ff32eadce8d052687e29b [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001// -*- C++ -*-
Louis Dionne9bd93882021-11-17 16:25:01 -05002//===----------------------------------------------------------------------===//
Howard Hinnantc51e1022010-05-11 19:42:16 +00003//
Chandler Carruthd2012102019-01-19 10:56:40 +00004// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
Howard Hinnantc51e1022010-05-11 19:42:16 +00007//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_STACK
11#define _LIBCPP_STACK
12
13/*
14 stack synopsis
15
16namespace std
17{
18
19template <class T, class Container = deque<T>>
20class stack
21{
22public:
23 typedef Container container_type;
24 typedef typename container_type::value_type value_type;
25 typedef typename container_type::reference reference;
26 typedef typename container_type::const_reference const_reference;
27 typedef typename container_type::size_type size_type;
28
29protected:
30 container_type c;
31
32public:
Howard Hinnante0da4a12011-06-04 22:09:19 +000033 stack() = default;
34 ~stack() = default;
35
36 stack(const stack& q) = default;
37 stack(stack&& q) = default;
38
39 stack& operator=(const stack& q) = default;
40 stack& operator=(stack&& q) = default;
41
Howard Hinnantc51e1022010-05-11 19:42:16 +000042 explicit stack(const container_type& c);
43 explicit stack(container_type&& c);
Nikolas Klauserf0b3d872022-01-06 12:36:07 +010044 template <class InputIterator> stack(InputIterator first, InputIterator last); // since C++23
Howard Hinnantc51e1022010-05-11 19:42:16 +000045 template <class Alloc> explicit stack(const Alloc& a);
46 template <class Alloc> stack(const container_type& c, const Alloc& a);
47 template <class Alloc> stack(container_type&& c, const Alloc& a);
Howard Hinnante0da4a12011-06-04 22:09:19 +000048 template <class Alloc> stack(const stack& c, const Alloc& a);
Howard Hinnantc51e1022010-05-11 19:42:16 +000049 template <class Alloc> stack(stack&& c, const Alloc& a);
Nikolas Klauserf0b3d872022-01-06 12:36:07 +010050 template<class InputIterator, class Alloc>
51 stack(InputIterator first, InputIterator last, const Alloc&); // since C++23
Howard Hinnantc51e1022010-05-11 19:42:16 +000052
53 bool empty() const;
54 size_type size() const;
55 reference top();
56 const_reference top() const;
57
58 void push(const value_type& x);
59 void push(value_type&& x);
Marshall Clowea52cc42017-01-24 23:09:12 +000060 template <class... Args> reference emplace(Args&&... args); // reference in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +000061 void pop();
62
Eric Fiselier6bfed252016-04-21 23:38:59 +000063 void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>)
Howard Hinnantc51e1022010-05-11 19:42:16 +000064};
65
Marshall Clow592d9952018-05-22 01:57:53 +000066template<class Container>
67 stack(Container) -> stack<typename Container::value_type, Container>; // C++17
Louis Dionne173f29e2019-05-29 16:01:36 +000068
Nikolas Klauserf0b3d872022-01-06 12:36:07 +010069template<class InputIterator>
70 stack(InputIterator, InputIterator) -> stack<iter-value-type<InputIterator>>; // since C++23
71
Louis Dionne173f29e2019-05-29 16:01:36 +000072template<class Container, class Allocator>
Marshall Clow592d9952018-05-22 01:57:53 +000073 stack(Container, Allocator) -> stack<typename Container::value_type, Container>; // C++17
74
Nikolas Klauserf0b3d872022-01-06 12:36:07 +010075template<class InputIterator, class Allocator>
76 stack(InputIterator, InputIterator, Allocator)
77 -> stack<iter-value-type<InputIterator>,
78 deque<iter-value-type<InputIterator>, Allocator>>; // since C++23
79
Howard Hinnantc51e1022010-05-11 19:42:16 +000080template <class T, class Container>
81 bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
82template <class T, class Container>
83 bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
84template <class T, class Container>
85 bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
86template <class T, class Container>
87 bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
88template <class T, class Container>
89 bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
90template <class T, class Container>
91 bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
92
93template <class T, class Container>
Howard Hinnante0da4a12011-06-04 22:09:19 +000094 void swap(stack<T, Container>& x, stack<T, Container>& y)
95 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +000096
97} // std
98
99*/
100
Louis Dionneb4fce352022-03-25 12:55:36 -0400101#include <__assert> // all public C++ headers provide the assertion handler
Howard Hinnantc51e1022010-05-11 19:42:16 +0000102#include <__config>
Nikolas Klauserf0b3d872022-01-06 12:36:07 +0100103#include <__iterator/iterator_traits.h>
Christopher Di Bella55d7a822021-07-01 09:25:35 -0400104#include <__memory/uses_allocator.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +0000105#include <__utility/forward.h>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000106#include <deque>
Nikolas Klauserf0b3d872022-01-06 12:36:07 +0100107#include <type_traits>
Mark de Weverce8f12c2021-12-22 18:14:14 +0100108#include <version>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000109
Mark de Weverf6df9e82022-08-20 10:34:26 +0200110#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
Louis Dionne22355cc2022-06-27 15:53:41 -0400111# include <functional>
112#endif
113
Nikolas Klausera0e0edb2022-06-16 22:43:46 +0200114// standard-mandated includes
115#include <compare>
116#include <initializer_list>
117
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000118#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Arthur O'Dwyer6eeaa002022-02-01 20:16:40 -0500119# pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000120#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000121
122_LIBCPP_BEGIN_NAMESPACE_STD
123
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000124template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS stack;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000125
126template <class _Tp, class _Container>
Howard Hinnanta54386e2012-09-14 00:39:16 +0000127_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000128bool
129operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);
130
131template <class _Tp, class _Container>
Howard Hinnanta54386e2012-09-14 00:39:16 +0000132_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000133bool
134operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);
135
Marshall Clow9e1b8452015-02-18 17:51:56 +0000136template <class _Tp, class _Container /*= deque<_Tp>*/>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000137class _LIBCPP_TEMPLATE_VIS stack
Howard Hinnantc51e1022010-05-11 19:42:16 +0000138{
139public:
140 typedef _Container container_type;
141 typedef typename container_type::value_type value_type;
142 typedef typename container_type::reference reference;
143 typedef typename container_type::const_reference const_reference;
144 typedef typename container_type::size_type size_type;
Marshall Clowb8825f02016-03-14 17:58:11 +0000145 static_assert((is_same<_Tp, value_type>::value), "" );
Louis Dionne173f29e2019-05-29 16:01:36 +0000146
Howard Hinnantc51e1022010-05-11 19:42:16 +0000147protected:
148 container_type c;
149
150public:
Howard Hinnant186dca82010-09-23 17:31:07 +0000151 _LIBCPP_INLINE_VISIBILITY
Howard Hinnante0da4a12011-06-04 22:09:19 +0000152 stack()
153 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
154 : c() {}
155
156 _LIBCPP_INLINE_VISIBILITY
157 stack(const stack& __q) : c(__q.c) {}
158
Eric Fiselier33cc2f02017-04-18 21:16:26 +0000159 _LIBCPP_INLINE_VISIBILITY
160 stack& operator=(const stack& __q) {c = __q.c; return *this;}
161
162
163#ifndef _LIBCPP_CXX03_LANG
Howard Hinnante0da4a12011-06-04 22:09:19 +0000164 _LIBCPP_INLINE_VISIBILITY
165 stack(stack&& __q)
166 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000167 : c(_VSTD::move(__q.c)) {}
Howard Hinnante0da4a12011-06-04 22:09:19 +0000168
169 _LIBCPP_INLINE_VISIBILITY
Howard Hinnante0da4a12011-06-04 22:09:19 +0000170 stack& operator=(stack&& __q)
171 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000172 {c = _VSTD::move(__q.c); return *this;}
Eric Fiselier33cc2f02017-04-18 21:16:26 +0000173
174 _LIBCPP_INLINE_VISIBILITY
175 explicit stack(container_type&& __c) : c(_VSTD::move(__c)) {}
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400176#endif // _LIBCPP_CXX03_LANG
Howard Hinnante0da4a12011-06-04 22:09:19 +0000177
Howard Hinnant186dca82010-09-23 17:31:07 +0000178 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000179 explicit stack(const container_type& __c) : c(__c) {}
Eric Fiselier33cc2f02017-04-18 21:16:26 +0000180
Howard Hinnantc51e1022010-05-11 19:42:16 +0000181 template <class _Alloc>
Howard Hinnant186dca82010-09-23 17:31:07 +0000182 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000183 explicit stack(const _Alloc& __a,
Louis Dionne9ce598d2021-09-08 09:14:43 -0400184 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000185 : c(__a) {}
186 template <class _Alloc>
Howard Hinnant186dca82010-09-23 17:31:07 +0000187 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000188 stack(const container_type& __c, const _Alloc& __a,
Louis Dionne9ce598d2021-09-08 09:14:43 -0400189 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000190 : c(__c, __a) {}
191 template <class _Alloc>
Howard Hinnant186dca82010-09-23 17:31:07 +0000192 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000193 stack(const stack& __s, const _Alloc& __a,
Louis Dionne9ce598d2021-09-08 09:14:43 -0400194 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000195 : c(__s.c, __a) {}
Eric Fiselier33cc2f02017-04-18 21:16:26 +0000196#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000197 template <class _Alloc>
Howard Hinnant186dca82010-09-23 17:31:07 +0000198 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000199 stack(container_type&& __c, const _Alloc& __a,
Louis Dionne9ce598d2021-09-08 09:14:43 -0400200 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000201 : c(_VSTD::move(__c), __a) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000202 template <class _Alloc>
Howard Hinnant186dca82010-09-23 17:31:07 +0000203 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000204 stack(stack&& __s, const _Alloc& __a,
Louis Dionne9ce598d2021-09-08 09:14:43 -0400205 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000206 : c(_VSTD::move(__s.c), __a) {}
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400207#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000208
Nikolas Klauserf0b3d872022-01-06 12:36:07 +0100209#if _LIBCPP_STD_VER > 20
210 template <class _InputIterator,
211 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>>
212 _LIBCPP_HIDE_FROM_ABI
213 stack(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
214
215 template <class _InputIterator,
216 class _Alloc,
217 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
218 class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>>
219 _LIBCPP_HIDE_FROM_ABI
220 stack(_InputIterator __first, _InputIterator __last, const _Alloc& __alloc) : c(__first, __last, __alloc) {}
221#endif
222
Marshall Clow425f5752017-11-15 05:51:26 +0000223 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000224 bool empty() const {return c.empty();}
Howard Hinnant186dca82010-09-23 17:31:07 +0000225 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000226 size_type size() const {return c.size();}
Howard Hinnant186dca82010-09-23 17:31:07 +0000227 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000228 reference top() {return c.back();}
Howard Hinnant186dca82010-09-23 17:31:07 +0000229 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000230 const_reference top() const {return c.back();}
231
Howard Hinnant186dca82010-09-23 17:31:07 +0000232 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000233 void push(const value_type& __v) {c.push_back(__v);}
Eric Fiselier33cc2f02017-04-18 21:16:26 +0000234#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant186dca82010-09-23 17:31:07 +0000235 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000236 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));}
Eric Fiselier33cc2f02017-04-18 21:16:26 +0000237
Howard Hinnant186dca82010-09-23 17:31:07 +0000238 template <class... _Args>
239 _LIBCPP_INLINE_VISIBILITY
Marshall Clowea52cc42017-01-24 23:09:12 +0000240#if _LIBCPP_STD_VER > 14
Marshall Clow88746852018-01-24 22:42:25 +0000241 decltype(auto) emplace(_Args&&... __args)
Eric Fiselier34ba5b92016-07-21 03:20:17 +0000242 { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
Marshall Clowea52cc42017-01-24 23:09:12 +0000243#else
244 void emplace(_Args&&... __args)
245 { c.emplace_back(_VSTD::forward<_Args>(__args)...);}
246#endif
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400247#endif // _LIBCPP_CXX03_LANG
Eric Fiselier33cc2f02017-04-18 21:16:26 +0000248
Howard Hinnant186dca82010-09-23 17:31:07 +0000249 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000250 void pop() {c.pop_back();}
251
Howard Hinnant186dca82010-09-23 17:31:07 +0000252 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000253 void swap(stack& __s)
Howard Hinnante0da4a12011-06-04 22:09:19 +0000254 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000255 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000256 using _VSTD::swap;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000257 swap(c, __s.c);
258 }
259
260 template <class T1, class _C1>
261 friend
262 bool
263 operator==(const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000264
Howard Hinnantc51e1022010-05-11 19:42:16 +0000265 template <class T1, class _C1>
266 friend
267 bool
268 operator< (const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
269};
270
Nikolas Klauserf0b3d872022-01-06 12:36:07 +0100271#if _LIBCPP_STD_VER > 14
Marshall Clow592d9952018-05-22 01:57:53 +0000272template<class _Container,
Louis Dionne25547162021-08-17 12:26:09 -0400273 class = enable_if_t<!__is_allocator<_Container>::value>
Marshall Clow592d9952018-05-22 01:57:53 +0000274>
275stack(_Container)
276 -> stack<typename _Container::value_type, _Container>;
Louis Dionne173f29e2019-05-29 16:01:36 +0000277
Marshall Clow592d9952018-05-22 01:57:53 +0000278template<class _Container,
279 class _Alloc,
Louis Dionne25547162021-08-17 12:26:09 -0400280 class = enable_if_t<!__is_allocator<_Container>::value>,
281 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
Louis Dionne173f29e2019-05-29 16:01:36 +0000282 >
Marshall Clow592d9952018-05-22 01:57:53 +0000283stack(_Container, _Alloc)
284 -> stack<typename _Container::value_type, _Container>;
285#endif
286
Nikolas Klauserf0b3d872022-01-06 12:36:07 +0100287#if _LIBCPP_STD_VER > 20
288template<class _InputIterator,
289 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>>
290stack(_InputIterator, _InputIterator)
291 -> stack<__iter_value_type<_InputIterator>>;
292
293template<class _InputIterator,
294 class _Alloc,
295 class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
296 class = __enable_if_t<__is_allocator<_Alloc>::value>>
297stack(_InputIterator, _InputIterator, _Alloc)
298 -> stack<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
299#endif
300
Howard Hinnantc51e1022010-05-11 19:42:16 +0000301template <class _Tp, class _Container>
Howard Hinnant186dca82010-09-23 17:31:07 +0000302inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000303bool
304operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
305{
306 return __x.c == __y.c;
307}
308
309template <class _Tp, class _Container>
Howard Hinnant186dca82010-09-23 17:31:07 +0000310inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000311bool
312operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
313{
314 return __x.c < __y.c;
315}
316
317template <class _Tp, class _Container>
Howard Hinnant186dca82010-09-23 17:31:07 +0000318inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000319bool
320operator!=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
321{
322 return !(__x == __y);
323}
324
325template <class _Tp, class _Container>
Howard Hinnant186dca82010-09-23 17:31:07 +0000326inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000327bool
328operator> (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
329{
330 return __y < __x;
331}
332
333template <class _Tp, class _Container>
Howard Hinnant186dca82010-09-23 17:31:07 +0000334inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000335bool
336operator>=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
337{
338 return !(__x < __y);
339}
340
341template <class _Tp, class _Container>
Howard Hinnant186dca82010-09-23 17:31:07 +0000342inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000343bool
344operator<=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
345{
346 return !(__y < __x);
347}
348
349template <class _Tp, class _Container>
Howard Hinnant186dca82010-09-23 17:31:07 +0000350inline _LIBCPP_INLINE_VISIBILITY
Louis Dionne9ce598d2021-09-08 09:14:43 -0400351__enable_if_t<__is_swappable<_Container>::value, void>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000352swap(stack<_Tp, _Container>& __x, stack<_Tp, _Container>& __y)
Howard Hinnante0da4a12011-06-04 22:09:19 +0000353 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000354{
355 __x.swap(__y);
356}
357
358template <class _Tp, class _Container, class _Alloc>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000359struct _LIBCPP_TEMPLATE_VIS uses_allocator<stack<_Tp, _Container>, _Alloc>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000360 : public uses_allocator<_Container, _Alloc>
361{
362};
363
364_LIBCPP_END_NAMESPACE_STD
365
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400366#endif // _LIBCPP_STACK