388 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP_STACK11#define _LIBCPP_STACK12 13/*14 stack synopsis15 16namespace std17{18 19template <class T, class Container = deque<T>>20class stack21{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++2345 template<container-compatible-range<T> R> stack(from_range_t, R&& rg); // since C++2346 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++2353 template<container-compatible-range<T> R, class Alloc>54 stack(from_range_t, R&& rg, const Alloc&); // since C++2355 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++2365 template <class... Args> reference emplace(Args&&... args); // reference in C++1766 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++1773 74template<class InputIterator>75 stack(InputIterator, InputIterator) -> stack<iter-value-type<InputIterator>>; // since C++2376 77template<ranges::input_range R>78 stack(from_range_t, R&&) -> stack<ranges::range_value_t<R>>; // since C++2379 80template<class Container, class Allocator>81 stack(Container, Allocator) -> stack<typename Container::value_type, Container>; // C++1782 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++2387 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++2391 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++20107 108template <class T, class Container>109 void swap(stack<T, Container>& x, stack<T, Container>& y)110 noexcept(noexcept(x.swap(y)));111 112} // std113 114*/115 116#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)117# include <__cxx03/stack>118#else119# include <__algorithm/ranges_copy.h>120# include <__config>121# include <__fwd/stack.h>122# include <__iterator/back_insert_iterator.h>123# include <__iterator/iterator_traits.h>124# include <__memory/uses_allocator.h>125# include <__ranges/access.h>126# include <__ranges/concepts.h>127# include <__ranges/container_compatible_range.h>128# include <__ranges/from_range.h>129# include <__type_traits/is_same.h>130# include <__utility/forward.h>131# include <deque>132# include <version>133 134// standard-mandated includes135 136// [stack.syn]137# include <compare>138# include <initializer_list>139 140# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)141# pragma GCC system_header142# endif143 144_LIBCPP_PUSH_MACROS145# include <__undef_macros>146 147_LIBCPP_BEGIN_NAMESPACE_STD148 149template <class _Tp, class _Container>150_LIBCPP_HIDE_FROM_ABI bool operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);151 152template <class _Tp, class _Container>153_LIBCPP_HIDE_FROM_ABI bool operator<(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);154 155template <class _Tp, class _Container /*= deque<_Tp>*/>156class stack {157public:158 typedef _Container container_type;159 typedef typename container_type::value_type value_type;160 typedef typename container_type::reference reference;161 typedef typename container_type::const_reference const_reference;162 typedef typename container_type::size_type size_type;163 static_assert(is_same<_Tp, value_type>::value, "");164 165protected:166 container_type c;167 168public:169 _LIBCPP_HIDE_FROM_ABI stack() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {}170 171 _LIBCPP_HIDE_FROM_ABI stack(const stack& __q) : c(__q.c) {}172 173 _LIBCPP_HIDE_FROM_ABI stack& operator=(const stack& __q) {174 c = __q.c;175 return *this;176 }177 178# ifndef _LIBCPP_CXX03_LANG179 _LIBCPP_HIDE_FROM_ABI stack(stack&& __q) noexcept(is_nothrow_move_constructible<container_type>::value)180 : c(std::move(__q.c)) {}181 182 _LIBCPP_HIDE_FROM_ABI stack& operator=(stack&& __q) noexcept(is_nothrow_move_assignable<container_type>::value) {183 c = std::move(__q.c);184 return *this;185 }186 187 _LIBCPP_HIDE_FROM_ABI explicit stack(container_type&& __c) : c(std::move(__c)) {}188# endif // _LIBCPP_CXX03_LANG189 190 _LIBCPP_HIDE_FROM_ABI explicit stack(const container_type& __c) : c(__c) {}191 192 template <class _Alloc>193 _LIBCPP_HIDE_FROM_ABI explicit stack(const _Alloc& __a,194 __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)195 : c(__a) {}196 template <class _Alloc>197 _LIBCPP_HIDE_FROM_ABI198 stack(const container_type& __c, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)199 : c(__c, __a) {}200 template <class _Alloc>201 _LIBCPP_HIDE_FROM_ABI202 stack(const stack& __s, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)203 : c(__s.c, __a) {}204# ifndef _LIBCPP_CXX03_LANG205 template <class _Alloc>206 _LIBCPP_HIDE_FROM_ABI207 stack(container_type&& __c, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)208 : c(std::move(__c), __a) {}209 template <class _Alloc>210 _LIBCPP_HIDE_FROM_ABI211 stack(stack&& __s, const _Alloc& __a, __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)212 : c(std::move(__s.c), __a) {}213# endif // _LIBCPP_CXX03_LANG214 215# if _LIBCPP_STD_VER >= 23216 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>217 _LIBCPP_HIDE_FROM_ABI stack(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}218 219 template <_ContainerCompatibleRange<_Tp> _Range>220 _LIBCPP_HIDE_FROM_ABI stack(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}221 222 template <class _InputIterator,223 class _Alloc,224 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,225 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>226 _LIBCPP_HIDE_FROM_ABI stack(_InputIterator __first, _InputIterator __last, const _Alloc& __alloc)227 : c(__first, __last, __alloc) {}228 229 template <_ContainerCompatibleRange<_Tp> _Range,230 class _Alloc,231 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>232 _LIBCPP_HIDE_FROM_ABI stack(from_range_t, _Range&& __range, const _Alloc& __alloc)233 : c(from_range, std::forward<_Range>(__range), __alloc) {}234 235# endif236 237 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }238 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }239 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI reference top() { return c.back(); }240 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.back(); }241 242 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); }243# ifndef _LIBCPP_CXX03_LANG244 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); }245 246# if _LIBCPP_STD_VER >= 23247 template <_ContainerCompatibleRange<_Tp> _Range>248 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {249 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {250 c.append_range(std::forward<_Range>(__range));251 } else {252 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));253 }254 }255# endif256 257 template <class... _Args>258 _LIBCPP_HIDE_FROM_ABI259# if _LIBCPP_STD_VER >= 17260 decltype(auto)261 emplace(_Args&&... __args) {262 return c.emplace_back(std::forward<_Args>(__args)...);263 }264# else265 void266 emplace(_Args&&... __args) {267 c.emplace_back(std::forward<_Args>(__args)...);268 }269# endif270# endif // _LIBCPP_CXX03_LANG271 272 _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_back(); }273 274 _LIBCPP_HIDE_FROM_ABI void swap(stack& __s) _NOEXCEPT_(__is_nothrow_swappable_v<container_type>) {275 using std::swap;276 swap(c, __s.c);277 }278 279 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }280 281 template <class _T1, class _OtherContainer>282 friend _LIBCPP_HIDE_FROM_ABI bool283 operator==(const stack<_T1, _OtherContainer>& __x, const stack<_T1, _OtherContainer>& __y);284 285 template <class _T1, class _OtherContainer>286 friend _LIBCPP_HIDE_FROM_ABI bool287 operator<(const stack<_T1, _OtherContainer>& __x, const stack<_T1, _OtherContainer>& __y);288 289# if _LIBCPP_STD_VER >= 20290 template <class _T1, three_way_comparable _OtherContainer>291 friend _LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_OtherContainer>292 operator<=>(const stack<_T1, _OtherContainer>& __x, const stack<_T1, _OtherContainer>& __y);293# endif294};295 296# if _LIBCPP_STD_VER >= 17297template <class _Container, class = enable_if_t<!__is_allocator_v<_Container>>>298stack(_Container) -> stack<typename _Container::value_type, _Container>;299 300template <class _Container,301 class _Alloc,302 class = enable_if_t<!__is_allocator_v<_Container>>,303 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >304stack(_Container, _Alloc) -> stack<typename _Container::value_type, _Container>;305# endif306 307# if _LIBCPP_STD_VER >= 23308template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>309stack(_InputIterator, _InputIterator) -> stack<__iterator_value_type<_InputIterator>>;310 311template <ranges::input_range _Range>312stack(from_range_t, _Range&&) -> stack<ranges::range_value_t<_Range>>;313 314template <class _InputIterator,315 class _Alloc,316 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,317 __enable_if_t<__is_allocator_v<_Alloc>, int> = 0>318stack(_InputIterator, _InputIterator, _Alloc)319 -> stack<__iterator_value_type<_InputIterator>, deque<__iterator_value_type<_InputIterator>, _Alloc>>;320 321template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator_v<_Alloc>, int> = 0>322stack(from_range_t, _Range&&, _Alloc)323 -> stack<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;324 325# endif326 327template <class _Tp, class _Container>328inline _LIBCPP_HIDE_FROM_ABI bool operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) {329 return __x.c == __y.c;330}331 332template <class _Tp, class _Container>333inline _LIBCPP_HIDE_FROM_ABI bool operator<(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) {334 return __x.c < __y.c;335}336 337template <class _Tp, class _Container>338inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) {339 return !(__x == __y);340}341 342template <class _Tp, class _Container>343inline _LIBCPP_HIDE_FROM_ABI bool operator>(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) {344 return __y < __x;345}346 347template <class _Tp, class _Container>348inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) {349 return !(__x < __y);350}351 352template <class _Tp, class _Container>353inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) {354 return !(__y < __x);355}356 357# if _LIBCPP_STD_VER >= 20358 359template <class _Tp, three_way_comparable _Container>360_LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>361operator<=>(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) {362 return __x.c <=> __y.c;363}364 365# endif366 367template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0>368inline _LIBCPP_HIDE_FROM_ABI void swap(stack<_Tp, _Container>& __x, stack<_Tp, _Container>& __y)369 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {370 __x.swap(__y);371}372 373template <class _Tp, class _Container, class _Alloc>374struct uses_allocator<stack<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> {};375 376_LIBCPP_END_NAMESPACE_STD377 378_LIBCPP_POP_MACROS379 380# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20381# include <concepts>382# include <functional>383# include <type_traits>384# endif385#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)386 387#endif // _LIBCPP_STACK388