stack 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315
  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. #ifndef _LIBCPP_STACK
  10. #define _LIBCPP_STACK
  11. /*
  12. stack synopsis
  13. namespace std
  14. {
  15. template <class T, class Container = deque<T>>
  16. class stack
  17. {
  18. public:
  19. typedef Container container_type;
  20. typedef typename container_type::value_type value_type;
  21. typedef typename container_type::reference reference;
  22. typedef typename container_type::const_reference const_reference;
  23. typedef typename container_type::size_type size_type;
  24. protected:
  25. container_type c;
  26. public:
  27. stack() = default;
  28. ~stack() = default;
  29. stack(const stack& q) = default;
  30. stack(stack&& q) = default;
  31. stack& operator=(const stack& q) = default;
  32. stack& operator=(stack&& q) = default;
  33. explicit stack(const container_type& c);
  34. explicit stack(container_type&& c);
  35. template <class Alloc> explicit stack(const Alloc& a);
  36. template <class Alloc> stack(const container_type& c, const Alloc& a);
  37. template <class Alloc> stack(container_type&& c, const Alloc& a);
  38. template <class Alloc> stack(const stack& c, const Alloc& a);
  39. template <class Alloc> stack(stack&& c, const Alloc& a);
  40. bool empty() const;
  41. size_type size() const;
  42. reference top();
  43. const_reference top() const;
  44. void push(const value_type& x);
  45. void push(value_type&& x);
  46. template <class... Args> reference emplace(Args&&... args); // reference in C++17
  47. void pop();
  48. void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>)
  49. };
  50. template<class Container>
  51. stack(Container) -> stack<typename Container::value_type, Container>; // C++17
  52. template<class Container, class Allocator>
  53. stack(Container, Allocator) -> stack<typename Container::value_type, Container>; // C++17
  54. template <class T, class Container>
  55. bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
  56. template <class T, class Container>
  57. bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
  58. template <class T, class Container>
  59. bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
  60. template <class T, class Container>
  61. bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
  62. template <class T, class Container>
  63. bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
  64. template <class T, class Container>
  65. bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
  66. template <class T, class Container>
  67. void swap(stack<T, Container>& x, stack<T, Container>& y)
  68. noexcept(noexcept(x.swap(y)));
  69. } // std
  70. */
  71. #include <__config>
  72. #include <__memory/uses_allocator.h>
  73. #include <__utility/forward.h>
  74. #include <deque>
  75. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  76. #pragma GCC system_header
  77. #endif
  78. _LIBCPP_BEGIN_NAMESPACE_STD
  79. template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS stack;
  80. template <class _Tp, class _Container>
  81. _LIBCPP_INLINE_VISIBILITY
  82. bool
  83. operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);
  84. template <class _Tp, class _Container>
  85. _LIBCPP_INLINE_VISIBILITY
  86. bool
  87. operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);
  88. template <class _Tp, class _Container /*= deque<_Tp>*/>
  89. class _LIBCPP_TEMPLATE_VIS stack
  90. {
  91. public:
  92. typedef _Container container_type;
  93. typedef typename container_type::value_type value_type;
  94. typedef typename container_type::reference reference;
  95. typedef typename container_type::const_reference const_reference;
  96. typedef typename container_type::size_type size_type;
  97. static_assert((is_same<_Tp, value_type>::value), "" );
  98. protected:
  99. container_type c;
  100. public:
  101. _LIBCPP_INLINE_VISIBILITY
  102. stack()
  103. _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
  104. : c() {}
  105. _LIBCPP_INLINE_VISIBILITY
  106. stack(const stack& __q) : c(__q.c) {}
  107. _LIBCPP_INLINE_VISIBILITY
  108. stack& operator=(const stack& __q) {c = __q.c; return *this;}
  109. #ifndef _LIBCPP_CXX03_LANG
  110. _LIBCPP_INLINE_VISIBILITY
  111. stack(stack&& __q)
  112. _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
  113. : c(_VSTD::move(__q.c)) {}
  114. _LIBCPP_INLINE_VISIBILITY
  115. stack& operator=(stack&& __q)
  116. _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
  117. {c = _VSTD::move(__q.c); return *this;}
  118. _LIBCPP_INLINE_VISIBILITY
  119. explicit stack(container_type&& __c) : c(_VSTD::move(__c)) {}
  120. #endif // _LIBCPP_CXX03_LANG
  121. _LIBCPP_INLINE_VISIBILITY
  122. explicit stack(const container_type& __c) : c(__c) {}
  123. template <class _Alloc>
  124. _LIBCPP_INLINE_VISIBILITY
  125. explicit stack(const _Alloc& __a,
  126. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  127. : c(__a) {}
  128. template <class _Alloc>
  129. _LIBCPP_INLINE_VISIBILITY
  130. stack(const container_type& __c, const _Alloc& __a,
  131. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  132. : c(__c, __a) {}
  133. template <class _Alloc>
  134. _LIBCPP_INLINE_VISIBILITY
  135. stack(const stack& __s, const _Alloc& __a,
  136. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  137. : c(__s.c, __a) {}
  138. #ifndef _LIBCPP_CXX03_LANG
  139. template <class _Alloc>
  140. _LIBCPP_INLINE_VISIBILITY
  141. stack(container_type&& __c, const _Alloc& __a,
  142. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  143. : c(_VSTD::move(__c), __a) {}
  144. template <class _Alloc>
  145. _LIBCPP_INLINE_VISIBILITY
  146. stack(stack&& __s, const _Alloc& __a,
  147. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  148. : c(_VSTD::move(__s.c), __a) {}
  149. #endif // _LIBCPP_CXX03_LANG
  150. _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
  151. bool empty() const {return c.empty();}
  152. _LIBCPP_INLINE_VISIBILITY
  153. size_type size() const {return c.size();}
  154. _LIBCPP_INLINE_VISIBILITY
  155. reference top() {return c.back();}
  156. _LIBCPP_INLINE_VISIBILITY
  157. const_reference top() const {return c.back();}
  158. _LIBCPP_INLINE_VISIBILITY
  159. void push(const value_type& __v) {c.push_back(__v);}
  160. #ifndef _LIBCPP_CXX03_LANG
  161. _LIBCPP_INLINE_VISIBILITY
  162. void push(value_type&& __v) {c.push_back(_VSTD::move(__v));}
  163. template <class... _Args>
  164. _LIBCPP_INLINE_VISIBILITY
  165. #if _LIBCPP_STD_VER > 14
  166. decltype(auto) emplace(_Args&&... __args)
  167. { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
  168. #else
  169. void emplace(_Args&&... __args)
  170. { c.emplace_back(_VSTD::forward<_Args>(__args)...);}
  171. #endif
  172. #endif // _LIBCPP_CXX03_LANG
  173. _LIBCPP_INLINE_VISIBILITY
  174. void pop() {c.pop_back();}
  175. _LIBCPP_INLINE_VISIBILITY
  176. void swap(stack& __s)
  177. _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
  178. {
  179. using _VSTD::swap;
  180. swap(c, __s.c);
  181. }
  182. template <class T1, class _C1>
  183. friend
  184. bool
  185. operator==(const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
  186. template <class T1, class _C1>
  187. friend
  188. bool
  189. operator< (const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
  190. };
  191. #if _LIBCPP_STD_VER >= 17
  192. template<class _Container,
  193. class = enable_if_t<!__is_allocator<_Container>::value>
  194. >
  195. stack(_Container)
  196. -> stack<typename _Container::value_type, _Container>;
  197. template<class _Container,
  198. class _Alloc,
  199. class = enable_if_t<!__is_allocator<_Container>::value>,
  200. class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
  201. >
  202. stack(_Container, _Alloc)
  203. -> stack<typename _Container::value_type, _Container>;
  204. #endif
  205. template <class _Tp, class _Container>
  206. inline _LIBCPP_INLINE_VISIBILITY
  207. bool
  208. operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  209. {
  210. return __x.c == __y.c;
  211. }
  212. template <class _Tp, class _Container>
  213. inline _LIBCPP_INLINE_VISIBILITY
  214. bool
  215. operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  216. {
  217. return __x.c < __y.c;
  218. }
  219. template <class _Tp, class _Container>
  220. inline _LIBCPP_INLINE_VISIBILITY
  221. bool
  222. operator!=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  223. {
  224. return !(__x == __y);
  225. }
  226. template <class _Tp, class _Container>
  227. inline _LIBCPP_INLINE_VISIBILITY
  228. bool
  229. operator> (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  230. {
  231. return __y < __x;
  232. }
  233. template <class _Tp, class _Container>
  234. inline _LIBCPP_INLINE_VISIBILITY
  235. bool
  236. operator>=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  237. {
  238. return !(__x < __y);
  239. }
  240. template <class _Tp, class _Container>
  241. inline _LIBCPP_INLINE_VISIBILITY
  242. bool
  243. operator<=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  244. {
  245. return !(__y < __x);
  246. }
  247. template <class _Tp, class _Container>
  248. inline _LIBCPP_INLINE_VISIBILITY
  249. __enable_if_t<__is_swappable<_Container>::value, void>
  250. swap(stack<_Tp, _Container>& __x, stack<_Tp, _Container>& __y)
  251. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  252. {
  253. __x.swap(__y);
  254. }
  255. template <class _Tp, class _Container, class _Alloc>
  256. struct _LIBCPP_TEMPLATE_VIS uses_allocator<stack<_Tp, _Container>, _Alloc>
  257. : public uses_allocator<_Container, _Alloc>
  258. {
  259. };
  260. _LIBCPP_END_NAMESPACE_STD
  261. #endif // _LIBCPP_STACK