1*0b57cec5SDimitry Andric// -*- C++ -*- 2*0b57cec5SDimitry Andric//===---------------------------- stack -----------------------------------===// 3*0b57cec5SDimitry Andric// 4*0b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5*0b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 6*0b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7*0b57cec5SDimitry Andric// 8*0b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 9*0b57cec5SDimitry Andric 10*0b57cec5SDimitry Andric#ifndef _LIBCPP_STACK 11*0b57cec5SDimitry Andric#define _LIBCPP_STACK 12*0b57cec5SDimitry Andric 13*0b57cec5SDimitry Andric/* 14*0b57cec5SDimitry Andric stack synopsis 15*0b57cec5SDimitry Andric 16*0b57cec5SDimitry Andricnamespace std 17*0b57cec5SDimitry Andric{ 18*0b57cec5SDimitry Andric 19*0b57cec5SDimitry Andrictemplate <class T, class Container = deque<T>> 20*0b57cec5SDimitry Andricclass stack 21*0b57cec5SDimitry Andric{ 22*0b57cec5SDimitry Andricpublic: 23*0b57cec5SDimitry Andric typedef Container container_type; 24*0b57cec5SDimitry Andric typedef typename container_type::value_type value_type; 25*0b57cec5SDimitry Andric typedef typename container_type::reference reference; 26*0b57cec5SDimitry Andric typedef typename container_type::const_reference const_reference; 27*0b57cec5SDimitry Andric typedef typename container_type::size_type size_type; 28*0b57cec5SDimitry Andric 29*0b57cec5SDimitry Andricprotected: 30*0b57cec5SDimitry Andric container_type c; 31*0b57cec5SDimitry Andric 32*0b57cec5SDimitry Andricpublic: 33*0b57cec5SDimitry Andric stack() = default; 34*0b57cec5SDimitry Andric ~stack() = default; 35*0b57cec5SDimitry Andric 36*0b57cec5SDimitry Andric stack(const stack& q) = default; 37*0b57cec5SDimitry Andric stack(stack&& q) = default; 38*0b57cec5SDimitry Andric 39*0b57cec5SDimitry Andric stack& operator=(const stack& q) = default; 40*0b57cec5SDimitry Andric stack& operator=(stack&& q) = default; 41*0b57cec5SDimitry Andric 42*0b57cec5SDimitry Andric explicit stack(const container_type& c); 43*0b57cec5SDimitry Andric explicit stack(container_type&& c); 44*0b57cec5SDimitry Andric template <class Alloc> explicit stack(const Alloc& a); 45*0b57cec5SDimitry Andric template <class Alloc> stack(const container_type& c, const Alloc& a); 46*0b57cec5SDimitry Andric template <class Alloc> stack(container_type&& c, const Alloc& a); 47*0b57cec5SDimitry Andric template <class Alloc> stack(const stack& c, const Alloc& a); 48*0b57cec5SDimitry Andric template <class Alloc> stack(stack&& c, const Alloc& a); 49*0b57cec5SDimitry Andric 50*0b57cec5SDimitry Andric bool empty() const; 51*0b57cec5SDimitry Andric size_type size() const; 52*0b57cec5SDimitry Andric reference top(); 53*0b57cec5SDimitry Andric const_reference top() const; 54*0b57cec5SDimitry Andric 55*0b57cec5SDimitry Andric void push(const value_type& x); 56*0b57cec5SDimitry Andric void push(value_type&& x); 57*0b57cec5SDimitry Andric template <class... Args> reference emplace(Args&&... args); // reference in C++17 58*0b57cec5SDimitry Andric void pop(); 59*0b57cec5SDimitry Andric 60*0b57cec5SDimitry Andric void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>) 61*0b57cec5SDimitry Andric}; 62*0b57cec5SDimitry Andric 63*0b57cec5SDimitry Andrictemplate<class Container> 64*0b57cec5SDimitry Andric stack(Container) -> stack<typename Container::value_type, Container>; // C++17 65*0b57cec5SDimitry Andric 66*0b57cec5SDimitry Andrictemplate<class Container, class Allocator> 67*0b57cec5SDimitry Andric stack(Container, Allocator) -> stack<typename Container::value_type, Container>; // C++17 68*0b57cec5SDimitry Andric 69*0b57cec5SDimitry Andrictemplate <class T, class Container> 70*0b57cec5SDimitry Andric bool operator==(const stack<T, Container>& x, const stack<T, Container>& y); 71*0b57cec5SDimitry Andrictemplate <class T, class Container> 72*0b57cec5SDimitry Andric bool operator< (const stack<T, Container>& x, const stack<T, Container>& y); 73*0b57cec5SDimitry Andrictemplate <class T, class Container> 74*0b57cec5SDimitry Andric bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y); 75*0b57cec5SDimitry Andrictemplate <class T, class Container> 76*0b57cec5SDimitry Andric bool operator> (const stack<T, Container>& x, const stack<T, Container>& y); 77*0b57cec5SDimitry Andrictemplate <class T, class Container> 78*0b57cec5SDimitry Andric bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y); 79*0b57cec5SDimitry Andrictemplate <class T, class Container> 80*0b57cec5SDimitry Andric bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y); 81*0b57cec5SDimitry Andric 82*0b57cec5SDimitry Andrictemplate <class T, class Container> 83*0b57cec5SDimitry Andric void swap(stack<T, Container>& x, stack<T, Container>& y) 84*0b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 85*0b57cec5SDimitry Andric 86*0b57cec5SDimitry Andric} // std 87*0b57cec5SDimitry Andric 88*0b57cec5SDimitry Andric*/ 89*0b57cec5SDimitry Andric 90*0b57cec5SDimitry Andric#include <__config> 91*0b57cec5SDimitry Andric#include <deque> 92*0b57cec5SDimitry Andric 93*0b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 94*0b57cec5SDimitry Andric#pragma GCC system_header 95*0b57cec5SDimitry Andric#endif 96*0b57cec5SDimitry Andric 97*0b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 98*0b57cec5SDimitry Andric 99*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS stack; 100*0b57cec5SDimitry Andric 101*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 102*0b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 103*0b57cec5SDimitry Andricbool 104*0b57cec5SDimitry Andricoperator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y); 105*0b57cec5SDimitry Andric 106*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 107*0b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 108*0b57cec5SDimitry Andricbool 109*0b57cec5SDimitry Andricoperator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y); 110*0b57cec5SDimitry Andric 111*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container /*= deque<_Tp>*/> 112*0b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS stack 113*0b57cec5SDimitry Andric{ 114*0b57cec5SDimitry Andricpublic: 115*0b57cec5SDimitry Andric typedef _Container container_type; 116*0b57cec5SDimitry Andric typedef typename container_type::value_type value_type; 117*0b57cec5SDimitry Andric typedef typename container_type::reference reference; 118*0b57cec5SDimitry Andric typedef typename container_type::const_reference const_reference; 119*0b57cec5SDimitry Andric typedef typename container_type::size_type size_type; 120*0b57cec5SDimitry Andric static_assert((is_same<_Tp, value_type>::value), "" ); 121*0b57cec5SDimitry Andric 122*0b57cec5SDimitry Andricprotected: 123*0b57cec5SDimitry Andric container_type c; 124*0b57cec5SDimitry Andric 125*0b57cec5SDimitry Andricpublic: 126*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 127*0b57cec5SDimitry Andric stack() 128*0b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) 129*0b57cec5SDimitry Andric : c() {} 130*0b57cec5SDimitry Andric 131*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 132*0b57cec5SDimitry Andric stack(const stack& __q) : c(__q.c) {} 133*0b57cec5SDimitry Andric 134*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 135*0b57cec5SDimitry Andric stack& operator=(const stack& __q) {c = __q.c; return *this;} 136*0b57cec5SDimitry Andric 137*0b57cec5SDimitry Andric 138*0b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 139*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 140*0b57cec5SDimitry Andric stack(stack&& __q) 141*0b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value) 142*0b57cec5SDimitry Andric : c(_VSTD::move(__q.c)) {} 143*0b57cec5SDimitry Andric 144*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 145*0b57cec5SDimitry Andric stack& operator=(stack&& __q) 146*0b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value) 147*0b57cec5SDimitry Andric {c = _VSTD::move(__q.c); return *this;} 148*0b57cec5SDimitry Andric 149*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 150*0b57cec5SDimitry Andric explicit stack(container_type&& __c) : c(_VSTD::move(__c)) {} 151*0b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 152*0b57cec5SDimitry Andric 153*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 154*0b57cec5SDimitry Andric explicit stack(const container_type& __c) : c(__c) {} 155*0b57cec5SDimitry Andric 156*0b57cec5SDimitry Andric template <class _Alloc> 157*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 158*0b57cec5SDimitry Andric explicit stack(const _Alloc& __a, 159*0b57cec5SDimitry Andric typename enable_if<uses_allocator<container_type, 160*0b57cec5SDimitry Andric _Alloc>::value>::type* = 0) 161*0b57cec5SDimitry Andric : c(__a) {} 162*0b57cec5SDimitry Andric template <class _Alloc> 163*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 164*0b57cec5SDimitry Andric stack(const container_type& __c, const _Alloc& __a, 165*0b57cec5SDimitry Andric typename enable_if<uses_allocator<container_type, 166*0b57cec5SDimitry Andric _Alloc>::value>::type* = 0) 167*0b57cec5SDimitry Andric : c(__c, __a) {} 168*0b57cec5SDimitry Andric template <class _Alloc> 169*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 170*0b57cec5SDimitry Andric stack(const stack& __s, const _Alloc& __a, 171*0b57cec5SDimitry Andric typename enable_if<uses_allocator<container_type, 172*0b57cec5SDimitry Andric _Alloc>::value>::type* = 0) 173*0b57cec5SDimitry Andric : c(__s.c, __a) {} 174*0b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 175*0b57cec5SDimitry Andric template <class _Alloc> 176*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 177*0b57cec5SDimitry Andric stack(container_type&& __c, const _Alloc& __a, 178*0b57cec5SDimitry Andric typename enable_if<uses_allocator<container_type, 179*0b57cec5SDimitry Andric _Alloc>::value>::type* = 0) 180*0b57cec5SDimitry Andric : c(_VSTD::move(__c), __a) {} 181*0b57cec5SDimitry Andric template <class _Alloc> 182*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 183*0b57cec5SDimitry Andric stack(stack&& __s, const _Alloc& __a, 184*0b57cec5SDimitry Andric typename enable_if<uses_allocator<container_type, 185*0b57cec5SDimitry Andric _Alloc>::value>::type* = 0) 186*0b57cec5SDimitry Andric : c(_VSTD::move(__s.c), __a) {} 187*0b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 188*0b57cec5SDimitry Andric 189*0b57cec5SDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 190*0b57cec5SDimitry Andric bool empty() const {return c.empty();} 191*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 192*0b57cec5SDimitry Andric size_type size() const {return c.size();} 193*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 194*0b57cec5SDimitry Andric reference top() {return c.back();} 195*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 196*0b57cec5SDimitry Andric const_reference top() const {return c.back();} 197*0b57cec5SDimitry Andric 198*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 199*0b57cec5SDimitry Andric void push(const value_type& __v) {c.push_back(__v);} 200*0b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 201*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 202*0b57cec5SDimitry Andric void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} 203*0b57cec5SDimitry Andric 204*0b57cec5SDimitry Andric template <class... _Args> 205*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 206*0b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 207*0b57cec5SDimitry Andric decltype(auto) emplace(_Args&&... __args) 208*0b57cec5SDimitry Andric { return c.emplace_back(_VSTD::forward<_Args>(__args)...);} 209*0b57cec5SDimitry Andric#else 210*0b57cec5SDimitry Andric void emplace(_Args&&... __args) 211*0b57cec5SDimitry Andric { c.emplace_back(_VSTD::forward<_Args>(__args)...);} 212*0b57cec5SDimitry Andric#endif 213*0b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 214*0b57cec5SDimitry Andric 215*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 216*0b57cec5SDimitry Andric void pop() {c.pop_back();} 217*0b57cec5SDimitry Andric 218*0b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 219*0b57cec5SDimitry Andric void swap(stack& __s) 220*0b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<container_type>::value) 221*0b57cec5SDimitry Andric { 222*0b57cec5SDimitry Andric using _VSTD::swap; 223*0b57cec5SDimitry Andric swap(c, __s.c); 224*0b57cec5SDimitry Andric } 225*0b57cec5SDimitry Andric 226*0b57cec5SDimitry Andric template <class T1, class _C1> 227*0b57cec5SDimitry Andric friend 228*0b57cec5SDimitry Andric bool 229*0b57cec5SDimitry Andric operator==(const stack<T1, _C1>& __x, const stack<T1, _C1>& __y); 230*0b57cec5SDimitry Andric 231*0b57cec5SDimitry Andric template <class T1, class _C1> 232*0b57cec5SDimitry Andric friend 233*0b57cec5SDimitry Andric bool 234*0b57cec5SDimitry Andric operator< (const stack<T1, _C1>& __x, const stack<T1, _C1>& __y); 235*0b57cec5SDimitry Andric}; 236*0b57cec5SDimitry Andric 237*0b57cec5SDimitry Andric#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 238*0b57cec5SDimitry Andrictemplate<class _Container, 239*0b57cec5SDimitry Andric class = typename enable_if<!__is_allocator<_Container>::value, nullptr_t>::type 240*0b57cec5SDimitry Andric> 241*0b57cec5SDimitry Andricstack(_Container) 242*0b57cec5SDimitry Andric -> stack<typename _Container::value_type, _Container>; 243*0b57cec5SDimitry Andric 244*0b57cec5SDimitry Andrictemplate<class _Container, 245*0b57cec5SDimitry Andric class _Alloc, 246*0b57cec5SDimitry Andric class = typename enable_if<!__is_allocator<_Container>::value, nullptr_t>::type, 247*0b57cec5SDimitry Andric class = typename enable_if< __is_allocator<_Alloc>::value, nullptr_t>::type 248*0b57cec5SDimitry Andric > 249*0b57cec5SDimitry Andricstack(_Container, _Alloc) 250*0b57cec5SDimitry Andric -> stack<typename _Container::value_type, _Container>; 251*0b57cec5SDimitry Andric#endif 252*0b57cec5SDimitry Andric 253*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 254*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 255*0b57cec5SDimitry Andricbool 256*0b57cec5SDimitry Andricoperator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 257*0b57cec5SDimitry Andric{ 258*0b57cec5SDimitry Andric return __x.c == __y.c; 259*0b57cec5SDimitry Andric} 260*0b57cec5SDimitry Andric 261*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 262*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 263*0b57cec5SDimitry Andricbool 264*0b57cec5SDimitry Andricoperator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 265*0b57cec5SDimitry Andric{ 266*0b57cec5SDimitry Andric return __x.c < __y.c; 267*0b57cec5SDimitry Andric} 268*0b57cec5SDimitry Andric 269*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 270*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 271*0b57cec5SDimitry Andricbool 272*0b57cec5SDimitry Andricoperator!=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 273*0b57cec5SDimitry Andric{ 274*0b57cec5SDimitry Andric return !(__x == __y); 275*0b57cec5SDimitry Andric} 276*0b57cec5SDimitry Andric 277*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 278*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 279*0b57cec5SDimitry Andricbool 280*0b57cec5SDimitry Andricoperator> (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 281*0b57cec5SDimitry Andric{ 282*0b57cec5SDimitry Andric return __y < __x; 283*0b57cec5SDimitry Andric} 284*0b57cec5SDimitry Andric 285*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 286*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 287*0b57cec5SDimitry Andricbool 288*0b57cec5SDimitry Andricoperator>=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 289*0b57cec5SDimitry Andric{ 290*0b57cec5SDimitry Andric return !(__x < __y); 291*0b57cec5SDimitry Andric} 292*0b57cec5SDimitry Andric 293*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 294*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 295*0b57cec5SDimitry Andricbool 296*0b57cec5SDimitry Andricoperator<=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y) 297*0b57cec5SDimitry Andric{ 298*0b57cec5SDimitry Andric return !(__y < __x); 299*0b57cec5SDimitry Andric} 300*0b57cec5SDimitry Andric 301*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container> 302*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 303*0b57cec5SDimitry Andrictypename enable_if< 304*0b57cec5SDimitry Andric __is_swappable<_Container>::value, 305*0b57cec5SDimitry Andric void 306*0b57cec5SDimitry Andric>::type 307*0b57cec5SDimitry Andricswap(stack<_Tp, _Container>& __x, stack<_Tp, _Container>& __y) 308*0b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 309*0b57cec5SDimitry Andric{ 310*0b57cec5SDimitry Andric __x.swap(__y); 311*0b57cec5SDimitry Andric} 312*0b57cec5SDimitry Andric 313*0b57cec5SDimitry Andrictemplate <class _Tp, class _Container, class _Alloc> 314*0b57cec5SDimitry Andricstruct _LIBCPP_TEMPLATE_VIS uses_allocator<stack<_Tp, _Container>, _Alloc> 315*0b57cec5SDimitry Andric : public uses_allocator<_Container, _Alloc> 316*0b57cec5SDimitry Andric{ 317*0b57cec5SDimitry Andric}; 318*0b57cec5SDimitry Andric 319*0b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 320*0b57cec5SDimitry Andric 321*0b57cec5SDimitry Andric#endif // _LIBCPP_STACK 322