1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// 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 7// 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: 33 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 42 explicit stack(const container_type& c); 43 explicit stack(container_type&& c); 44 template <class InputIterator> stack(InputIterator first, InputIterator last); // since C++23 45 template<container-compatible-range<T> R> stack(from_range_t, R&& rg); // since C++23 46 template <class Alloc> explicit stack(const Alloc& a); 47 template <class Alloc> stack(const container_type& c, const Alloc& a); 48 template <class Alloc> stack(container_type&& c, const Alloc& a); 49 template <class Alloc> stack(const stack& c, const Alloc& a); 50 template <class Alloc> stack(stack&& c, const Alloc& a); 51 template<class InputIterator, class Alloc> 52 stack(InputIterator first, InputIterator last, const Alloc&); // since C++23 53 template<container-compatible-range<T> R, class Alloc> 54 stack(from_range_t, R&& rg, const Alloc&); // since C++23 55 56 bool empty() const; 57 size_type size() const; 58 reference top(); 59 const_reference top() const; 60 61 void push(const value_type& x); 62 void push(value_type&& x); 63 template<container-compatible-range<T> R> 64 void push_range(R&& rg); // C++23 65 template <class... Args> reference emplace(Args&&... args); // reference in C++17 66 void pop(); 67 68 void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>) 69}; 70 71template<class Container> 72 stack(Container) -> stack<typename Container::value_type, Container>; // C++17 73 74template<class InputIterator> 75 stack(InputIterator, InputIterator) -> stack<iter-value-type<InputIterator>>; // since C++23 76 77template<ranges::input_range R> 78 stack(from_range_t, R&&) -> stack<ranges::range_value_t<R>>; // since C++23 79 80template<class Container, class Allocator> 81 stack(Container, Allocator) -> stack<typename Container::value_type, Container>; // C++17 82 83template<class InputIterator, class Allocator> 84 stack(InputIterator, InputIterator, Allocator) 85 -> stack<iter-value-type<InputIterator>, 86 deque<iter-value-type<InputIterator>, Allocator>>; // since C++23 87 88template<ranges::input_range R, class Allocator> 89 stack(from_range_t, R&&, Allocator) 90 -> stack<ranges::range_value_t<R>, deque<ranges::range_value_t<R>, Allocator>>; // since C++23 91 92template <class T, class Container> 93 bool operator==(const stack<T, Container>& x, const stack<T, Container>& y); 94template <class T, class Container> 95 bool operator< (const stack<T, Container>& x, const stack<T, Container>& y); 96template <class T, class Container> 97 bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y); 98template <class T, class Container> 99 bool operator> (const stack<T, Container>& x, const stack<T, Container>& y); 100template <class T, class Container> 101 bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y); 102template <class T, class Container> 103 bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y); 104template<class T, three_way_comparable Container> 105 compare_three_way_result_t<Container> 106 operator<=>(const stack<T, Container>& x, const stack<T, Container>& y); // since C++20 107 108template <class T, class Container> 109 void swap(stack<T, Container>& x, stack<T, Container>& y) 110 noexcept(noexcept(x.swap(y))); 111 112} // std 113 114*/ 115 116#include <__algorithm/ranges_copy.h> 117#include <__assert> // all public C++ headers provide the assertion handler 118#include <__config> 119#include <__iterator/back_insert_iterator.h> 120#include <__iterator/iterator_traits.h> 121#include <__memory/uses_allocator.h> 122#include <__ranges/access.h> 123#include <__ranges/concepts.h> 124#include <__ranges/container_compatible_range.h> 125#include <__ranges/from_range.h> 126#include <__type_traits/is_same.h> 127#include <__utility/forward.h> 128#include <deque> 129#include <version> 130 131// standard-mandated includes 132 133// [stack.syn] 134#include <compare> 135#include <initializer_list> 136 137#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 138# pragma GCC system_header 139#endif 140 141_LIBCPP_BEGIN_NAMESPACE_STD 142 143template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS stack; 144 145template <class _Tp, class _Container> 146_LIBCPP_INLINE_VISIBILITY 147bool 148operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y); 149 150template <class _Tp, class _Container> 151_LIBCPP_INLINE_VISIBILITY 152bool 153operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y); 154 155template <class _Tp, class _Container /*= deque<_Tp>*/> 156class _LIBCPP_TEMPLATE_VIS stack 157{ 158public: 159 typedef _Container container_type; 160 typedef typename container_type::value_type value_type; 161 typedef typename container_type::reference reference; 162 typedef typename container_type::const_reference const_reference; 163 typedef typename container_type::size_type size_type; 164 static_assert((is_same<_Tp, value_type>::value), "" ); 165 166protected: 167 container_type c; 168 169public: 170 _LIBCPP_INLINE_VISIBILITY 171 stack() 172 _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) 173 : c() {} 174 175 _LIBCPP_INLINE_VISIBILITY 176 stack(const stack& __q) : c(__q.c) {} 177 178 _LIBCPP_INLINE_VISIBILITY 179 stack& operator=(const stack& __q) {c = __q.c; return *this;} 180 181 182#ifndef _LIBCPP_CXX03_LANG 183 _LIBCPP_INLINE_VISIBILITY 184 stack(stack&& __q) 185 _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value) 186 : c(_VSTD::move(__q.c)) {} 187 188 _LIBCPP_INLINE_VISIBILITY 189 stack& operator=(stack&& __q) 190 _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value) 191 {c = _VSTD::move(__q.c); return *this;} 192 193 _LIBCPP_INLINE_VISIBILITY 194 explicit stack(container_type&& __c) : c(_VSTD::move(__c)) {} 195#endif // _LIBCPP_CXX03_LANG 196 197 _LIBCPP_INLINE_VISIBILITY 198 explicit stack(const container_type& __c) : c(__c) {} 199 200 template <class _Alloc> 201 _LIBCPP_INLINE_VISIBILITY 202 explicit stack(const _Alloc& __a, 203 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 204 : c(__a) {} 205 template <class _Alloc> 206 _LIBCPP_INLINE_VISIBILITY 207 stack(const container_type& __c, const _Alloc& __a, 208 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 209 : c(__c, __a) {} 210 template <class _Alloc> 211 _LIBCPP_INLINE_VISIBILITY 212 stack(const stack& __s, const _Alloc& __a, 213 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 214 : c(__s.c, __a) {} 215#ifndef _LIBCPP_CXX03_LANG 216 template <class _Alloc> 217 _LIBCPP_INLINE_VISIBILITY 218 stack(container_type&& __c, const _Alloc& __a, 219 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 220 : c(_VSTD::move(__c), __a) {} 221 template <class _Alloc> 222 _LIBCPP_INLINE_VISIBILITY 223 stack(stack&& __s, const _Alloc& __a, 224 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0) 225 : c(_VSTD::move(__s.c), __a) {} 226#endif // _LIBCPP_CXX03_LANG 227 228#if _LIBCPP_STD_VER >= 23 229 template <class _InputIterator, 230 class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>> 231 _LIBCPP_HIDE_FROM_ABI 232 stack(_InputIterator __first, _InputIterator __last) : c(__first, __last) {} 233 234 template <_ContainerCompatibleRange<_Tp> _Range> 235 _LIBCPP_HIDE_FROM_ABI 236 stack(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {} 237 238 template <class _InputIterator, 239 class _Alloc, 240 class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 241 class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>> 242 _LIBCPP_HIDE_FROM_ABI 243 stack(_InputIterator __first, _InputIterator __last, const _Alloc& __alloc) : c(__first, __last, __alloc) {} 244 245 template <_ContainerCompatibleRange<_Tp> _Range, 246 class _Alloc, 247 class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>> 248 _LIBCPP_HIDE_FROM_ABI 249 stack(from_range_t, _Range&& __range, const _Alloc& __alloc) 250 : c(from_range, std::forward<_Range>(__range), __alloc) {} 251 252#endif 253 254 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 255 bool empty() const {return c.empty();} 256 _LIBCPP_INLINE_VISIBILITY 257 size_type size() const {return c.size();} 258 _LIBCPP_INLINE_VISIBILITY 259 reference top() {return c.back();} 260 _LIBCPP_INLINE_VISIBILITY 261 const_reference top() const {return c.back();} 262 263 _LIBCPP_INLINE_VISIBILITY 264 void push(const value_type& __v) {c.push_back(__v);} 265#ifndef _LIBCPP_CXX03_LANG 266 _LIBCPP_INLINE_VISIBILITY 267 void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} 268 269#if _LIBCPP_STD_VER >= 23 270 template <_ContainerCompatibleRange<_Tp> _Range> 271 _LIBCPP_HIDE_FROM_ABI 272 void push_range(_Range&& __range) { 273 if constexpr (requires (container_type& __c) { 274 __c.append_range(std::forward<_Range>(__range)); 275 }) { 276 c.append_range(std::forward<_Range>(__range)); 277 } else { 278 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c)); 279 } 280 } 281#endif 282 283 template <class... _Args> 284 _LIBCPP_INLINE_VISIBILITY 285#if _LIBCPP_STD_VER >= 17 286 decltype(auto) emplace(_Args&&... __args) 287 { return c.emplace_back(_VSTD::forward<_Args>(__args)...);} 288#else 289 void emplace(_Args&&... __args) 290 { c.emplace_back(_VSTD::forward<_Args>(__args)...);} 291#endif 292#endif // _LIBCPP_CXX03_LANG 293 294 _LIBCPP_INLINE_VISIBILITY 295 void pop() {c.pop_back();} 296 297 _LIBCPP_INLINE_VISIBILITY 298 void swap(stack& __s) 299 _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) 300 { 301 using _VSTD::swap; 302 swap(c, __s.c); 303 } 304 305 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; } 306 307 template <class _T1, class _OtherContainer> 308 friend 309 bool 310 operator==(const stack<_T1, _OtherContainer>& __x, const stack<_T1, _OtherContainer>& __y); 311 312 template <class _T1, class _OtherContainer> 313 friend 314 bool 315 operator< (const stack<_T1, _OtherContainer>& __x, const stack<_T1, _OtherContainer>& __y); 316}; 317 318#if _LIBCPP_STD_VER >= 17 319template<class _Container, 320 class = enable_if_t<!__is_allocator<_Container>::value> 321> 322stack(_Container) 323 -> stack<typename _Container::value_type, _Container>; 324 325template<class _Container, 326 class _Alloc, 327 class = enable_if_t<!__is_allocator<_Container>::value>, 328 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> 329 > 330stack(_Container, _Alloc) 331 -> stack<typename _Container::value_type, _Container>; 332#endif 333 334#if _LIBCPP_STD_VER >= 23 335template<class _InputIterator, 336 class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>> 337stack(_InputIterator, _InputIterator) 338 -> stack<__iter_value_type<_InputIterator>>; 339 340template <ranges::input_range _Range> 341stack(from_range_t, _Range&&) -> stack<ranges::range_value_t<_Range>>; 342 343template<class _InputIterator, 344 class _Alloc, 345 class = __enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 346 class = __enable_if_t<__is_allocator<_Alloc>::value>> 347stack(_InputIterator, _InputIterator, _Alloc) 348 -> stack<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>; 349 350template <ranges::input_range _Range, 351 class _Alloc, 352 class = __enable_if_t<__is_allocator<_Alloc>::value>> 353stack(from_range_t, _Range&&, _Alloc) 354 -> stack<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>; 355 356#endif 357 358template <class _Tp, class _Container> 359inline _LIBCPP_INLINE_VISIBILITY 360bool 361operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 362{ 363 return __x.c == __y.c; 364} 365 366template <class _Tp, class _Container> 367inline _LIBCPP_INLINE_VISIBILITY 368bool 369operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 370{ 371 return __x.c < __y.c; 372} 373 374template <class _Tp, class _Container> 375inline _LIBCPP_INLINE_VISIBILITY 376bool 377operator!=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 378{ 379 return !(__x == __y); 380} 381 382template <class _Tp, class _Container> 383inline _LIBCPP_INLINE_VISIBILITY 384bool 385operator> (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 386{ 387 return __y < __x; 388} 389 390template <class _Tp, class _Container> 391inline _LIBCPP_INLINE_VISIBILITY 392bool 393operator>=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 394{ 395 return !(__x < __y); 396} 397 398template <class _Tp, class _Container> 399inline _LIBCPP_INLINE_VISIBILITY 400bool 401operator<=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 402{ 403 return !(__y < __x); 404} 405 406#if _LIBCPP_STD_VER >= 20 407 408template <class _Tp, three_way_comparable _Container> 409_LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container> 410operator<=>(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) { 411 // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors 412 return __x.__get_container() <=> __y.__get_container(); 413} 414 415#endif 416 417template <class _Tp, class _Container> 418inline _LIBCPP_INLINE_VISIBILITY 419__enable_if_t<__is_swappable<_Container>::value, void> 420swap(stack<_Tp, _Container>& __x, stack<_Tp, _Container>& __y) 421 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 422{ 423 __x.swap(__y); 424} 425 426template <class _Tp, class _Container, class _Alloc> 427struct _LIBCPP_TEMPLATE_VIS uses_allocator<stack<_Tp, _Container>, _Alloc> 428 : public uses_allocator<_Container, _Alloc> 429{ 430}; 431 432_LIBCPP_END_NAMESPACE_STD 433 434#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 435# include <concepts> 436# include <functional> 437# include <type_traits> 438#endif 439 440#endif // _LIBCPP_STACK 441