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