1246 lines · plain
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03_FORWARD_LIST11#define _LIBCPP___CXX03_FORWARD_LIST12 13/*14 forward_list synopsis15 16namespace std17{18 19template <class T, class Allocator = allocator<T>>20class forward_list21{22public:23 typedef T value_type;24 typedef Allocator allocator_type;25 26 typedef value_type& reference;27 typedef const value_type& const_reference;28 typedef typename allocator_traits<allocator_type>::pointer pointer;29 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;30 typedef typename allocator_traits<allocator_type>::size_type size_type;31 typedef typename allocator_traits<allocator_type>::difference_type difference_type;32 33 typedef <details> iterator;34 typedef <details> const_iterator;35 36 forward_list()37 noexcept(is_nothrow_default_constructible<allocator_type>::value);38 explicit forward_list(const allocator_type& a);39 explicit forward_list(size_type n);40 explicit forward_list(size_type n, const allocator_type& a); // C++1441 forward_list(size_type n, const value_type& v);42 forward_list(size_type n, const value_type& v, const allocator_type& a);43 template <class InputIterator>44 forward_list(InputIterator first, InputIterator last);45 template <class InputIterator>46 forward_list(InputIterator first, InputIterator last, const allocator_type& a);47 template<container-compatible-range<T> R>48 forward_list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++2349 forward_list(const forward_list& x);50 forward_list(const forward_list& x, const allocator_type& a);51 forward_list(forward_list&& x)52 noexcept(is_nothrow_move_constructible<allocator_type>::value);53 forward_list(forward_list&& x, const allocator_type& a);54 forward_list(initializer_list<value_type> il);55 forward_list(initializer_list<value_type> il, const allocator_type& a);56 57 ~forward_list();58 59 forward_list& operator=(const forward_list& x);60 forward_list& operator=(forward_list&& x)61 noexcept(62 allocator_type::propagate_on_container_move_assignment::value &&63 is_nothrow_move_assignable<allocator_type>::value);64 forward_list& operator=(initializer_list<value_type> il);65 66 template <class InputIterator>67 void assign(InputIterator first, InputIterator last);68 template<container-compatible-range<T> R>69 void assign_range(R&& rg); // C++2370 void assign(size_type n, const value_type& v);71 void assign(initializer_list<value_type> il);72 73 allocator_type get_allocator() const noexcept;74 75 iterator begin() noexcept;76 const_iterator begin() const noexcept;77 iterator end() noexcept;78 const_iterator end() const noexcept;79 80 const_iterator cbegin() const noexcept;81 const_iterator cend() const noexcept;82 83 iterator before_begin() noexcept;84 const_iterator before_begin() const noexcept;85 const_iterator cbefore_begin() const noexcept;86 87 bool empty() const noexcept;88 size_type max_size() const noexcept;89 90 reference front();91 const_reference front() const;92 93 template <class... Args> reference emplace_front(Args&&... args); // reference in C++1794 void push_front(const value_type& v);95 void push_front(value_type&& v);96 template<container-compatible-range<T> R>97 void prepend_range(R&& rg); // C++2398 99 void pop_front();100 101 template <class... Args>102 iterator emplace_after(const_iterator p, Args&&... args);103 iterator insert_after(const_iterator p, const value_type& v);104 iterator insert_after(const_iterator p, value_type&& v);105 iterator insert_after(const_iterator p, size_type n, const value_type& v);106 template <class InputIterator>107 iterator insert_after(const_iterator p,108 InputIterator first, InputIterator last);109 template<container-compatible-range<T> R>110 iterator insert_range_after(const_iterator position, R&& rg); // C++23111 iterator insert_after(const_iterator p, initializer_list<value_type> il);112 113 iterator erase_after(const_iterator p);114 iterator erase_after(const_iterator first, const_iterator last);115 116 void swap(forward_list& x)117 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17118 119 void resize(size_type n);120 void resize(size_type n, const value_type& v);121 void clear() noexcept;122 123 void splice_after(const_iterator p, forward_list& x);124 void splice_after(const_iterator p, forward_list&& x);125 void splice_after(const_iterator p, forward_list& x, const_iterator i);126 void splice_after(const_iterator p, forward_list&& x, const_iterator i);127 void splice_after(const_iterator p, forward_list& x,128 const_iterator first, const_iterator last);129 void splice_after(const_iterator p, forward_list&& x,130 const_iterator first, const_iterator last);131 size_type remove(const value_type& v); // void before C++20132 template <class Predicate>133 size_type remove_if(Predicate pred); // void before C++20134 size_type unique(); // void before C++20135 template <class BinaryPredicate>136 size_type unique(BinaryPredicate binary_pred); // void before C++20137 void merge(forward_list& x);138 void merge(forward_list&& x);139 template <class Compare> void merge(forward_list& x, Compare comp);140 template <class Compare> void merge(forward_list&& x, Compare comp);141 void sort();142 template <class Compare> void sort(Compare comp);143 void reverse() noexcept;144};145 146 147template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>148 forward_list(InputIterator, InputIterator, Allocator = Allocator())149 -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17150 151template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>152 forward_list(from_range_t, R&&, Allocator = Allocator())153 -> forward_list<ranges::range_value_t<R>, Allocator>; // C++23154 155template <class T, class Allocator>156 bool operator==(const forward_list<T, Allocator>& x,157 const forward_list<T, Allocator>& y);158 159template <class T, class Allocator>160 bool operator< (const forward_list<T, Allocator>& x,161 const forward_list<T, Allocator>& y); // removed in C++20162 163template <class T, class Allocator>164 bool operator!=(const forward_list<T, Allocator>& x,165 const forward_list<T, Allocator>& y); // removed in C++20166 167template <class T, class Allocator>168 bool operator> (const forward_list<T, Allocator>& x,169 const forward_list<T, Allocator>& y); // removed in C++20170 171template <class T, class Allocator>172 bool operator>=(const forward_list<T, Allocator>& x,173 const forward_list<T, Allocator>& y); // removed in C++20174 175template <class T, class Allocator>176 bool operator<=(const forward_list<T, Allocator>& x,177 const forward_list<T, Allocator>& y); // removed in C++20178 179template<class T, class Allocator>180 synth-three-way-result<T> operator<=>(const forward_list<T, Allocator>& x,181 const forward_list<T, Allocator>& y); // since C++20182 183template <class T, class Allocator>184 void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)185 noexcept(noexcept(x.swap(y)));186 187template <class T, class Allocator, class U>188 typename forward_list<T, Allocator>::size_type189 erase(forward_list<T, Allocator>& c, const U& value); // C++20190template <class T, class Allocator, class Predicate>191 typename forward_list<T, Allocator>::size_type192 erase_if(forward_list<T, Allocator>& c, Predicate pred); // C++20193 194} // std195 196*/197 198#include <__cxx03/__algorithm/comp.h>199#include <__cxx03/__algorithm/lexicographical_compare.h>200#include <__cxx03/__algorithm/min.h>201#include <__cxx03/__config>202#include <__cxx03/__iterator/distance.h>203#include <__cxx03/__iterator/iterator_traits.h>204#include <__cxx03/__iterator/move_iterator.h>205#include <__cxx03/__iterator/next.h>206#include <__cxx03/__memory/addressof.h>207#include <__cxx03/__memory/allocation_guard.h>208#include <__cxx03/__memory/allocator.h>209#include <__cxx03/__memory/allocator_traits.h>210#include <__cxx03/__memory/compressed_pair.h>211#include <__cxx03/__memory/construct_at.h>212#include <__cxx03/__memory/pointer_traits.h>213#include <__cxx03/__memory/swap_allocator.h>214#include <__cxx03/__type_traits/conditional.h>215#include <__cxx03/__type_traits/is_allocator.h>216#include <__cxx03/__type_traits/is_const.h>217#include <__cxx03/__type_traits/is_nothrow_assignable.h>218#include <__cxx03/__type_traits/is_nothrow_constructible.h>219#include <__cxx03/__type_traits/is_pointer.h>220#include <__cxx03/__type_traits/is_same.h>221#include <__cxx03/__type_traits/is_swappable.h>222#include <__cxx03/__type_traits/type_identity.h>223#include <__cxx03/__utility/forward.h>224#include <__cxx03/__utility/move.h>225#include <__cxx03/limits>226#include <__cxx03/new> // __launder227#include <__cxx03/version>228 229// standard-mandated includes230 231// [iterator.range]232#include <__cxx03/__iterator/access.h>233 234#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)235# pragma GCC system_header236#endif237 238_LIBCPP_PUSH_MACROS239#include <__cxx03/__undef_macros>240 241_LIBCPP_BEGIN_NAMESPACE_STD242 243template <class _Tp, class _VoidPtr>244struct __forward_list_node;245template <class _NodePtr>246struct __forward_begin_node;247 248template <class>249struct __forward_list_node_value_type;250 251template <class _Tp, class _VoidPtr>252struct __forward_list_node_value_type<__forward_list_node<_Tp, _VoidPtr> > {253 typedef _Tp type;254};255 256template <class _NodePtr>257struct __forward_node_traits {258 typedef __remove_cv_t<typename pointer_traits<_NodePtr>::element_type> __node_type;259 typedef typename __forward_list_node_value_type<__node_type>::type __node_value_type;260 typedef _NodePtr __node_pointer;261 typedef __forward_begin_node<_NodePtr> __begin_node;262 typedef __rebind_pointer_t<_NodePtr, __begin_node> __begin_node_pointer;263 typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;264 265#if defined(_LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB)266 typedef __begin_node_pointer __iter_node_pointer;267#else268 typedef __conditional_t<is_pointer<__void_pointer>::value, __begin_node_pointer, __node_pointer> __iter_node_pointer;269#endif270 271 typedef __conditional_t<is_same<__iter_node_pointer, __node_pointer>::value, __begin_node_pointer, __node_pointer>272 __non_iter_node_pointer;273 274 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__iter_node_pointer __p) { return __p; }275 _LIBCPP_HIDE_FROM_ABI static __iter_node_pointer __as_iter_node(__non_iter_node_pointer __p) {276 return static_cast<__iter_node_pointer>(static_cast<__void_pointer>(__p));277 }278};279 280template <class _NodePtr>281struct __forward_begin_node {282 typedef _NodePtr pointer;283 typedef __rebind_pointer_t<_NodePtr, __forward_begin_node> __begin_node_pointer;284 285 pointer __next_;286 287 _LIBCPP_HIDE_FROM_ABI __forward_begin_node() : __next_(nullptr) {}288 _LIBCPP_HIDE_FROM_ABI explicit __forward_begin_node(pointer __n) : __next_(__n) {}289 290 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __next_as_begin() const {291 return static_cast<__begin_node_pointer>(__next_);292 }293};294 295template <class _Tp, class _VoidPtr>296using __begin_node_of = __forward_begin_node<__rebind_pointer_t<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> > >;297 298template <class _Tp, class _VoidPtr>299struct __forward_list_node : public __begin_node_of<_Tp, _VoidPtr> {300 typedef _Tp value_type;301 typedef __begin_node_of<_Tp, _VoidPtr> _Base;302 typedef typename _Base::pointer _NodePtr;303 304 // We allow starting the lifetime of nodes without initializing the value held by the node,305 // since that is handled by the list itself in order to be allocator-aware.306 307private:308 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];309 310public:311 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }312 313 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_node(_NodePtr __next) : _Base(__next) {}314 _LIBCPP_HIDE_FROM_ABI ~__forward_list_node() {}315};316 317template <class _Tp, class _Alloc = allocator<_Tp> >318class _LIBCPP_TEMPLATE_VIS forward_list;319template <class _NodeConstPtr>320class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;321 322template <class _NodePtr>323class _LIBCPP_TEMPLATE_VIS __forward_list_iterator {324 typedef __forward_node_traits<_NodePtr> __traits;325 typedef typename __traits::__node_pointer __node_pointer;326 typedef typename __traits::__begin_node_pointer __begin_node_pointer;327 typedef typename __traits::__iter_node_pointer __iter_node_pointer;328 typedef typename __traits::__void_pointer __void_pointer;329 330 __iter_node_pointer __ptr_;331 332 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {333 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));334 }335 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {336 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));337 }338 339 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}340 341 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__begin_node_pointer __p) _NOEXCEPT342 : __ptr_(__traits::__as_iter_node(__p)) {}343 344 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_iterator(__node_pointer __p) _NOEXCEPT345 : __ptr_(__traits::__as_iter_node(__p)) {}346 347 template <class, class>348 friend class _LIBCPP_TEMPLATE_VIS forward_list;349 template <class>350 friend class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator;351 352public:353 typedef forward_iterator_tag iterator_category;354 typedef typename __traits::__node_value_type value_type;355 typedef value_type& reference;356 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;357 typedef __rebind_pointer_t<__node_pointer, value_type> pointer;358 359 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}360 361 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }362 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {363 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());364 }365 366 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator& operator++() {367 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);368 return *this;369 }370 _LIBCPP_HIDE_FROM_ABI __forward_list_iterator operator++(int) {371 __forward_list_iterator __t(*this);372 ++(*this);373 return __t;374 }375 376 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {377 return __x.__ptr_ == __y.__ptr_;378 }379 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __forward_list_iterator& __x, const __forward_list_iterator& __y) {380 return !(__x == __y);381 }382};383 384template <class _NodeConstPtr>385class _LIBCPP_TEMPLATE_VIS __forward_list_const_iterator {386 static_assert(!is_const<typename pointer_traits<_NodeConstPtr>::element_type>::value, "");387 typedef _NodeConstPtr _NodePtr;388 389 typedef __forward_node_traits<_NodePtr> __traits;390 typedef typename __traits::__node_type __node_type;391 typedef typename __traits::__node_pointer __node_pointer;392 typedef typename __traits::__begin_node_pointer __begin_node_pointer;393 typedef typename __traits::__iter_node_pointer __iter_node_pointer;394 typedef typename __traits::__void_pointer __void_pointer;395 396 __iter_node_pointer __ptr_;397 398 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __get_begin() const {399 return static_cast<__begin_node_pointer>(static_cast<__void_pointer>(__ptr_));400 }401 _LIBCPP_HIDE_FROM_ABI __node_pointer __get_unsafe_node_pointer() const {402 return static_cast<__node_pointer>(static_cast<__void_pointer>(__ptr_));403 }404 405 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(nullptr_t) _NOEXCEPT : __ptr_(nullptr) {}406 407 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__begin_node_pointer __p) _NOEXCEPT408 : __ptr_(__traits::__as_iter_node(__p)) {}409 410 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_const_iterator(__node_pointer __p) _NOEXCEPT411 : __ptr_(__traits::__as_iter_node(__p)) {}412 413 template <class, class>414 friend class forward_list;415 416public:417 typedef forward_iterator_tag iterator_category;418 typedef typename __traits::__node_value_type value_type;419 typedef const value_type& reference;420 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;421 typedef __rebind_pointer_t<__node_pointer, const value_type> pointer;422 423 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}424 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator(__forward_list_iterator<__node_pointer> __p) _NOEXCEPT425 : __ptr_(__p.__ptr_) {}426 427 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_unsafe_node_pointer()->__get_value(); }428 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {429 return pointer_traits<pointer>::pointer_to(__get_unsafe_node_pointer()->__get_value());430 }431 432 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator& operator++() {433 __ptr_ = __traits::__as_iter_node(__ptr_->__next_);434 return *this;435 }436 _LIBCPP_HIDE_FROM_ABI __forward_list_const_iterator operator++(int) {437 __forward_list_const_iterator __t(*this);438 ++(*this);439 return __t;440 }441 442 friend _LIBCPP_HIDE_FROM_ABI bool443 operator==(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {444 return __x.__ptr_ == __y.__ptr_;445 }446 friend _LIBCPP_HIDE_FROM_ABI bool447 operator!=(const __forward_list_const_iterator& __x, const __forward_list_const_iterator& __y) {448 return !(__x == __y);449 }450};451 452template <class _Tp, class _Alloc>453class __forward_list_base {454protected:455 typedef _Tp value_type;456 typedef _Alloc allocator_type;457 458 typedef typename allocator_traits<allocator_type>::void_pointer void_pointer;459 typedef __forward_list_node<value_type, void_pointer> __node_type;460 typedef __begin_node_of<value_type, void_pointer> __begin_node;461 typedef __rebind_alloc<allocator_traits<allocator_type>, __node_type> __node_allocator;462 typedef allocator_traits<__node_allocator> __node_traits;463 typedef typename __node_traits::pointer __node_pointer;464 465 typedef __rebind_alloc<allocator_traits<allocator_type>, __begin_node> __begin_node_allocator;466 typedef typename allocator_traits<__begin_node_allocator>::pointer __begin_node_pointer;467 468 __compressed_pair<__begin_node, __node_allocator> __before_begin_;469 470 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() _NOEXCEPT {471 return pointer_traits<__begin_node_pointer>::pointer_to(__before_begin_.first());472 }473 _LIBCPP_HIDE_FROM_ABI __begin_node_pointer __before_begin() const _NOEXCEPT {474 return pointer_traits<__begin_node_pointer>::pointer_to(const_cast<__begin_node&>(__before_begin_.first()));475 }476 477 _LIBCPP_HIDE_FROM_ABI __node_allocator& __alloc() _NOEXCEPT { return __before_begin_.second(); }478 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __alloc() const _NOEXCEPT { return __before_begin_.second(); }479 480 typedef __forward_list_iterator<__node_pointer> iterator;481 typedef __forward_list_const_iterator<__node_pointer> const_iterator;482 483 _LIBCPP_HIDE_FROM_ABI __forward_list_base() : __before_begin_(__begin_node(), __default_init_tag()) {}484 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const allocator_type& __a)485 : __before_begin_(__begin_node(), __node_allocator(__a)) {}486 _LIBCPP_HIDE_FROM_ABI explicit __forward_list_base(const __node_allocator& __a)487 : __before_begin_(__begin_node(), __a) {}488 489public:490 __forward_list_base(const __forward_list_base&) = delete;491 __forward_list_base& operator=(const __forward_list_base&) = delete;492 493 _LIBCPP_HIDE_FROM_ABI ~__forward_list_base();494 495protected:496 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x) {497 __copy_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());498 }499 500 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x) {501 __move_assign_alloc(__x, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());502 }503 504 template <class... _Args>505 _LIBCPP_HIDE_FROM_ABI __node_pointer __create_node(__node_pointer __next, _Args&&... __args) {506 __node_allocator& __a = __alloc();507 __allocation_guard<__node_allocator> __guard(__a, 1);508 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value509 // held inside the node, since we need to use the allocator's construct() method for that.510 //511 // We don't use the allocator's construct() method to construct the node itself since the512 // Cpp17FooInsertable named requirements don't require the allocator's construct() method513 // to work on anything other than the value_type.514 std::__construct_at(std::addressof(*__guard.__get()), __next);515 516 // Now construct the value_type using the allocator's construct() method.517 __node_traits::construct(__a, std::addressof(__guard.__get()->__get_value()), std::forward<_Args>(__args)...);518 return __guard.__release_ptr();519 }520 521 _LIBCPP_HIDE_FROM_ABI void __delete_node(__node_pointer __node) {522 // For the same reason as above, we use the allocator's destroy() method for the value_type,523 // but not for the node itself.524 __node_allocator& __a = __alloc();525 __node_traits::destroy(__a, std::addressof(__node->__get_value()));526 std::__destroy_at(std::addressof(*__node));527 __node_traits::deallocate(__a, __node, 1);528 }529 530public:531 _LIBCPP_HIDE_FROM_ABI void swap(__forward_list_base& __x);532 533protected:534 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;535 536private:537 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base&, false_type) {}538 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __forward_list_base& __x, true_type) {539 if (__alloc() != __x.__alloc())540 clear();541 __alloc() = __x.__alloc();542 }543 544 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base&, false_type) _NOEXCEPT {}545 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__forward_list_base& __x, true_type) {546 __alloc() = std::move(__x.__alloc());547 }548};549 550template <class _Tp, class _Alloc>551__forward_list_base<_Tp, _Alloc>::~__forward_list_base() {552 clear();553}554 555template <class _Tp, class _Alloc>556inline void __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x) {557 std::__swap_allocator(558 __alloc(), __x.__alloc(), integral_constant<bool, __node_traits::propagate_on_container_swap::value>());559 using std::swap;560 swap(__before_begin()->__next_, __x.__before_begin()->__next_);561}562 563template <class _Tp, class _Alloc>564void __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT {565 for (__node_pointer __p = __before_begin()->__next_; __p != nullptr;) {566 __node_pointer __next = __p->__next_;567 __delete_node(__p);568 __p = __next;569 }570 __before_begin()->__next_ = nullptr;571}572 573template <class _Tp, class _Alloc /*= allocator<_Tp>*/>574class _LIBCPP_TEMPLATE_VIS forward_list : private __forward_list_base<_Tp, _Alloc> {575 typedef __forward_list_base<_Tp, _Alloc> __base;576 typedef typename __base::__node_allocator __node_allocator;577 typedef typename __base::__node_type __node_type;578 typedef typename __base::__node_traits __node_traits;579 typedef typename __base::__node_pointer __node_pointer;580 typedef typename __base::__begin_node_pointer __begin_node_pointer;581 582public:583 typedef _Tp value_type;584 typedef _Alloc allocator_type;585 586 static_assert(__check_valid_allocator<allocator_type>::value, "");587 588 static_assert(is_same<value_type, typename allocator_type::value_type>::value,589 "Allocator::value_type must be same type as value_type");590 591 static_assert(!is_same<allocator_type, __node_allocator>::value,592 "internal allocator type must differ from user-specified type; otherwise overload resolution breaks");593 594 typedef value_type& reference;595 typedef const value_type& const_reference;596 typedef typename allocator_traits<allocator_type>::pointer pointer;597 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;598 typedef typename allocator_traits<allocator_type>::size_type size_type;599 typedef typename allocator_traits<allocator_type>::difference_type difference_type;600 601 typedef typename __base::iterator iterator;602 typedef typename __base::const_iterator const_iterator;603 typedef void __remove_return_type;604 605 _LIBCPP_HIDE_FROM_ABI forward_list() {} // = default;606 _LIBCPP_HIDE_FROM_ABI explicit forward_list(const allocator_type& __a);607 _LIBCPP_HIDE_FROM_ABI explicit forward_list(size_type __n);608 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v);609 610 template <__enable_if_t<__is_allocator<_Alloc>::value, int> = 0>611 _LIBCPP_HIDE_FROM_ABI forward_list(size_type __n, const value_type& __v, const allocator_type& __a) : __base(__a) {612 insert_after(cbefore_begin(), __n, __v);613 }614 615 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>616 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l);617 618 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>619 _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a);620 621 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x);622 _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a);623 624 _LIBCPP_HIDE_FROM_ABI forward_list& operator=(const forward_list& __x);625 626 // ~forward_list() = default;627 628 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>629 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __f, _InputIterator __l);630 631 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v);632 633 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__base::__alloc()); }634 635 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return iterator(__base::__before_begin()->__next_); }636 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT {637 return const_iterator(__base::__before_begin()->__next_);638 }639 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return iterator(nullptr); }640 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return const_iterator(nullptr); }641 642 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT {643 return const_iterator(__base::__before_begin()->__next_);644 }645 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return const_iterator(nullptr); }646 647 _LIBCPP_HIDE_FROM_ABI iterator before_begin() _NOEXCEPT { return iterator(__base::__before_begin()); }648 _LIBCPP_HIDE_FROM_ABI const_iterator before_begin() const _NOEXCEPT {649 return const_iterator(__base::__before_begin());650 }651 _LIBCPP_HIDE_FROM_ABI const_iterator cbefore_begin() const _NOEXCEPT {652 return const_iterator(__base::__before_begin());653 }654 655 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {656 return __base::__before_begin()->__next_ == nullptr;657 }658 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {659 return std::min<size_type>(__node_traits::max_size(__base::__alloc()), numeric_limits<difference_type>::max());660 }661 662 _LIBCPP_HIDE_FROM_ABI reference front() { return __base::__before_begin()->__next_->__get_value(); }663 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return __base::__before_begin()->__next_->__get_value(); }664 665 _LIBCPP_HIDE_FROM_ABI void push_front(const value_type& __v);666 667 _LIBCPP_HIDE_FROM_ABI void pop_front();668 669 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, const value_type& __v);670 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, size_type __n, const value_type& __v);671 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>672 _LIBCPP_HIDE_FROM_ABI iterator insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l);673 674 template <class _InputIterator, class _Sentinel>675 _LIBCPP_HIDE_FROM_ABI iterator __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l);676 677 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p);678 _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l);679 680 _LIBCPP_HIDE_FROM_ABI void swap(forward_list& __x) { __base::swap(__x); }681 682 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n);683 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n, const value_type& __v);684 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __base::clear(); }685 686 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x);687 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list&& __x, const_iterator __i);688 _LIBCPP_HIDE_FROM_ABI void689 splice_after(const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l);690 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x);691 _LIBCPP_HIDE_FROM_ABI void splice_after(const_iterator __p, forward_list& __x, const_iterator __i);692 _LIBCPP_HIDE_FROM_ABI void693 splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l);694 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove(const value_type& __v);695 template <class _Predicate>696 _LIBCPP_HIDE_FROM_ABI __remove_return_type remove_if(_Predicate __pred);697 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique() { return unique(__equal_to()); }698 template <class _BinaryPredicate>699 _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred);700 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x) { merge(__x, __less<>()); }701 template <class _Compare>702 _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp);703 _LIBCPP_HIDE_FROM_ABI void sort() { sort(__less<>()); }704 template <class _Compare>705 _LIBCPP_HIDE_FROM_ABI void sort(_Compare __comp);706 _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT;707 708private:709 template <class _Iter, class _Sent>710 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iter __f, _Sent __l);711 712 template <class _Compare>713 static _LIBCPP_HIDE_FROM_ABI __node_pointer __merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp);714 715 // TODO: Make this _LIBCPP_HIDE_FROM_ABI716 template <class _Compare>717 static _LIBCPP_HIDDEN __node_pointer __sort(__node_pointer __f, difference_type __sz, _Compare& __comp);718};719 720template <class _Tp, class _Alloc>721inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) : __base(__a) {}722 723template <class _Tp, class _Alloc>724forward_list<_Tp, _Alloc>::forward_list(size_type __n) {725 if (__n > 0) {726 for (__begin_node_pointer __p = __base::__before_begin(); __n > 0; --__n, __p = __p->__next_as_begin()) {727 __p->__next_ = this->__create_node(/* next = */ nullptr);728 }729 }730}731 732template <class _Tp, class _Alloc>733forward_list<_Tp, _Alloc>::forward_list(size_type __n, const value_type& __v) {734 insert_after(cbefore_begin(), __n, __v);735}736 737template <class _Tp, class _Alloc>738template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >739forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l) {740 insert_after(cbefore_begin(), __f, __l);741}742 743template <class _Tp, class _Alloc>744template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >745forward_list<_Tp, _Alloc>::forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a)746 : __base(__a) {747 insert_after(cbefore_begin(), __f, __l);748}749 750template <class _Tp, class _Alloc>751forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)752 : __base(__node_traits::select_on_container_copy_construction(__x.__alloc())) {753 insert_after(cbefore_begin(), __x.begin(), __x.end());754}755 756template <class _Tp, class _Alloc>757forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x, const __type_identity_t<allocator_type>& __a)758 : __base(__a) {759 insert_after(cbefore_begin(), __x.begin(), __x.end());760}761 762template <class _Tp, class _Alloc>763forward_list<_Tp, _Alloc>& forward_list<_Tp, _Alloc>::operator=(const forward_list& __x) {764 if (this != std::addressof(__x)) {765 __base::__copy_assign_alloc(__x);766 assign(__x.begin(), __x.end());767 }768 return *this;769}770 771template <class _Tp, class _Alloc>772template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >773void forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) {774 __assign_with_sentinel(__f, __l);775}776 777template <class _Tp, class _Alloc>778template <class _Iter, class _Sent>779_LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __l) {780 iterator __i = before_begin();781 iterator __j = std::next(__i);782 iterator __e = end();783 for (; __j != __e && __f != __l; ++__i, (void)++__j, ++__f)784 *__j = *__f;785 if (__j == __e)786 __insert_after_with_sentinel(__i, std::move(__f), std::move(__l));787 else788 erase_after(__i, __e);789}790 791template <class _Tp, class _Alloc>792void forward_list<_Tp, _Alloc>::assign(size_type __n, const value_type& __v) {793 iterator __i = before_begin();794 iterator __j = std::next(__i);795 iterator __e = end();796 for (; __j != __e && __n > 0; --__n, ++__i, ++__j)797 *__j = __v;798 if (__j == __e)799 insert_after(__i, __n, __v);800 else801 erase_after(__i, __e);802}803 804template <class _Tp, class _Alloc>805void forward_list<_Tp, _Alloc>::push_front(const value_type& __v) {806 __base::__before_begin()->__next_ = this->__create_node(/* next = */ __base::__before_begin()->__next_, __v);807}808 809template <class _Tp, class _Alloc>810void forward_list<_Tp, _Alloc>::pop_front() {811 __node_pointer __p = __base::__before_begin()->__next_;812 __base::__before_begin()->__next_ = __p->__next_;813 this->__delete_node(__p);814}815 816template <class _Tp, class _Alloc>817typename forward_list<_Tp, _Alloc>::iterator818forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, const value_type& __v) {819 __begin_node_pointer const __r = __p.__get_begin();820 __r->__next_ = this->__create_node(/* next = */ __r->__next_, __v);821 return iterator(__r->__next_);822}823 824template <class _Tp, class _Alloc>825typename forward_list<_Tp, _Alloc>::iterator826forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, size_type __n, const value_type& __v) {827 __begin_node_pointer __r = __p.__get_begin();828 if (__n > 0) {829 __node_pointer __first = this->__create_node(/* next = */ nullptr, __v);830 __node_pointer __last = __first;831#ifndef _LIBCPP_HAS_NO_EXCEPTIONS832 try {833#endif // _LIBCPP_HAS_NO_EXCEPTIONS834 for (--__n; __n != 0; --__n, __last = __last->__next_) {835 __last->__next_ = this->__create_node(/* next = */ nullptr, __v);836 }837#ifndef _LIBCPP_HAS_NO_EXCEPTIONS838 } catch (...) {839 while (__first != nullptr) {840 __node_pointer __next = __first->__next_;841 this->__delete_node(__first);842 __first = __next;843 }844 throw;845 }846#endif // _LIBCPP_HAS_NO_EXCEPTIONS847 __last->__next_ = __r->__next_;848 __r->__next_ = __first;849 __r = static_cast<__begin_node_pointer>(__last);850 }851 return iterator(__r);852}853 854template <class _Tp, class _Alloc>855template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> >856typename forward_list<_Tp, _Alloc>::iterator857forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) {858 return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l));859}860 861template <class _Tp, class _Alloc>862template <class _InputIterator, class _Sentinel>863_LIBCPP_HIDE_FROM_ABI typename forward_list<_Tp, _Alloc>::iterator864forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) {865 __begin_node_pointer __r = __p.__get_begin();866 867 if (__f != __l) {868 __node_pointer __first = this->__create_node(/* next = */ nullptr, *__f);869 __node_pointer __last = __first;870 871#ifndef _LIBCPP_HAS_NO_EXCEPTIONS872 try {873#endif // _LIBCPP_HAS_NO_EXCEPTIONS874 for (++__f; __f != __l; ++__f, ((void)(__last = __last->__next_))) {875 __last->__next_ = this->__create_node(/* next = */ nullptr, *__f);876 }877#ifndef _LIBCPP_HAS_NO_EXCEPTIONS878 } catch (...) {879 while (__first != nullptr) {880 __node_pointer __next = __first->__next_;881 this->__delete_node(__first);882 __first = __next;883 }884 throw;885 }886#endif // _LIBCPP_HAS_NO_EXCEPTIONS887 888 __last->__next_ = __r->__next_;889 __r->__next_ = __first;890 __r = static_cast<__begin_node_pointer>(__last);891 }892 893 return iterator(__r);894}895 896template <class _Tp, class _Alloc>897typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>::erase_after(const_iterator __f) {898 __begin_node_pointer __p = __f.__get_begin();899 __node_pointer __n = __p->__next_;900 __p->__next_ = __n->__next_;901 this->__delete_node(__n);902 return iterator(__p->__next_);903}904 905template <class _Tp, class _Alloc>906typename forward_list<_Tp, _Alloc>::iterator907forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l) {908 __node_pointer __e = __l.__get_unsafe_node_pointer();909 if (__f != __l) {910 __begin_node_pointer __bp = __f.__get_begin();911 912 __node_pointer __n = __bp->__next_;913 if (__n != __e) {914 __bp->__next_ = __e;915 do {916 __node_pointer __tmp = __n->__next_;917 this->__delete_node(__n);918 __n = __tmp;919 } while (__n != __e);920 }921 }922 return iterator(__e);923}924 925template <class _Tp, class _Alloc>926void forward_list<_Tp, _Alloc>::resize(size_type __n) {927 size_type __sz = 0;928 iterator __p = before_begin();929 iterator __i = begin();930 iterator __e = end();931 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)932 ;933 if (__i != __e)934 erase_after(__p, __e);935 else {936 __n -= __sz;937 if (__n > 0) {938 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {939 __ptr->__next_ = this->__create_node(/* next = */ nullptr);940 }941 }942 }943}944 945template <class _Tp, class _Alloc>946void forward_list<_Tp, _Alloc>::resize(size_type __n, const value_type& __v) {947 size_type __sz = 0;948 iterator __p = before_begin();949 iterator __i = begin();950 iterator __e = end();951 for (; __i != __e && __sz < __n; ++__p, ++__i, ++__sz)952 ;953 if (__i != __e)954 erase_after(__p, __e);955 else {956 __n -= __sz;957 if (__n > 0) {958 for (__begin_node_pointer __ptr = __p.__get_begin(); __n > 0; --__n, __ptr = __ptr->__next_as_begin()) {959 __ptr->__next_ = this->__create_node(/* next = */ nullptr, __v);960 }961 }962 }963}964 965template <class _Tp, class _Alloc>966void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& __x) {967 if (!__x.empty()) {968 if (__p.__get_begin()->__next_ != nullptr) {969 const_iterator __lm1 = __x.before_begin();970 while (__lm1.__get_begin()->__next_ != nullptr)971 ++__lm1;972 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;973 }974 __p.__get_begin()->__next_ = __x.__before_begin()->__next_;975 __x.__before_begin()->__next_ = nullptr;976 }977}978 979template <class _Tp, class _Alloc>980void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list& /*__other*/, const_iterator __i) {981 const_iterator __lm1 = std::next(__i);982 if (__p != __i && __p != __lm1) {983 __i.__get_begin()->__next_ = __lm1.__get_begin()->__next_;984 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;985 __p.__get_begin()->__next_ = __lm1.__get_unsafe_node_pointer();986 }987}988 989template <class _Tp, class _Alloc>990void forward_list<_Tp, _Alloc>::splice_after(991 const_iterator __p, forward_list& /*__other*/, const_iterator __f, const_iterator __l) {992 if (__f != __l && __p != __f) {993 const_iterator __lm1 = __f;994 while (__lm1.__get_begin()->__next_ != __l.__get_begin())995 ++__lm1;996 if (__f != __lm1) {997 __lm1.__get_begin()->__next_ = __p.__get_begin()->__next_;998 __p.__get_begin()->__next_ = __f.__get_begin()->__next_;999 __f.__get_begin()->__next_ = __l.__get_unsafe_node_pointer();1000 }1001 }1002}1003 1004template <class _Tp, class _Alloc>1005inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x) {1006 splice_after(__p, __x);1007}1008 1009template <class _Tp, class _Alloc>1010inline _LIBCPP_HIDE_FROM_ABI void1011forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, forward_list&& __x, const_iterator __i) {1012 splice_after(__p, __x, __i);1013}1014 1015template <class _Tp, class _Alloc>1016inline _LIBCPP_HIDE_FROM_ABI void forward_list<_Tp, _Alloc>::splice_after(1017 const_iterator __p, forward_list&& __x, const_iterator __f, const_iterator __l) {1018 splice_after(__p, __x, __f, __l);1019}1020 1021template <class _Tp, class _Alloc>1022typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove(const value_type& __v) {1023 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1024 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;1025 const iterator __e = end();1026 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {1027 if (__i.__get_begin()->__next_->__get_value() == __v) {1028 ++__count_removed;1029 iterator __j = std::next(__i, 2);1030 for (; __j != __e && *__j == __v; ++__j)1031 ++__count_removed;1032 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);1033 if (__j == __e)1034 break;1035 __i = __j;1036 } else1037 ++__i;1038 }1039 1040 return (__remove_return_type)__count_removed;1041}1042 1043template <class _Tp, class _Alloc>1044template <class _Predicate>1045typename forward_list<_Tp, _Alloc>::__remove_return_type forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) {1046 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1047 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;1048 const iterator __e = end();1049 for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) {1050 if (__pred(__i.__get_begin()->__next_->__get_value())) {1051 ++__count_removed;1052 iterator __j = std::next(__i, 2);1053 for (; __j != __e && __pred(*__j); ++__j)1054 ++__count_removed;1055 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);1056 if (__j == __e)1057 break;1058 __i = __j;1059 } else1060 ++__i;1061 }1062 1063 return (__remove_return_type)__count_removed;1064}1065 1066template <class _Tp, class _Alloc>1067template <class _BinaryPredicate>1068typename forward_list<_Tp, _Alloc>::__remove_return_type1069forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) {1070 forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing1071 typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0;1072 for (iterator __i = begin(), __e = end(); __i != __e;) {1073 iterator __j = std::next(__i);1074 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)1075 ++__count_removed;1076 if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer())1077 __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j);1078 __i = __j;1079 }1080 1081 return (__remove_return_type)__count_removed;1082}1083 1084template <class _Tp, class _Alloc>1085template <class _Compare>1086void forward_list<_Tp, _Alloc>::merge(forward_list& __x, _Compare __comp) {1087 if (this != std::addressof(__x)) {1088 __base::__before_begin()->__next_ =1089 __merge(__base::__before_begin()->__next_, __x.__before_begin()->__next_, __comp);1090 __x.__before_begin()->__next_ = nullptr;1091 }1092}1093 1094template <class _Tp, class _Alloc>1095template <class _Compare>1096typename forward_list<_Tp, _Alloc>::__node_pointer1097forward_list<_Tp, _Alloc>::__merge(__node_pointer __f1, __node_pointer __f2, _Compare& __comp) {1098 if (__f1 == nullptr)1099 return __f2;1100 if (__f2 == nullptr)1101 return __f1;1102 __node_pointer __r;1103 if (__comp(__f2->__get_value(), __f1->__get_value())) {1104 __node_pointer __t = __f2;1105 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))1106 __t = __t->__next_;1107 __r = __f2;1108 __f2 = __t->__next_;1109 __t->__next_ = __f1;1110 } else1111 __r = __f1;1112 __node_pointer __p = __f1;1113 __f1 = __f1->__next_;1114 while (__f1 != nullptr && __f2 != nullptr) {1115 if (__comp(__f2->__get_value(), __f1->__get_value())) {1116 __node_pointer __t = __f2;1117 while (__t->__next_ != nullptr && __comp(__t->__next_->__get_value(), __f1->__get_value()))1118 __t = __t->__next_;1119 __p->__next_ = __f2;1120 __f2 = __t->__next_;1121 __t->__next_ = __f1;1122 }1123 __p = __f1;1124 __f1 = __f1->__next_;1125 }1126 if (__f2 != nullptr)1127 __p->__next_ = __f2;1128 return __r;1129}1130 1131template <class _Tp, class _Alloc>1132template <class _Compare>1133inline void forward_list<_Tp, _Alloc>::sort(_Compare __comp) {1134 __base::__before_begin()->__next_ = __sort(__base::__before_begin()->__next_, std::distance(begin(), end()), __comp);1135}1136 1137template <class _Tp, class _Alloc>1138template <class _Compare>1139typename forward_list<_Tp, _Alloc>::__node_pointer1140forward_list<_Tp, _Alloc>::__sort(__node_pointer __f1, difference_type __sz, _Compare& __comp) {1141 switch (__sz) {1142 case 0:1143 case 1:1144 return __f1;1145 case 2:1146 if (__comp(__f1->__next_->__get_value(), __f1->__get_value())) {1147 __node_pointer __t = __f1->__next_;1148 __t->__next_ = __f1;1149 __f1->__next_ = nullptr;1150 __f1 = __t;1151 }1152 return __f1;1153 }1154 difference_type __sz1 = __sz / 2;1155 difference_type __sz2 = __sz - __sz1;1156 __node_pointer __t = std::next(iterator(__f1), __sz1 - 1).__get_unsafe_node_pointer();1157 __node_pointer __f2 = __t->__next_;1158 __t->__next_ = nullptr;1159 return __merge(__sort(__f1, __sz1, __comp), __sort(__f2, __sz2, __comp), __comp);1160}1161 1162template <class _Tp, class _Alloc>1163void forward_list<_Tp, _Alloc>::reverse() _NOEXCEPT {1164 __node_pointer __p = __base::__before_begin()->__next_;1165 if (__p != nullptr) {1166 __node_pointer __f = __p->__next_;1167 __p->__next_ = nullptr;1168 while (__f != nullptr) {1169 __node_pointer __t = __f->__next_;1170 __f->__next_ = __p;1171 __p = __f;1172 __f = __t;1173 }1174 __base::__before_begin()->__next_ = __p;1175 }1176}1177 1178template <class _Tp, class _Alloc>1179_LIBCPP_HIDE_FROM_ABI bool operator==(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {1180 typedef forward_list<_Tp, _Alloc> _Cp;1181 typedef typename _Cp::const_iterator _Ip;1182 _Ip __ix = __x.begin();1183 _Ip __ex = __x.end();1184 _Ip __iy = __y.begin();1185 _Ip __ey = __y.end();1186 for (; __ix != __ex && __iy != __ey; ++__ix, ++__iy)1187 if (!(*__ix == *__iy))1188 return false;1189 return (__ix == __ex) == (__iy == __ey);1190}1191 1192template <class _Tp, class _Alloc>1193inline _LIBCPP_HIDE_FROM_ABI bool1194operator!=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {1195 return !(__x == __y);1196}1197 1198template <class _Tp, class _Alloc>1199inline _LIBCPP_HIDE_FROM_ABI bool1200operator<(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {1201 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());1202}1203 1204template <class _Tp, class _Alloc>1205inline _LIBCPP_HIDE_FROM_ABI bool1206operator>(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {1207 return __y < __x;1208}1209 1210template <class _Tp, class _Alloc>1211inline _LIBCPP_HIDE_FROM_ABI bool1212operator>=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {1213 return !(__x < __y);1214}1215 1216template <class _Tp, class _Alloc>1217inline _LIBCPP_HIDE_FROM_ABI bool1218operator<=(const forward_list<_Tp, _Alloc>& __x, const forward_list<_Tp, _Alloc>& __y) {1219 return !(__y < __x);1220}1221 1222template <class _Tp, class _Alloc>1223inline _LIBCPP_HIDE_FROM_ABI void swap(forward_list<_Tp, _Alloc>& __x, forward_list<_Tp, _Alloc>& __y) {1224 __x.swap(__y);1225}1226 1227_LIBCPP_END_NAMESPACE_STD1228 1229_LIBCPP_POP_MACROS1230 1231#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)1232# include <__cxx03/algorithm>1233# include <__cxx03/atomic>1234# include <__cxx03/cstdint>1235# include <__cxx03/cstdlib>1236# include <__cxx03/cstring>1237# include <__cxx03/functional>1238# include <__cxx03/iosfwd>1239# include <__cxx03/iterator>1240# include <__cxx03/stdexcept>1241# include <__cxx03/type_traits>1242# include <__cxx03/typeinfo>1243#endif1244 1245#endif // _LIBCPP___CXX03_FORWARD_LIST1246