forward_list 61 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789
  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_FORWARD_LIST
  10. #define _LIBCPP_FORWARD_LIST
  11. /*
  12. forward_list synopsis
  13. namespace std
  14. {
  15. template <class T, class Allocator = allocator<T>>
  16. class forward_list
  17. {
  18. public:
  19. typedef T value_type;
  20. typedef Allocator allocator_type;
  21. typedef value_type& reference;
  22. typedef const value_type& const_reference;
  23. typedef typename allocator_traits<allocator_type>::pointer pointer;
  24. typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
  25. typedef typename allocator_traits<allocator_type>::size_type size_type;
  26. typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  27. typedef <details> iterator;
  28. typedef <details> const_iterator;
  29. forward_list()
  30. noexcept(is_nothrow_default_constructible<allocator_type>::value);
  31. explicit forward_list(const allocator_type& a);
  32. explicit forward_list(size_type n);
  33. explicit forward_list(size_type n, const allocator_type& a); // C++14
  34. forward_list(size_type n, const value_type& v);
  35. forward_list(size_type n, const value_type& v, const allocator_type& a);
  36. template <class InputIterator>
  37. forward_list(InputIterator first, InputIterator last);
  38. template <class InputIterator>
  39. forward_list(InputIterator first, InputIterator last, const allocator_type& a);
  40. forward_list(const forward_list& x);
  41. forward_list(const forward_list& x, const allocator_type& a);
  42. forward_list(forward_list&& x)
  43. noexcept(is_nothrow_move_constructible<allocator_type>::value);
  44. forward_list(forward_list&& x, const allocator_type& a);
  45. forward_list(initializer_list<value_type> il);
  46. forward_list(initializer_list<value_type> il, const allocator_type& a);
  47. ~forward_list();
  48. forward_list& operator=(const forward_list& x);
  49. forward_list& operator=(forward_list&& x)
  50. noexcept(
  51. allocator_type::propagate_on_container_move_assignment::value &&
  52. is_nothrow_move_assignable<allocator_type>::value);
  53. forward_list& operator=(initializer_list<value_type> il);
  54. template <class InputIterator>
  55. void assign(InputIterator first, InputIterator last);
  56. void assign(size_type n, const value_type& v);
  57. void assign(initializer_list<value_type> il);
  58. allocator_type get_allocator() const noexcept;
  59. iterator begin() noexcept;
  60. const_iterator begin() const noexcept;
  61. iterator end() noexcept;
  62. const_iterator end() const noexcept;
  63. const_iterator cbegin() const noexcept;
  64. const_iterator cend() const noexcept;
  65. iterator before_begin() noexcept;
  66. const_iterator before_begin() const noexcept;
  67. const_iterator cbefore_begin() const noexcept;
  68. bool empty() const noexcept;
  69. size_type max_size() const noexcept;
  70. reference front();
  71. const_reference front() const;
  72. template <class... Args> reference emplace_front(Args&&... args); // reference in C++17
  73. void push_front(const value_type& v);
  74. void push_front(value_type&& v);
  75. void pop_front();
  76. template <class... Args>
  77. iterator emplace_after(const_iterator p, Args&&... args);
  78. iterator insert_after(const_iterator p, const value_type& v);
  79. iterator insert_after(const_iterator p, value_type&& v);
  80. iterator insert_after(const_iterator p, size_type n, const value_type& v);
  81. template <class InputIterator>
  82. iterator insert_after(const_iterator p,
  83. InputIterator first, InputIterator last);
  84. iterator insert_after(const_iterator p, initializer_list<value_type> il);
  85. iterator erase_after(const_iterator p);
  86. iterator erase_after(const_iterator first, const_iterator last);
  87. void swap(forward_list& x)
  88. noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
  89. void resize(size_type n);
  90. void resize(size_type n, const value_type& v);
  91. void clear() noexcept;
  92. void splice_after(const_iterator p, forward_list& x);
  93. void splice_after(const_iterator p, forward_list&& x);
  94. void splice_after(const_iterator p, forward_list& x, const_iterator i);
  95. void splice_after(const_iterator p, forward_list&& x, const_iterator i);
  96. void splice_after(const_iterator p, forward_list& x,
  97. const_iterator first, const_iterator last);
  98. void splice_after(const_iterator p, forward_list&& x,
  99. const_iterator first, const_iterator last);
  100. size_type remove(const value_type& v); // void before C++20
  101. template <class Predicate>
  102. size_type remove_if(Predicate pred); // void before C++20
  103. size_type unique(); // void before C++20
  104. template <class BinaryPredicate>
  105. size_type unique(BinaryPredicate binary_pred); // void before C++20
  106. void merge(forward_list& x);
  107. void merge(forward_list&& x);
  108. template <class Compare> void merge(forward_list& x, Compare comp);
  109. template <class Compare> void merge(forward_list&& x, Compare comp);
  110. void sort();
  111. template <class Compare> void sort(Compare comp);
  112. void reverse() noexcept;
  113. };
  114. template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
  115. forward_list(InputIterator, InputIterator, Allocator = Allocator())
  116. -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
  117. template <class T, class Allocator>
  118. bool operator==(const forward_list<T, Allocator>& x,
  119. const forward_list<T, Allocator>& y);
  120. template <class T, class Allocator>
  121. bool operator< (const forward_list<T, Allocator>& x,
  122. const forward_list<T, Allocator>& y);
  123. template <class T, class Allocator>
  124. bool operator!=(const forward_list<T, Allocator>& x,
  125. const forward_list<T, Allocator>& y);
  126. template <class T, class Allocator>
  127. bool operator> (const forward_list<T, Allocator>& x,
  128. const forward_list<T, Allocator>& y);
  129. template <class T, class Allocator>
  130. bool operator>=(const forward_list<T, Allocator>& x,
  131. const forward_list<T, Allocator>& y);
  132. template <class T, class Allocator>
  133. bool operator<=(const forward_list<T, Allocator>& x,
  134. const forward_list<T, Allocator>& y);
  135. template <class T, class Allocator>
  136. void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
  137. noexcept(noexcept(x.swap(y)));
  138. template <class T, class Allocator, class U>
  139. typename forward_list<T, Allocator>::size_type
  140. erase(forward_list<T, Allocator>& c, const U& value); // C++20
  141. template <class T, class Allocator, class Predicate>
  142. typename forward_list<T, Allocator>::size_type
  143. erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20
  144. } // std
  145. */
  146. #include <__config>
  147. #include <__utility/forward.h>
  148. #include <algorithm>
  149. #include <initializer_list>
  150. #include <iterator>
  151. #include <limits>
  152. #include <memory>
  153. #include <type_traits>
  154. #include <version>
  155. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  156. #pragma GCC system_header
  157. #endif
  158. _LIBCPP_PUSH_MACROS
  159. #include <__undef_macros>
  160. _LIBCPP_BEGIN_NAMESPACE_STD
  161. template <class _Tp, class _VoidPtr> struct __forward_list_node;
  162. template <class _NodePtr> struct __forward_begin_node;
  163. template <class>
  164. struct __forward_list_node_value_type;
  165. template <class _Tp, class _VoidPtr>
  166. struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {
  167. typedef _Tp type;
  168. };
  169. template <class _NodePtr>
  170. struct __forward_node_traits {
  171. typedef typename remove_cv<
  172. typename pointer_traits<_NodePtr>::element_type>::type __node;
  173. typedef typename __forward_list_node_value_type<__node>::type __node_value_type;
  174. typedef _NodePtr __node_pointer;
  175. typedef __forward_begin_node<_NodePtr> __begin_node;
  176. typedef typename __rebind_pointer<_NodePtr, __begin_node>::type
  177. __begin_node_pointer;
  178. typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;
  179. #if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)
  180. typedef __begin_node_pointer __iter_node_pointer;
  181. #else
  182. typedef typename conditional<
  183. is_pointer<__void_pointer>::value,
  184. __begin_node_pointer,
  185. __node_pointer
  186. >::type __iter_node_pointer;
  187. #endif
  188. typedef typename conditional<
  189. is_same<__iter_node_pointer, __node_pointer>::value,
  190. __begin_node_pointer,
  191. __node_pointer
  192. >::type __non_iter_node_pointer;
  193. _LIBCPP_INLINE_VISIBILITY
  194. static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) {
  195. return __p;
  196. }
  197. _LIBCPP_INLINE_VISIBILITY
  198. static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {
  199. return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));
  200. }
  201. };
  202. template <class _NodePtr>
  203. struct __forward_begin_node
  204. {
  205. typedef _NodePtr pointer;
  206. typedef typename __rebind_pointer<_NodePtr, __forward_begin_node>::type __begin_node_pointer;
  207. pointer __next_;
  208. _LIBCPP_INLINE_VISIBILITY __forward_begin_node() : __next_(nullptr) {}
  209. _LIBCPP_INLINE_VISIBILITY
  210. __begin_node_pointer __next_as_begin() const {
  211. return static_cast<__begin_node_pointer>(__next_);
  212. }
  213. };
  214. template <class _Tp, class _VoidPtr>
  215. struct _LIBCPP_HIDDEN __begin_node_of
  216. {
  217. typedef __forward_begin_node<
  218. typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type
  219. > type;
  220. };
  221. template <class _Tp, class _VoidPtr>
  222. struct _LIBCPP_STANDALONE_DEBUG __forward_list_node
  223. : public __begin_node_of<_Tp, _VoidPtr>::type
  224. {
  225. typedef _Tp value_type;
  226. value_type __value_;
  227. };
  228. template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS forward_list;
  229. template<class _NodeConstPtr> class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
  230. template <class _NodePtr>
  231. class _LIBCPP_TEMPLATE_VIS __forward_list_iterator
  232. {
  233. typedef __forward_node_traits<_NodePtr> __traits;
  234. typedef typename __traits::__node_pointer __node_pointer;
  235. typedef typename __traits::__begin_node_pointer __begin_node_pointer;
  236. typedef typename __traits::__iter_node_pointer __iter_node_pointer;
  237. typedef typename __traits::__void_pointer __void_pointer;
  238. __iter_node_pointer __ptr_;
  239. _LIBCPP_INLINE_VISIBILITY
  240. __begin_node_pointer __get_begin() const {
  241. return static_cast<__begin_node_pointer>(
  242. static_cast<__void_pointer>(__ptr_));
  243. }
  244. _LIBCPP_INLINE_VISIBILITY
  245. __node_pointer __get_unsafe_node_pointer() const {
  246. return static_cast<__node_pointer>(
  247. static_cast<__void_pointer>(__ptr_));
  248. }
  249. _LIBCPP_INLINE_VISIBILITY
  250. explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}
  251. _LIBCPP_INLINE_VISIBILITY
  252. explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT
  253. : __ptr_(__traits::__as_iter_node(__p)) {}
  254. _LIBCPP_INLINE_VISIBILITY
  255. explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT
  256. : __ptr_(__traits::__as_iter_node(__p)) {}
  257. template<class, class> friend class _LIBCPP_TEMPLATE_VIS forward_list;
  258. template<class> friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;
  259. public:
  260. typedef forward_iterator_tag iterator_category;
  261. typedef typename __traits::__node_value_type value_type;
  262. typedef value_type& reference;
  263. typedef typename pointer_traits<__node_pointer>::difference_type
  264. difference_type;
  265. typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
  266. _LIBCPP_INLINE_VISIBILITY
  267. __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
  268. _LIBCPP_INLINE_VISIBILITY
  269. reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
  270. _LIBCPP_INLINE_VISIBILITY
  271. pointer operator->() const {
  272. return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__value_);
  273. }
  274. _LIBCPP_INLINE_VISIBILITY
  275. __forward_list_iterator& operator++()
  276. {
  277. __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
  278. return *this;
  279. }
  280. _LIBCPP_INLINE_VISIBILITY
  281. __forward_list_iterator operator++(int)
  282. {
  283. __forward_list_iterator __t(*this);
  284. ++(*this);
  285. return __t;
  286. }
  287. friend _LIBCPP_INLINE_VISIBILITY
  288. bool operator==(const __forward_list_iterator& __x,
  289. const __forward_list_iterator& __y)
  290. {return __x.__ptr_ == __y.__ptr_;}
  291. friend _LIBCPP_INLINE_VISIBILITY
  292. bool operator!=(const __forward_list_iterator& __x,
  293. const __forward_list_iterator& __y)
  294. {return !(__x == __y);}
  295. };
  296. template <class _NodeConstPtr>
  297. class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator
  298. {
  299. static_assert((!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value), "");
  300. typedef _NodeConstPtr _NodePtr;
  301. typedef __forward_node_traits<_NodePtr> __traits;
  302. typedef typename __traits::__node __node;
  303. typedef typename __traits::__node_pointer __node_pointer;
  304. typedef typename __traits::__begin_node_pointer __begin_node_pointer;
  305. typedef typename __traits::__iter_node_pointer __iter_node_pointer;
  306. typedef typename __traits::__void_pointer __void_pointer;
  307. __iter_node_pointer __ptr_;
  308. __begin_node_pointer __get_begin() const {
  309. return static_cast<__begin_node_pointer>(
  310. static_cast<__void_pointer>(__ptr_));
  311. }
  312. __node_pointer __get_unsafe_node_pointer() const {
  313. return static_cast<__node_pointer>(
  314. static_cast<__void_pointer>(__ptr_));
  315. }
  316. _LIBCPP_INLINE_VISIBILITY
  317. explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT
  318. : __ptr_(nullptr) {}
  319. _LIBCPP_INLINE_VISIBILITY
  320. explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT
  321. : __ptr_(__traits::__as_iter_node(__p)) {}
  322. _LIBCPP_INLINE_VISIBILITY
  323. explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT
  324. : __ptr_(__traits::__as_iter_node(__p)) {}
  325. template<class, class> friend class forward_list;
  326. public:
  327. typedef forward_iterator_tag iterator_category;
  328. typedef typename __traits::__node_value_type value_type;
  329. typedef const value_type& reference;
  330. typedef typename pointer_traits<__node_pointer>::difference_type
  331. difference_type;
  332. typedef typename __rebind_pointer<__node_pointer, const value_type>::type
  333. pointer;
  334. _LIBCPP_INLINE_VISIBILITY
  335. __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
  336. _LIBCPP_INLINE_VISIBILITY
  337. __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT
  338. : __ptr_(__p.__ptr_) {}
  339. _LIBCPP_INLINE_VISIBILITY
  340. reference operator*() const {return __get_unsafe_node_pointer()->__value_;}
  341. _LIBCPP_INLINE_VISIBILITY
  342. pointer operator->() const {return pointer_traits<pointer>::pointer_to(
  343. __get_unsafe_node_pointer()->__value_);}
  344. _LIBCPP_INLINE_VISIBILITY
  345. __forward_list_const_iterator& operator++()
  346. {
  347. __ptr_ = __traits::__as_iter_node(__ptr_->__next_);
  348. return *this;
  349. }
  350. _LIBCPP_INLINE_VISIBILITY
  351. __forward_list_const_iterator operator++(int)
  352. {
  353. __forward_list_const_iterator __t(*this);
  354. ++(*this);
  355. return __t;
  356. }
  357. friend _LIBCPP_INLINE_VISIBILITY
  358. bool operator==(const __forward_list_const_iterator& __x,
  359. const __forward_list_const_iterator& __y)
  360. {return __x.__ptr_ == __y.__ptr_;}
  361. friend _LIBCPP_INLINE_VISIBILITY
  362. bool operator!=(const __forward_list_const_iterator& __x,
  363. const __forward_list_const_iterator& __y)
  364. {return !(__x == __y);}
  365. };
  366. template <class _Tp, class _Alloc>
  367. class __forward_list_base
  368. {
  369. protected:
  370. typedef _Tp value_type;
  371. typedef _Alloc allocator_type;
  372. typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;
  373. typedef __forward_list_node<value_type, void_pointer> __node;
  374. typedef typename __begin_node_of<value_type, void_pointer>::type __begin_node;
  375. typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, __node>::type __node_allocator;
  376. typedef allocator_traits<__node_allocator> __node_traits;
  377. typedef typename __node_traits::pointer __node_pointer;
  378. typedef typename __rebind_alloc_helper<
  379. allocator_traits<allocator_type>, __begin_node
  380. >::type __begin_node_allocator;
  381. typedef typename allocator_traits<__begin_node_allocator>::pointer
  382. __begin_node_pointer;
  383. static_assert((!is_same<allocator_type, __node_allocator>::value),
  384. "internal allocator type must differ from user-specified "
  385. "type; otherwise overload resolution breaks");
  386. __compressed_pair<__begin_node, __node_allocator> __before_begin_;
  387. _LIBCPP_INLINE_VISIBILITY
  388. __begin_node_pointer __before_begin() _NOEXCEPT
  389. {return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());}
  390. _LIBCPP_INLINE_VISIBILITY
  391. __begin_node_pointer __before_begin() const _NOEXCEPT
  392. {return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));}
  393. _LIBCPP_INLINE_VISIBILITY
  394. __node_allocator& __alloc() _NOEXCEPT
  395. {return __before_begin_.second();}
  396. _LIBCPP_INLINE_VISIBILITY
  397. const __node_allocator& __alloc() const _NOEXCEPT
  398. {return __before_begin_.second();}
  399. typedef __forward_list_iterator<__node_pointer> iterator;
  400. typedef __forward_list_const_iterator<__node_pointer> const_iterator;
  401. _LIBCPP_INLINE_VISIBILITY
  402. __forward_list_base()
  403. _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
  404. : __before_begin_(__begin_node(), __default_init_tag()) {}
  405. _LIBCPP_INLINE_VISIBILITY
  406. explicit __forward_list_base(const allocator_type& __a)
  407. : __before_begin_(__begin_node(), __node_allocator(__a)) {}
  408. _LIBCPP_INLINE_VISIBILITY
  409. explicit __forward_list_base(const __node_allocator& __a)
  410. : __before_begin_(__begin_node(), __a) {}
  411. #ifndef _LIBCPP_CXX03_LANG
  412. public:
  413. _LIBCPP_INLINE_VISIBILITY
  414. __forward_list_base(__forward_list_base&& __x)
  415. _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
  416. _LIBCPP_INLINE_VISIBILITY
  417. __forward_list_base(__forward_list_base&& __x, const allocator_type& __a);
  418. #endif // _LIBCPP_CXX03_LANG
  419. private:
  420. __forward_list_base(const __forward_list_base&);
  421. __forward_list_base& operator=(const __forward_list_base&);
  422. public:
  423. ~__forward_list_base();
  424. protected:
  425. _LIBCPP_INLINE_VISIBILITY
  426. void __copy_assign_alloc(const __forward_list_base& __x)
  427. {__copy_assign_alloc(__x, integral_constant<bool,
  428. __node_traits::propagate_on_container_copy_assignment::value>());}
  429. _LIBCPP_INLINE_VISIBILITY
  430. void __move_assign_alloc(__forward_list_base& __x)
  431. _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
  432. is_nothrow_move_assignable<__node_allocator>::value)
  433. {__move_assign_alloc(__x, integral_constant<bool,
  434. __node_traits::propagate_on_container_move_assignment::value>());}
  435. public:
  436. _LIBCPP_INLINE_VISIBILITY
  437. void swap(__forward_list_base& __x)
  438. #if _LIBCPP_STD_VER >= 14
  439. _NOEXCEPT;
  440. #else
  441. _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
  442. __is_nothrow_swappable<__node_allocator>::value);
  443. #endif
  444. protected:
  445. void clear() _NOEXCEPT;
  446. private:
  447. _LIBCPP_INLINE_VISIBILITY
  448. void __copy_assign_alloc(const __forward_list_base&, false_type) {}
  449. _LIBCPP_INLINE_VISIBILITY
  450. void __copy_assign_alloc(const __forward_list_base& __x, true_type)
  451. {
  452. if (__alloc() != __x.__alloc())
  453. clear();
  454. __alloc() = __x.__alloc();
  455. }
  456. _LIBCPP_INLINE_VISIBILITY
  457. void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT
  458. {}
  459. _LIBCPP_INLINE_VISIBILITY
  460. void __move_assign_alloc(__forward_list_base& __x, true_type)
  461. _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
  462. {__alloc() = _VSTD::move(__x.__alloc());}
  463. };
  464. #ifndef _LIBCPP_CXX03_LANG
  465. template <class _Tp, class _Alloc>
  466. inline
  467. __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x)
  468. _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
  469. : __before_begin_(_VSTD::move(__x.__before_begin_))
  470. {
  471. __x.__before_begin()->__next_ = nullptr;
  472. }
  473. template <class _Tp, class _Alloc>
  474. inline
  475. __forward_list_base<_Tp, _Alloc>::__forward_list_base(__forward_list_base&& __x,
  476. const allocator_type& __a)
  477. : __before_begin_(__begin_node(), __node_allocator(__a))
  478. {
  479. if (__alloc() == __x.__alloc())
  480. {
  481. __before_begin()->__next_ = __x.__before_begin()->__next_;
  482. __x.__before_begin()->__next_ = nullptr;
  483. }
  484. }
  485. #endif // _LIBCPP_CXX03_LANG
  486. template <class _Tp, class _Alloc>
  487. __forward_list_base<_Tp, _Alloc>::~__forward_list_base()
  488. {
  489. clear();
  490. }
  491. template <class _Tp, class _Alloc>
  492. inline
  493. void
  494. __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
  495. #if _LIBCPP_STD_VER >= 14
  496. _NOEXCEPT
  497. #else
  498. _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
  499. __is_nothrow_swappable<__node_allocator>::value)
  500. #endif
  501. {
  502. _VSTD::__swap_allocator(__alloc(), __x.__alloc(),
  503. integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
  504. using _VSTD::swap;
  505. swap(__before_begin()->__next_, __x.__before_begin()->__next_);
  506. }
  507. template <class _Tp, class _Alloc>
  508. void
  509. __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT
  510. {
  511. __node_allocator& __a = __alloc();
  512. for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;)
  513. {
  514. __node_pointer __next = __p->__next_;
  515. __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
  516. __node_traits::deallocate(__a, __p, 1);
  517. __p = __next;
  518. }
  519. __before_begin()->__next_ = nullptr;
  520. }
  521. template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
  522. class _LIBCPP_TEMPLATE_VIS forward_list
  523. : private __forward_list_base<_Tp, _Alloc>
  524. {
  525. typedef __forward_list_base<_Tp, _Alloc> base;
  526. typedef typename base::__node_allocator __node_allocator;
  527. typedef typename base::__node __node;
  528. typedef typename base::__node_traits __node_traits;
  529. typedef typename base::__node_pointer __node_pointer;
  530. typedef typename base::__begin_node_pointer __begin_node_pointer;
  531. public:
  532. typedef _Tp value_type;
  533. typedef _Alloc allocator_type;
  534. static_assert((is_same<typename allocator_type::value_type, value_type>::value),
  535. "Allocator::value_type must be same type as value_type");
  536. typedef value_type& reference;
  537. typedef const value_type& const_reference;
  538. typedef typename allocator_traits<allocator_type>::pointer pointer;
  539. typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
  540. typedef typename allocator_traits<allocator_type>::size_type size_type;
  541. typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  542. typedef typename base::iterator iterator;
  543. typedef typename base::const_iterator const_iterator;
  544. #if _LIBCPP_STD_VER > 17
  545. typedef size_type __remove_return_type;
  546. #else
  547. typedef void __remove_return_type;
  548. #endif
  549. _LIBCPP_INLINE_VISIBILITY
  550. forward_list()
  551. _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
  552. {} // = default;
  553. _LIBCPP_INLINE_VISIBILITY
  554. explicit forward_list(const allocator_type& __a);
  555. explicit forward_list(size_type __n);
  556. #if _LIBCPP_STD_VER > 11
  557. explicit forward_list(size_type __n, const allocator_type& __a);
  558. #endif
  559. forward_list(size_type __n, const value_type& __v);
  560. template <class = __enable_if_t<__is_allocator<_Alloc>::value> >
  561. forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : base(__a)
  562. {
  563. insert_after(cbefore_begin(), __n, __v);
  564. }
  565. template <class _InputIterator>
  566. forward_list(_InputIterator __f, _InputIterator __l,
  567. typename enable_if<
  568. __is_cpp17_input_iterator<_InputIterator>::value
  569. >::type* = nullptr);
  570. template <class _InputIterator>
  571. forward_list(_InputIterator __f, _InputIterator __l,
  572. const allocator_type& __a,
  573. typename enable_if<
  574. __is_cpp17_input_iterator<_InputIterator>::value
  575. >::type* = nullptr);
  576. forward_list(const forward_list& __x);
  577. forward_list(const forward_list& __x, const __identity_t<allocator_type>& __a);
  578. forward_list& operator=(const forward_list& __x);
  579. #ifndef _LIBCPP_CXX03_LANG
  580. _LIBCPP_INLINE_VISIBILITY
  581. forward_list(forward_list&& __x)
  582. _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
  583. : base(_VSTD::move(__x)) {}
  584. forward_list(forward_list&& __x, const __identity_t<allocator_type>& __a);
  585. forward_list(initializer_list<value_type> __il);
  586. forward_list(initializer_list<value_type> __il, const allocator_type& __a);
  587. _LIBCPP_INLINE_VISIBILITY
  588. forward_list& operator=(forward_list&& __x)
  589. _NOEXCEPT_(
  590. __node_traits::propagate_on_container_move_assignment::value &&
  591. is_nothrow_move_assignable<allocator_type>::value);
  592. _LIBCPP_INLINE_VISIBILITY
  593. forward_list& operator=(initializer_list<value_type> __il);
  594. _LIBCPP_INLINE_VISIBILITY
  595. void assign(initializer_list<value_type> __il);
  596. #endif // _LIBCPP_CXX03_LANG
  597. // ~forward_list() = default;
  598. template <class _InputIterator>
  599. typename enable_if
  600. <
  601. __is_cpp17_input_iterator<_InputIterator>::value,
  602. void
  603. >::type
  604. assign(_InputIterator __f, _InputIterator __l);
  605. void assign(size_type __n, const value_type& __v);
  606. _LIBCPP_INLINE_VISIBILITY
  607. allocator_type get_allocator() const _NOEXCEPT
  608. {return allocator_type(base::__alloc());}
  609. _LIBCPP_INLINE_VISIBILITY
  610. iterator begin() _NOEXCEPT
  611. {return iterator(base::__before_begin()->__next_);}
  612. _LIBCPP_INLINE_VISIBILITY
  613. const_iterator begin() const _NOEXCEPT
  614. {return const_iterator(base::__before_begin()->__next_);}
  615. _LIBCPP_INLINE_VISIBILITY
  616. iterator end() _NOEXCEPT
  617. {return iterator(nullptr);}
  618. _LIBCPP_INLINE_VISIBILITY
  619. const_iterator end() const _NOEXCEPT
  620. {return const_iterator(nullptr);}
  621. _LIBCPP_INLINE_VISIBILITY
  622. const_iterator cbegin() const _NOEXCEPT
  623. {return const_iterator(base::__before_begin()->__next_);}
  624. _LIBCPP_INLINE_VISIBILITY
  625. const_iterator cend() const _NOEXCEPT
  626. {return const_iterator(nullptr);}
  627. _LIBCPP_INLINE_VISIBILITY
  628. iterator before_begin() _NOEXCEPT
  629. {return iterator(base::__before_begin());}
  630. _LIBCPP_INLINE_VISIBILITY
  631. const_iterator before_begin() const _NOEXCEPT
  632. {return const_iterator(base::__before_begin());}
  633. _LIBCPP_INLINE_VISIBILITY
  634. const_iterator cbefore_begin() const _NOEXCEPT
  635. {return const_iterator(base::__before_begin());}
  636. _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
  637. bool empty() const _NOEXCEPT
  638. {return base::__before_begin()->__next_ == nullptr;}
  639. _LIBCPP_INLINE_VISIBILITY
  640. size_type max_size() const _NOEXCEPT {
  641. return _VSTD::min<size_type>(
  642. __node_traits::max_size(base::__alloc()),
  643. numeric_limits<difference_type>::max());
  644. }
  645. _LIBCPP_INLINE_VISIBILITY
  646. reference front() {return base::__before_begin()->__next_->__value_;}
  647. _LIBCPP_INLINE_VISIBILITY
  648. const_reference front() const {return base::__before_begin()->__next_->__value_;}
  649. #ifndef _LIBCPP_CXX03_LANG
  650. #if _LIBCPP_STD_VER > 14
  651. template <class... _Args> reference emplace_front(_Args&&... __args);
  652. #else
  653. template <class... _Args> void emplace_front(_Args&&... __args);
  654. #endif
  655. void push_front(value_type&& __v);
  656. #endif // _LIBCPP_CXX03_LANG
  657. void push_front(const value_type& __v);
  658. void pop_front();
  659. #ifndef _LIBCPP_CXX03_LANG
  660. template <class... _Args>
  661. iterator emplace_after(const_iterator __p, _Args&&... __args);
  662. iterator insert_after(const_iterator __p, value_type&& __v);
  663. iterator insert_after(const_iterator __p, initializer_list<value_type> __il)
  664. {return insert_after(__p, __il.begin(), __il.end());}
  665. #endif // _LIBCPP_CXX03_LANG
  666. iterator insert_after(const_iterator __p, const value_type& __v);
  667. iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);
  668. template <class _InputIterator>
  669. _LIBCPP_INLINE_VISIBILITY
  670. typename enable_if
  671. <
  672. __is_cpp17_input_iterator<_InputIterator>::value,
  673. iterator
  674. >::type
  675. insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);
  676. iterator erase_after(const_iterator __p);
  677. iterator erase_after(const_iterator __f, const_iterator __l);
  678. _LIBCPP_INLINE_VISIBILITY
  679. void swap(forward_list& __x)
  680. #if _LIBCPP_STD_VER >= 14
  681. _NOEXCEPT
  682. #else
  683. _NOEXCEPT_(!__node_traits::propagate_on_container_swap::value ||
  684. __is_nothrow_swappable<__node_allocator>::value)
  685. #endif
  686. {base::swap(__x);}
  687. void resize(size_type __n);
  688. void resize(size_type __n, const value_type& __v);
  689. _LIBCPP_INLINE_VISIBILITY
  690. void clear() _NOEXCEPT {base::clear();}
  691. _LIBCPP_INLINE_VISIBILITY
  692. void splice_after(const_iterator __p, forward_list&& __x);
  693. _LIBCPP_INLINE_VISIBILITY
  694. void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);
  695. _LIBCPP_INLINE_VISIBILITY
  696. void splice_after(const_iterator __p, forward_list&& __x,
  697. const_iterator __f, const_iterator __l);
  698. void splice_after(const_iterator __p, forward_list& __x);
  699. void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);
  700. void splice_after(const_iterator __p, forward_list& __x,
  701. const_iterator __f, const_iterator __l);
  702. __remove_return_type remove(const value_type& __v);
  703. template <class _Predicate> __remove_return_type remove_if(_Predicate __pred);
  704. _LIBCPP_INLINE_VISIBILITY
  705. __remove_return_type unique() {return unique(__equal_to<value_type>());}
  706. template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred);
  707. #ifndef _LIBCPP_CXX03_LANG
  708. _LIBCPP_INLINE_VISIBILITY
  709. void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
  710. template <class _Compare>
  711. _LIBCPP_INLINE_VISIBILITY
  712. void merge(forward_list&& __x, _Compare __comp)
  713. {merge(__x, _VSTD::move(__comp));}
  714. #endif // _LIBCPP_CXX03_LANG
  715. _LIBCPP_INLINE_VISIBILITY
  716. void merge(forward_list& __x) {merge(__x, __less<value_type>());}
  717. template <class _Compare> void merge(forward_list& __x, _Compare __comp);
  718. _LIBCPP_INLINE_VISIBILITY
  719. void sort() {sort(__less<value_type>());}
  720. template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
  721. void reverse() _NOEXCEPT;
  722. private:
  723. #ifndef _LIBCPP_CXX03_LANG
  724. void __move_assign(forward_list& __x, true_type)
  725. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
  726. void __move_assign(forward_list& __x, false_type);
  727. #endif // _LIBCPP_CXX03_LANG
  728. template <class _Compare>
  729. static
  730. __node_pointer
  731. __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);
  732. template <class _Compare>
  733. static
  734. __node_pointer
  735. __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);
  736. };
  737. #if _LIBCPP_STD_VER >= 17
  738. template<class _InputIterator,
  739. class _Alloc = allocator<__iter_value_type<_InputIterator>>,
  740. class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
  741. class = enable_if_t<__is_allocator<_Alloc>::value>
  742. >
  743. forward_list(_InputIterator, _InputIterator)
  744. -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
  745. template<class _InputIterator,
  746. class _Alloc,
  747. class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
  748. class = enable_if_t<__is_allocator<_Alloc>::value>
  749. >
  750. forward_list(_InputIterator, _InputIterator, _Alloc)
  751. -> forward_list<__iter_value_type<_InputIterator>, _Alloc>;
  752. #endif
  753. template <class _Tp, class _Alloc>
  754. inline
  755. forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a)
  756. : base(__a)
  757. {
  758. }
  759. template <class _Tp, class _Alloc>
  760. forward_list<_Tp, _Alloc>::forward_list(size_type __n)
  761. {
  762. if (__n > 0)
  763. {
  764. __node_allocator& __a = base::__alloc();
  765. typedef __allocator_destructor<__node_allocator> _Dp;
  766. unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
  767. for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
  768. __p = __p->__next_as_begin())
  769. {
  770. __h.reset(__node_traits::allocate(__a, 1));
  771. __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
  772. __h->__next_ = nullptr;
  773. __p->__next_ = __h.release();
  774. }
  775. }
  776. }
  777. #if _LIBCPP_STD_VER > 11
  778. template <class _Tp, class _Alloc>
  779. forward_list<_Tp, _Alloc>::forward_list(size_type __n,
  780. const allocator_type& __base_alloc)
  781. : base ( __base_alloc )
  782. {
  783. if (__n > 0)
  784. {
  785. __node_allocator& __a = base::__alloc();
  786. typedef __allocator_destructor<__node_allocator> _Dp;
  787. unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
  788. for (__begin_node_pointer __p = base::__before_begin(); __n > 0; --__n,
  789. __p = __p->__next_as_begin())
  790. {
  791. __h.reset(__node_traits::allocate(__a, 1));
  792. __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
  793. __h->__next_ = nullptr;
  794. __p->__next_ = __h.release();
  795. }
  796. }
  797. }
  798. #endif
  799. template <class _Tp, class _Alloc>
  800. forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v)
  801. {
  802. insert_after(cbefore_begin(), __n, __v);
  803. }
  804. template <class _Tp, class _Alloc>
  805. template <class _InputIterator>
  806. forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
  807. typename enable_if<
  808. __is_cpp17_input_iterator<_InputIterator>::value
  809. >::type*)
  810. {
  811. insert_after(cbefore_begin(), __f, __l);
  812. }
  813. template <class _Tp, class _Alloc>
  814. template <class _InputIterator>
  815. forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l,
  816. const allocator_type& __a,
  817. typename enable_if<
  818. __is_cpp17_input_iterator<_InputIterator>::value
  819. >::type*)
  820. : base(__a)
  821. {
  822. insert_after(cbefore_begin(), __f, __l);
  823. }
  824. template <class _Tp, class _Alloc>
  825. forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
  826. : base(
  827. __node_traits::select_on_container_copy_construction(__x.__alloc())) {
  828. insert_after(cbefore_begin(), __x.begin(), __x.end());
  829. }
  830. template <class _Tp, class _Alloc>
  831. forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
  832. const __identity_t<allocator_type>& __a)
  833. : base(__a)
  834. {
  835. insert_after(cbefore_begin(), __x.begin(), __x.end());
  836. }
  837. template <class _Tp, class _Alloc>
  838. forward_list<_Tp, _Alloc>&
  839. forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
  840. {
  841. if (this != _VSTD::addressof(__x))
  842. {
  843. base::__copy_assign_alloc(__x);
  844. assign(__x.begin(), __x.end());
  845. }
  846. return *this;
  847. }
  848. #ifndef _LIBCPP_CXX03_LANG
  849. template <class _Tp, class _Alloc>
  850. forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
  851. const __identity_t<allocator_type>& __a)
  852. : base(_VSTD::move(__x), __a)
  853. {
  854. if (base::__alloc() != __x.__alloc())
  855. {
  856. typedef move_iterator<iterator> _Ip;
  857. insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
  858. }
  859. }
  860. template <class _Tp, class _Alloc>
  861. forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il)
  862. {
  863. insert_after(cbefore_begin(), __il.begin(), __il.end());
  864. }
  865. template <class _Tp, class _Alloc>
  866. forward_list<_Tp, _Alloc>::forward_list(initializer_list<value_type> __il,
  867. const allocator_type& __a)
  868. : base(__a)
  869. {
  870. insert_after(cbefore_begin(), __il.begin(), __il.end());
  871. }
  872. template <class _Tp, class _Alloc>
  873. void
  874. forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, true_type)
  875. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  876. {
  877. clear();
  878. base::__move_assign_alloc(__x);
  879. base::__before_begin()->__next_ = __x.__before_begin()->__next_;
  880. __x.__before_begin()->__next_ = nullptr;
  881. }
  882. template <class _Tp, class _Alloc>
  883. void
  884. forward_list<_Tp, _Alloc>::__move_assign(forward_list& __x, false_type)
  885. {
  886. if (base::__alloc() == __x.__alloc())
  887. __move_assign(__x, true_type());
  888. else
  889. {
  890. typedef move_iterator<iterator> _Ip;
  891. assign(_Ip(__x.begin()), _Ip(__x.end()));
  892. }
  893. }
  894. template <class _Tp, class _Alloc>
  895. inline
  896. forward_list<_Tp, _Alloc>&
  897. forward_list<_Tp, _Alloc>::operator=(forward_list&& __x)
  898. _NOEXCEPT_(
  899. __node_traits::propagate_on_container_move_assignment::value &&
  900. is_nothrow_move_assignable<allocator_type>::value)
  901. {
  902. __move_assign(__x, integral_constant<bool,
  903. __node_traits::propagate_on_container_move_assignment::value>());
  904. return *this;
  905. }
  906. template <class _Tp, class _Alloc>
  907. inline
  908. forward_list<_Tp, _Alloc>&
  909. forward_list<_Tp, _Alloc>::operator=(initializer_list<value_type> __il)
  910. {
  911. assign(__il.begin(), __il.end());
  912. return *this;
  913. }
  914. #endif // _LIBCPP_CXX03_LANG
  915. template <class _Tp, class _Alloc>
  916. template <class _InputIterator>
  917. typename enable_if
  918. <
  919. __is_cpp17_input_iterator<_InputIterator>::value,
  920. void
  921. >::type
  922. forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l)
  923. {
  924. iterator __i = before_begin();
  925. iterator __j = _VSTD::next(__i);
  926. iterator __e = end();
  927. for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f)
  928. *__j = *__f;
  929. if (__j == __e)
  930. insert_after(__i, __f, __l);
  931. else
  932. erase_after(__i, __e);
  933. }
  934. template <class _Tp, class _Alloc>
  935. void
  936. forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v)
  937. {
  938. iterator __i = before_begin();
  939. iterator __j = _VSTD::next(__i);
  940. iterator __e = end();
  941. for (; __j != __e && __n > 0; --__n, ++__i, ++__j)
  942. *__j = __v;
  943. if (__j == __e)
  944. insert_after(__i, __n, __v);
  945. else
  946. erase_after(__i, __e);
  947. }
  948. #ifndef _LIBCPP_CXX03_LANG
  949. template <class _Tp, class _Alloc>
  950. inline
  951. void
  952. forward_list<_Tp, _Alloc>::assign(initializer_list<value_type> __il)
  953. {
  954. assign(__il.begin(), __il.end());
  955. }
  956. template <class _Tp, class _Alloc>
  957. template <class... _Args>
  958. #if _LIBCPP_STD_VER > 14
  959. typename forward_list<_Tp, _Alloc>::reference
  960. #else
  961. void
  962. #endif
  963. forward_list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
  964. {
  965. __node_allocator& __a = base::__alloc();
  966. typedef __allocator_destructor<__node_allocator> _Dp;
  967. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  968. __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
  969. _VSTD::forward<_Args>(__args)...);
  970. __h->__next_ = base::__before_begin()->__next_;
  971. base::__before_begin()->__next_ = __h.release();
  972. #if _LIBCPP_STD_VER > 14
  973. return base::__before_begin()->__next_->__value_;
  974. #endif
  975. }
  976. template <class _Tp, class _Alloc>
  977. void
  978. forward_list<_Tp, _Alloc>::push_front(value_type&& __v)
  979. {
  980. __node_allocator& __a = base::__alloc();
  981. typedef __allocator_destructor<__node_allocator> _Dp;
  982. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  983. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
  984. __h->__next_ = base::__before_begin()->__next_;
  985. base::__before_begin()->__next_ = __h.release();
  986. }
  987. #endif // _LIBCPP_CXX03_LANG
  988. template <class _Tp, class _Alloc>
  989. void
  990. forward_list<_Tp, _Alloc>::push_front(const value_type& __v)
  991. {
  992. __node_allocator& __a = base::__alloc();
  993. typedef __allocator_destructor<__node_allocator> _Dp;
  994. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  995. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
  996. __h->__next_ = base::__before_begin()->__next_;
  997. base::__before_begin()->__next_ = __h.release();
  998. }
  999. template <class _Tp, class _Alloc>
  1000. void
  1001. forward_list<_Tp, _Alloc>::pop_front()
  1002. {
  1003. __node_allocator& __a = base::__alloc();
  1004. __node_pointer __p = base::__before_begin()->__next_;
  1005. base::__before_begin()->__next_ = __p->__next_;
  1006. __node_traits::destroy(__a, _VSTD::addressof(__p->__value_));
  1007. __node_traits::deallocate(__a, __p, 1);
  1008. }
  1009. #ifndef _LIBCPP_CXX03_LANG
  1010. template <class _Tp, class _Alloc>
  1011. template <class... _Args>
  1012. typename forward_list<_Tp, _Alloc>::iterator
  1013. forward_list<_Tp, _Alloc>::emplace_after(const_iterator __p, _Args&&... __args)
  1014. {
  1015. __begin_node_pointer const __r = __p.__get_begin();
  1016. __node_allocator& __a = base::__alloc();
  1017. typedef __allocator_destructor<__node_allocator> _Dp;
  1018. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  1019. __node_traits::construct(__a, _VSTD::addressof(__h->__value_),
  1020. _VSTD::forward<_Args>(__args)...);
  1021. __h->__next_ = __r->__next_;
  1022. __r->__next_ = __h.release();
  1023. return iterator(__r->__next_);
  1024. }
  1025. template <class _Tp, class _Alloc>
  1026. typename forward_list<_Tp, _Alloc>::iterator
  1027. forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, value_type&& __v)
  1028. {
  1029. __begin_node_pointer const __r = __p.__get_begin();
  1030. __node_allocator& __a = base::__alloc();
  1031. typedef __allocator_destructor<__node_allocator> _Dp;
  1032. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  1033. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
  1034. __h->__next_ = __r->__next_;
  1035. __r->__next_ = __h.release();
  1036. return iterator(__r->__next_);
  1037. }
  1038. #endif // _LIBCPP_CXX03_LANG
  1039. template <class _Tp, class _Alloc>
  1040. typename forward_list<_Tp, _Alloc>::iterator
  1041. forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v)
  1042. {
  1043. __begin_node_pointer const __r = __p.__get_begin();
  1044. __node_allocator& __a = base::__alloc();
  1045. typedef __allocator_destructor<__node_allocator> _Dp;
  1046. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  1047. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
  1048. __h->__next_ = __r->__next_;
  1049. __r->__next_ = __h.release();
  1050. return iterator(__r->__next_);
  1051. }
  1052. template <class _Tp, class _Alloc>
  1053. typename forward_list<_Tp, _Alloc>::iterator
  1054. forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n,
  1055. const value_type& __v)
  1056. {
  1057. __begin_node_pointer __r = __p.__get_begin();
  1058. if (__n > 0)
  1059. {
  1060. __node_allocator& __a = base::__alloc();
  1061. typedef __allocator_destructor<__node_allocator> _Dp;
  1062. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  1063. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
  1064. __node_pointer __first = __h.release();
  1065. __node_pointer __last = __first;
  1066. #ifndef _LIBCPP_NO_EXCEPTIONS
  1067. try
  1068. {
  1069. #endif // _LIBCPP_NO_EXCEPTIONS
  1070. for (--__n; __n != 0; --__n, __last = __last->__next_)
  1071. {
  1072. __h.reset(__node_traits::allocate(__a, 1));
  1073. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
  1074. __last->__next_ = __h.release();
  1075. }
  1076. #ifndef _LIBCPP_NO_EXCEPTIONS
  1077. }
  1078. catch (...)
  1079. {
  1080. while (__first != nullptr)
  1081. {
  1082. __node_pointer __next = __first->__next_;
  1083. __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
  1084. __node_traits::deallocate(__a, __first, 1);
  1085. __first = __next;
  1086. }
  1087. throw;
  1088. }
  1089. #endif // _LIBCPP_NO_EXCEPTIONS
  1090. __last->__next_ = __r->__next_;
  1091. __r->__next_ = __first;
  1092. __r = static_cast<__begin_node_pointer>(__last);
  1093. }
  1094. return iterator(__r);
  1095. }
  1096. template <class _Tp, class _Alloc>
  1097. template <class _InputIterator>
  1098. typename enable_if
  1099. <
  1100. __is_cpp17_input_iterator<_InputIterator>::value,
  1101. typename forward_list<_Tp, _Alloc>::iterator
  1102. >::type
  1103. forward_list<_Tp, _Alloc>::insert_after(const_iterator __p,
  1104. _InputIterator __f, _InputIterator __l)
  1105. {
  1106. __begin_node_pointer __r = __p.__get_begin();
  1107. if (__f != __l)
  1108. {
  1109. __node_allocator& __a = base::__alloc();
  1110. typedef __allocator_destructor<__node_allocator> _Dp;
  1111. unique_ptr<__node, _Dp> __h(__node_traits::allocate(__a, 1), _Dp(__a, 1));
  1112. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
  1113. __node_pointer __first = __h.release();
  1114. __node_pointer __last = __first;
  1115. #ifndef _LIBCPP_NO_EXCEPTIONS
  1116. try
  1117. {
  1118. #endif // _LIBCPP_NO_EXCEPTIONS
  1119. for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_)))
  1120. {
  1121. __h.reset(__node_traits::allocate(__a, 1));
  1122. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), *__f);
  1123. __last->__next_ = __h.release();
  1124. }
  1125. #ifndef _LIBCPP_NO_EXCEPTIONS
  1126. }
  1127. catch (...)
  1128. {
  1129. while (__first != nullptr)
  1130. {
  1131. __node_pointer __next = __first->__next_;
  1132. __node_traits::destroy(__a, _VSTD::addressof(__first->__value_));
  1133. __node_traits::deallocate(__a, __first, 1);
  1134. __first = __next;
  1135. }
  1136. throw;
  1137. }
  1138. #endif // _LIBCPP_NO_EXCEPTIONS
  1139. __last->__next_ = __r->__next_;
  1140. __r->__next_ = __first;
  1141. __r = static_cast<__begin_node_pointer>(__last);
  1142. }
  1143. return iterator(__r);
  1144. }
  1145. template <class _Tp, class _Alloc>
  1146. typename forward_list<_Tp, _Alloc>::iterator
  1147. forward_list<_Tp, _Alloc>::erase_after(const_iterator __f)
  1148. {
  1149. __begin_node_pointer __p = __f.__get_begin();
  1150. __node_pointer __n = __p->__next_;
  1151. __p->__next_ = __n->__next_;
  1152. __node_allocator& __a = base::__alloc();
  1153. __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
  1154. __node_traits::deallocate(__a, __n, 1);
  1155. return iterator(__p->__next_);
  1156. }
  1157. template <class _Tp, class _Alloc>
  1158. typename forward_list<_Tp, _Alloc>::iterator
  1159. forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
  1160. {
  1161. __node_pointer __e = __l.__get_unsafe_node_pointer();
  1162. if (__f != __l)
  1163. {
  1164. __begin_node_pointer __bp = __f.__get_begin();
  1165. __node_pointer __n = __bp->__next_;
  1166. if (__n != __e)
  1167. {
  1168. __bp->__next_ = __e;
  1169. __node_allocator& __a = base::__alloc();
  1170. do
  1171. {
  1172. __node_pointer __tmp = __n->__next_;
  1173. __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
  1174. __node_traits::deallocate(__a, __n, 1);
  1175. __n = __tmp;
  1176. } while (__n != __e);
  1177. }
  1178. }
  1179. return iterator(__e);
  1180. }
  1181. template <class _Tp, class _Alloc>
  1182. void
  1183. forward_list<_Tp, _Alloc>::resize(size_type __n)
  1184. {
  1185. size_type __sz = 0;
  1186. iterator __p = before_begin();
  1187. iterator __i = begin();
  1188. iterator __e = end();
  1189. for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
  1190. ;
  1191. if (__i != __e)
  1192. erase_after(__p, __e);
  1193. else
  1194. {
  1195. __n -= __sz;
  1196. if (__n > 0)
  1197. {
  1198. __node_allocator& __a = base::__alloc();
  1199. typedef __allocator_destructor<__node_allocator> _Dp;
  1200. unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
  1201. for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
  1202. __ptr = __ptr->__next_as_begin())
  1203. {
  1204. __h.reset(__node_traits::allocate(__a, 1));
  1205. __node_traits::construct(__a, _VSTD::addressof(__h->__value_));
  1206. __h->__next_ = nullptr;
  1207. __ptr->__next_ = __h.release();
  1208. }
  1209. }
  1210. }
  1211. }
  1212. template <class _Tp, class _Alloc>
  1213. void
  1214. forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v)
  1215. {
  1216. size_type __sz = 0;
  1217. iterator __p = before_begin();
  1218. iterator __i = begin();
  1219. iterator __e = end();
  1220. for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)
  1221. ;
  1222. if (__i != __e)
  1223. erase_after(__p, __e);
  1224. else
  1225. {
  1226. __n -= __sz;
  1227. if (__n > 0)
  1228. {
  1229. __node_allocator& __a = base::__alloc();
  1230. typedef __allocator_destructor<__node_allocator> _Dp;
  1231. unique_ptr<__node, _Dp> __h(nullptr, _Dp(__a, 1));
  1232. for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n,
  1233. __ptr = __ptr->__next_as_begin())
  1234. {
  1235. __h.reset(__node_traits::allocate(__a, 1));
  1236. __node_traits::construct(__a, _VSTD::addressof(__h->__value_), __v);
  1237. __h->__next_ = nullptr;
  1238. __ptr->__next_ = __h.release();
  1239. }
  1240. }
  1241. }
  1242. }
  1243. template <class _Tp, class _Alloc>
  1244. void
  1245. forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
  1246. forward_list& __x)
  1247. {
  1248. if (!__x.empty())
  1249. {
  1250. if (__p.__get_begin()->__next_ != nullptr)
  1251. {
  1252. const_iterator __lm1 = __x.before_begin();
  1253. while (__lm1.__get_begin()->__next_ != nullptr)
  1254. ++__lm1;
  1255. __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
  1256. }
  1257. __p.__get_begin()->__next_ = __x.__before_begin()->__next_;
  1258. __x.__before_begin()->__next_ = nullptr;
  1259. }
  1260. }
  1261. template <class _Tp, class _Alloc>
  1262. void
  1263. forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
  1264. forward_list& /*__other*/,
  1265. const_iterator __i)
  1266. {
  1267. const_iterator __lm1 = _VSTD::next(__i);
  1268. if (__p != __i && __p != __lm1)
  1269. {
  1270. __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;
  1271. __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
  1272. __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();
  1273. }
  1274. }
  1275. template <class _Tp, class _Alloc>
  1276. void
  1277. forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
  1278. forward_list& /*__other*/,
  1279. const_iterator __f, const_iterator __l)
  1280. {
  1281. if (__f != __l && __p != __f)
  1282. {
  1283. const_iterator __lm1 = __f;
  1284. while (__lm1.__get_begin()->__next_ != __l.__get_begin())
  1285. ++__lm1;
  1286. if (__f != __lm1)
  1287. {
  1288. __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;
  1289. __p.__get_begin()->__next_ = __f.__get_begin()->__next_;
  1290. __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();
  1291. }
  1292. }
  1293. }
  1294. template <class _Tp, class _Alloc>
  1295. inline _LIBCPP_INLINE_VISIBILITY
  1296. void
  1297. forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
  1298. forward_list&& __x)
  1299. {
  1300. splice_after(__p, __x);
  1301. }
  1302. template <class _Tp, class _Alloc>
  1303. inline _LIBCPP_INLINE_VISIBILITY
  1304. void
  1305. forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
  1306. forward_list&& __x,
  1307. const_iterator __i)
  1308. {
  1309. splice_after(__p, __x, __i);
  1310. }
  1311. template <class _Tp, class _Alloc>
  1312. inline _LIBCPP_INLINE_VISIBILITY
  1313. void
  1314. forward_list<_Tp, _Alloc>::splice_after(const_iterator __p,
  1315. forward_list&& __x,
  1316. const_iterator __f, const_iterator __l)
  1317. {
  1318. splice_after(__p, __x, __f, __l);
  1319. }
  1320. template <class _Tp, class _Alloc>
  1321. typename forward_list<_Tp, _Alloc>::__remove_return_type
  1322. forward_list<_Tp, _Alloc>::remove(const value_type& __v)
  1323. {
  1324. forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
  1325. typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
  1326. const iterator __e = end();
  1327. for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
  1328. {
  1329. if (__i.__get_begin()->__next_->__value_ == __v)
  1330. {
  1331. ++__count_removed;
  1332. iterator __j = _VSTD::next(__i, 2);
  1333. for (; __j != __e && *__j == __v; ++__j)
  1334. ++__count_removed;
  1335. __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
  1336. if (__j == __e)
  1337. break;
  1338. __i = __j;
  1339. }
  1340. else
  1341. ++__i;
  1342. }
  1343. return (__remove_return_type) __count_removed;
  1344. }
  1345. template <class _Tp, class _Alloc>
  1346. template <class _Predicate>
  1347. typename forward_list<_Tp, _Alloc>::__remove_return_type
  1348. forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
  1349. {
  1350. forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
  1351. typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
  1352. const iterator __e = end();
  1353. for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;)
  1354. {
  1355. if (__pred(__i.__get_begin()->__next_->__value_))
  1356. {
  1357. ++__count_removed;
  1358. iterator __j = _VSTD::next(__i, 2);
  1359. for (; __j != __e && __pred(*__j); ++__j)
  1360. ++__count_removed;
  1361. __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
  1362. if (__j == __e)
  1363. break;
  1364. __i = __j;
  1365. }
  1366. else
  1367. ++__i;
  1368. }
  1369. return (__remove_return_type) __count_removed;
  1370. }
  1371. template <class _Tp, class _Alloc>
  1372. template <class _BinaryPredicate>
  1373. typename forward_list<_Tp, _Alloc>::__remove_return_type
  1374. forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
  1375. {
  1376. forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
  1377. typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;
  1378. for (iterator __i = begin(), __e = end(); __i != __e;)
  1379. {
  1380. iterator __j = _VSTD::next(__i);
  1381. for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
  1382. ++__count_removed;
  1383. if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())
  1384. __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);
  1385. __i = __j;
  1386. }
  1387. return (__remove_return_type) __count_removed;
  1388. }
  1389. template <class _Tp, class _Alloc>
  1390. template <class _Compare>
  1391. void
  1392. forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp)
  1393. {
  1394. if (this != _VSTD::addressof(__x))
  1395. {
  1396. base::__before_begin()->__next_ = __merge(base::__before_begin()->__next_,
  1397. __x.__before_begin()->__next_,
  1398. __comp);
  1399. __x.__before_begin()->__next_ = nullptr;
  1400. }
  1401. }
  1402. template <class _Tp, class _Alloc>
  1403. template <class _Compare>
  1404. typename forward_list<_Tp, _Alloc>::__node_pointer
  1405. forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2,
  1406. _Compare& __comp)
  1407. {
  1408. if (__f1 == nullptr)
  1409. return __f2;
  1410. if (__f2 == nullptr)
  1411. return __f1;
  1412. __node_pointer __r;
  1413. if (__comp(__f2->__value_, __f1->__value_))
  1414. {
  1415. __node_pointer __t = __f2;
  1416. while (__t->__next_ != nullptr &&
  1417. __comp(__t->__next_->__value_, __f1->__value_))
  1418. __t = __t->__next_;
  1419. __r = __f2;
  1420. __f2 = __t->__next_;
  1421. __t->__next_ = __f1;
  1422. }
  1423. else
  1424. __r = __f1;
  1425. __node_pointer __p = __f1;
  1426. __f1 = __f1->__next_;
  1427. while (__f1 != nullptr && __f2 != nullptr)
  1428. {
  1429. if (__comp(__f2->__value_, __f1->__value_))
  1430. {
  1431. __node_pointer __t = __f2;
  1432. while (__t->__next_ != nullptr &&
  1433. __comp(__t->__next_->__value_, __f1->__value_))
  1434. __t = __t->__next_;
  1435. __p->__next_ = __f2;
  1436. __f2 = __t->__next_;
  1437. __t->__next_ = __f1;
  1438. }
  1439. __p = __f1;
  1440. __f1 = __f1->__next_;
  1441. }
  1442. if (__f2 != nullptr)
  1443. __p->__next_ = __f2;
  1444. return __r;
  1445. }
  1446. template <class _Tp, class _Alloc>
  1447. template <class _Compare>
  1448. inline
  1449. void
  1450. forward_list<_Tp, _Alloc>::sort(_Compare __comp)
  1451. {
  1452. base::__before_begin()->__next_ = __sort(base::__before_begin()->__next_,
  1453. _VSTD::distance(begin(), end()), __comp);
  1454. }
  1455. template <class _Tp, class _Alloc>
  1456. template <class _Compare>
  1457. typename forward_list<_Tp, _Alloc>::__node_pointer
  1458. forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz,
  1459. _Compare& __comp)
  1460. {
  1461. switch (__sz)
  1462. {
  1463. case 0:
  1464. case 1:
  1465. return __f1;
  1466. case 2:
  1467. if (__comp(__f1->__next_->__value_, __f1->__value_))
  1468. {
  1469. __node_pointer __t = __f1->__next_;
  1470. __t->__next_ = __f1;
  1471. __f1->__next_ = nullptr;
  1472. __f1 = __t;
  1473. }
  1474. return __f1;
  1475. }
  1476. difference_type __sz1 = __sz / 2;
  1477. difference_type __sz2 = __sz - __sz1;
  1478. __node_pointer __t = _VSTD::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();
  1479. __node_pointer __f2 = __t->__next_;
  1480. __t->__next_ = nullptr;
  1481. return __merge(__sort(__f1, __sz1, __comp),
  1482. __sort(__f2, __sz2, __comp), __comp);
  1483. }
  1484. template <class _Tp, class _Alloc>
  1485. void
  1486. forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT
  1487. {
  1488. __node_pointer __p = base::__before_begin()->__next_;
  1489. if (__p != nullptr)
  1490. {
  1491. __node_pointer __f = __p->__next_;
  1492. __p->__next_ = nullptr;
  1493. while (__f != nullptr)
  1494. {
  1495. __node_pointer __t = __f->__next_;
  1496. __f->__next_ = __p;
  1497. __p = __f;
  1498. __f = __t;
  1499. }
  1500. base::__before_begin()->__next_ = __p;
  1501. }
  1502. }
  1503. template <class _Tp, class _Alloc>
  1504. bool operator==(const forward_list<_Tp, _Alloc>& __x,
  1505. const forward_list<_Tp, _Alloc>& __y)
  1506. {
  1507. typedef forward_list<_Tp, _Alloc> _Cp;
  1508. typedef typename _Cp::const_iterator _Ip;
  1509. _Ip __ix = __x.begin();
  1510. _Ip __ex = __x.end();
  1511. _Ip __iy = __y.begin();
  1512. _Ip __ey = __y.end();
  1513. for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)
  1514. if (!(*__ix == *__iy))
  1515. return false;
  1516. return (__ix == __ex) == (__iy == __ey);
  1517. }
  1518. template <class _Tp, class _Alloc>
  1519. inline _LIBCPP_INLINE_VISIBILITY
  1520. bool operator!=(const forward_list<_Tp, _Alloc>& __x,
  1521. const forward_list<_Tp, _Alloc>& __y)
  1522. {
  1523. return !(__x == __y);
  1524. }
  1525. template <class _Tp, class _Alloc>
  1526. inline _LIBCPP_INLINE_VISIBILITY
  1527. bool operator< (const forward_list<_Tp, _Alloc>& __x,
  1528. const forward_list<_Tp, _Alloc>& __y)
  1529. {
  1530. return _VSTD::lexicographical_compare(__x.begin(), __x.end(),
  1531. __y.begin(), __y.end());
  1532. }
  1533. template <class _Tp, class _Alloc>
  1534. inline _LIBCPP_INLINE_VISIBILITY
  1535. bool operator> (const forward_list<_Tp, _Alloc>& __x,
  1536. const forward_list<_Tp, _Alloc>& __y)
  1537. {
  1538. return __y < __x;
  1539. }
  1540. template <class _Tp, class _Alloc>
  1541. inline _LIBCPP_INLINE_VISIBILITY
  1542. bool operator>=(const forward_list<_Tp, _Alloc>& __x,
  1543. const forward_list<_Tp, _Alloc>& __y)
  1544. {
  1545. return !(__x < __y);
  1546. }
  1547. template <class _Tp, class _Alloc>
  1548. inline _LIBCPP_INLINE_VISIBILITY
  1549. bool operator<=(const forward_list<_Tp, _Alloc>& __x,
  1550. const forward_list<_Tp, _Alloc>& __y)
  1551. {
  1552. return !(__y < __x);
  1553. }
  1554. template <class _Tp, class _Alloc>
  1555. inline _LIBCPP_INLINE_VISIBILITY
  1556. void
  1557. swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y)
  1558. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  1559. {
  1560. __x.swap(__y);
  1561. }
  1562. #if _LIBCPP_STD_VER > 17
  1563. template <class _Tp, class _Allocator, class _Predicate>
  1564. inline _LIBCPP_INLINE_VISIBILITY
  1565. typename forward_list<_Tp, _Allocator>::size_type
  1566. erase_if(forward_list<_Tp, _Allocator>& __c, _Predicate __pred) {
  1567. return __c.remove_if(__pred);
  1568. }
  1569. template <class _Tp, class _Allocator, class _Up>
  1570. inline _LIBCPP_INLINE_VISIBILITY
  1571. typename forward_list<_Tp, _Allocator>::size_type
  1572. erase(forward_list<_Tp, _Allocator>& __c, const _Up& __v) {
  1573. return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
  1574. }
  1575. #endif
  1576. _LIBCPP_END_NAMESPACE_STD
  1577. _LIBCPP_POP_MACROS
  1578. #endif // _LIBCPP_FORWARD_LIST