stack 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358
  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 InputIterator> stack(InputIterator first, InputIterator last); // since C++23
  36. template <class Alloc> explicit stack(const Alloc& a);
  37. template <class Alloc> stack(const container_type& c, const Alloc& a);
  38. template <class Alloc> stack(container_type&& c, const Alloc& a);
  39. template <class Alloc> stack(const stack& c, const Alloc& a);
  40. template <class Alloc> stack(stack&& c, const Alloc& a);
  41. template<class InputIterator, class Alloc>
  42. stack(InputIterator first, InputIterator last, const Alloc&); // since C++23
  43. bool empty() const;
  44. size_type size() const;
  45. reference top();
  46. const_reference top() const;
  47. void push(const value_type& x);
  48. void push(value_type&& x);
  49. template <class... Args> reference emplace(Args&&... args); // reference in C++17
  50. void pop();
  51. void swap(stack& c) noexcept(is_nothrow_swappable_v<Container>)
  52. };
  53. template<class Container>
  54. stack(Container) -> stack<typename Container::value_type, Container>; // C++17
  55. template<class InputIterator>
  56. stack(InputIterator, InputIterator) -> stack<iter-value-type<InputIterator>>; // since C++23
  57. template<class Container, class Allocator>
  58. stack(Container, Allocator) -> stack<typename Container::value_type, Container>; // C++17
  59. template<class InputIterator, class Allocator>
  60. stack(InputIterator, InputIterator, Allocator)
  61. -> stack<iter-value-type<InputIterator>,
  62. deque<iter-value-type<InputIterator>, Allocator>>; // since C++23
  63. template <class T, class Container>
  64. bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
  65. template <class T, class Container>
  66. bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
  67. template <class T, class Container>
  68. bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
  69. template <class T, class Container>
  70. bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
  71. template <class T, class Container>
  72. bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
  73. template <class T, class Container>
  74. bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
  75. template <class T, class Container>
  76. void swap(stack<T, Container>& x, stack<T, Container>& y)
  77. noexcept(noexcept(x.swap(y)));
  78. } // std
  79. */
  80. #include <__assert> // all public C++ headers provide the assertion handler
  81. #include <__config>
  82. #include <__iterator/iterator_traits.h>
  83. #include <__memory/uses_allocator.h>
  84. #include <__utility/forward.h>
  85. #include <deque>
  86. #include <type_traits>
  87. #include <version>
  88. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  89. # pragma GCC system_header
  90. #endif
  91. _LIBCPP_BEGIN_NAMESPACE_STD
  92. template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS stack;
  93. template <class _Tp, class _Container>
  94. _LIBCPP_INLINE_VISIBILITY
  95. bool
  96. operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);
  97. template <class _Tp, class _Container>
  98. _LIBCPP_INLINE_VISIBILITY
  99. bool
  100. operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y);
  101. template <class _Tp, class _Container /*= deque<_Tp>*/>
  102. class _LIBCPP_TEMPLATE_VIS stack
  103. {
  104. public:
  105. typedef _Container container_type;
  106. typedef typename container_type::value_type value_type;
  107. typedef typename container_type::reference reference;
  108. typedef typename container_type::const_reference const_reference;
  109. typedef typename container_type::size_type size_type;
  110. static_assert((is_same<_Tp, value_type>::value), "" );
  111. protected:
  112. container_type c;
  113. public:
  114. _LIBCPP_INLINE_VISIBILITY
  115. stack()
  116. _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
  117. : c() {}
  118. _LIBCPP_INLINE_VISIBILITY
  119. stack(const stack& __q) : c(__q.c) {}
  120. _LIBCPP_INLINE_VISIBILITY
  121. stack& operator=(const stack& __q) {c = __q.c; return *this;}
  122. #ifndef _LIBCPP_CXX03_LANG
  123. _LIBCPP_INLINE_VISIBILITY
  124. stack(stack&& __q)
  125. _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
  126. : c(_VSTD::move(__q.c)) {}
  127. _LIBCPP_INLINE_VISIBILITY
  128. stack& operator=(stack&& __q)
  129. _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
  130. {c = _VSTD::move(__q.c); return *this;}
  131. _LIBCPP_INLINE_VISIBILITY
  132. explicit stack(container_type&& __c) : c(_VSTD::move(__c)) {}
  133. #endif // _LIBCPP_CXX03_LANG
  134. _LIBCPP_INLINE_VISIBILITY
  135. explicit stack(const container_type& __c) : c(__c) {}
  136. template <class _Alloc>
  137. _LIBCPP_INLINE_VISIBILITY
  138. explicit stack(const _Alloc& __a,
  139. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  140. : c(__a) {}
  141. template <class _Alloc>
  142. _LIBCPP_INLINE_VISIBILITY
  143. stack(const container_type& __c, const _Alloc& __a,
  144. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  145. : c(__c, __a) {}
  146. template <class _Alloc>
  147. _LIBCPP_INLINE_VISIBILITY
  148. stack(const stack& __s, const _Alloc& __a,
  149. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  150. : c(__s.c, __a) {}
  151. #ifndef _LIBCPP_CXX03_LANG
  152. template <class _Alloc>
  153. _LIBCPP_INLINE_VISIBILITY
  154. stack(container_type&& __c, const _Alloc& __a,
  155. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  156. : c(_VSTD::move(__c), __a) {}
  157. template <class _Alloc>
  158. _LIBCPP_INLINE_VISIBILITY
  159. stack(stack&& __s, const _Alloc& __a,
  160. __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
  161. : c(_VSTD::move(__s.c), __a) {}
  162. #endif // _LIBCPP_CXX03_LANG
  163. #if _LIBCPP_STD_VER > 20
  164. template <class _InputIterator,
  165. class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>>
  166. _LIBCPP_HIDE_FROM_ABI
  167. stack(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
  168. template <class _InputIterator,
  169. class _Alloc,
  170. class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
  171. class = __enable_if_t<uses_allocator<container_type, _Alloc>::value>>
  172. _LIBCPP_HIDE_FROM_ABI
  173. stack(_InputIterator __first, _InputIterator __last, const _Alloc& __alloc) : c(__first, __last, __alloc) {}
  174. #endif
  175. _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
  176. bool empty() const {return c.empty();}
  177. _LIBCPP_INLINE_VISIBILITY
  178. size_type size() const {return c.size();}
  179. _LIBCPP_INLINE_VISIBILITY
  180. reference top() {return c.back();}
  181. _LIBCPP_INLINE_VISIBILITY
  182. const_reference top() const {return c.back();}
  183. _LIBCPP_INLINE_VISIBILITY
  184. void push(const value_type& __v) {c.push_back(__v);}
  185. #ifndef _LIBCPP_CXX03_LANG
  186. _LIBCPP_INLINE_VISIBILITY
  187. void push(value_type&& __v) {c.push_back(_VSTD::move(__v));}
  188. template <class... _Args>
  189. _LIBCPP_INLINE_VISIBILITY
  190. #if _LIBCPP_STD_VER > 14
  191. decltype(auto) emplace(_Args&&... __args)
  192. { return c.emplace_back(_VSTD::forward<_Args>(__args)...);}
  193. #else
  194. void emplace(_Args&&... __args)
  195. { c.emplace_back(_VSTD::forward<_Args>(__args)...);}
  196. #endif
  197. #endif // _LIBCPP_CXX03_LANG
  198. _LIBCPP_INLINE_VISIBILITY
  199. void pop() {c.pop_back();}
  200. _LIBCPP_INLINE_VISIBILITY
  201. void swap(stack& __s)
  202. _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
  203. {
  204. using _VSTD::swap;
  205. swap(c, __s.c);
  206. }
  207. template <class T1, class _C1>
  208. friend
  209. bool
  210. operator==(const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
  211. template <class T1, class _C1>
  212. friend
  213. bool
  214. operator< (const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
  215. };
  216. #if _LIBCPP_STD_VER > 14
  217. template<class _Container,
  218. class = enable_if_t<!__is_allocator<_Container>::value>
  219. >
  220. stack(_Container)
  221. -> stack<typename _Container::value_type, _Container>;
  222. template<class _Container,
  223. class _Alloc,
  224. class = enable_if_t<!__is_allocator<_Container>::value>,
  225. class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
  226. >
  227. stack(_Container, _Alloc)
  228. -> stack<typename _Container::value_type, _Container>;
  229. #endif
  230. #if _LIBCPP_STD_VER > 20
  231. template<class _InputIterator,
  232. class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>>
  233. stack(_InputIterator, _InputIterator)
  234. -> stack<__iter_value_type<_InputIterator>>;
  235. template<class _InputIterator,
  236. class _Alloc,
  237. class = __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
  238. class = __enable_if_t<__is_allocator<_Alloc>::value>>
  239. stack(_InputIterator, _InputIterator, _Alloc)
  240. -> stack<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
  241. #endif
  242. template <class _Tp, class _Container>
  243. inline _LIBCPP_INLINE_VISIBILITY
  244. bool
  245. operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  246. {
  247. return __x.c == __y.c;
  248. }
  249. template <class _Tp, class _Container>
  250. inline _LIBCPP_INLINE_VISIBILITY
  251. bool
  252. operator< (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  253. {
  254. return __x.c < __y.c;
  255. }
  256. template <class _Tp, class _Container>
  257. inline _LIBCPP_INLINE_VISIBILITY
  258. bool
  259. operator!=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  260. {
  261. return !(__x == __y);
  262. }
  263. template <class _Tp, class _Container>
  264. inline _LIBCPP_INLINE_VISIBILITY
  265. bool
  266. operator> (const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  267. {
  268. return __y < __x;
  269. }
  270. template <class _Tp, class _Container>
  271. inline _LIBCPP_INLINE_VISIBILITY
  272. bool
  273. operator>=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  274. {
  275. return !(__x < __y);
  276. }
  277. template <class _Tp, class _Container>
  278. inline _LIBCPP_INLINE_VISIBILITY
  279. bool
  280. operator<=(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
  281. {
  282. return !(__y < __x);
  283. }
  284. template <class _Tp, class _Container>
  285. inline _LIBCPP_INLINE_VISIBILITY
  286. __enable_if_t<__is_swappable<_Container>::value, void>
  287. swap(stack<_Tp, _Container>& __x, stack<_Tp, _Container>& __y)
  288. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  289. {
  290. __x.swap(__y);
  291. }
  292. template <class _Tp, class _Container, class _Alloc>
  293. struct _LIBCPP_TEMPLATE_VIS uses_allocator<stack<_Tp, _Container>, _Alloc>
  294. : public uses_allocator<_Container, _Alloc>
  295. {
  296. };
  297. _LIBCPP_END_NAMESPACE_STD
  298. #endif // _LIBCPP_STACK