1 // <forward_list.h> -*- C++ -*- 2 3 // Copyright (C) 2008-2018 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/forward_list.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{forward_list} 28 */ 29 30 #ifndef _FORWARD_LIST_H 31 #define _FORWARD_LIST_H 1 32 33 #pragma GCC system_header 34 35 #include <initializer_list> 36 #include <bits/stl_iterator_base_types.h> 37 #include <bits/stl_iterator.h> 38 #include <bits/stl_algobase.h> 39 #include <bits/stl_function.h> 40 #include <bits/allocator.h> 41 #include <ext/alloc_traits.h> 42 #include <ext/aligned_buffer.h> 43 44 namespace std _GLIBCXX_VISIBILITY(default) 45 { 46 _GLIBCXX_BEGIN_NAMESPACE_VERSION 47 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 48 49 /** 50 * @brief A helper basic node class for %forward_list. 51 * This is just a linked list with nothing inside it. 52 * There are purely list shuffling utility methods here. 53 */ 54 struct _Fwd_list_node_base 55 { 56 _Fwd_list_node_base() = default; 57 _Fwd_list_node_base(_Fwd_list_node_base&& __x) noexcept 58 : _M_next(__x._M_next) 59 { __x._M_next = nullptr; } 60 61 _Fwd_list_node_base(const _Fwd_list_node_base&) = delete; 62 _Fwd_list_node_base& operator=(const _Fwd_list_node_base&) = delete; 63 64 _Fwd_list_node_base& 65 operator=(_Fwd_list_node_base&& __x) noexcept 66 { 67 _M_next = __x._M_next; 68 __x._M_next = nullptr; 69 return *this; 70 } 71 72 _Fwd_list_node_base* _M_next = nullptr; 73 74 _Fwd_list_node_base* 75 _M_transfer_after(_Fwd_list_node_base* __begin, 76 _Fwd_list_node_base* __end) noexcept 77 { 78 _Fwd_list_node_base* __keep = __begin->_M_next; 79 if (__end) 80 { 81 __begin->_M_next = __end->_M_next; 82 __end->_M_next = _M_next; 83 } 84 else 85 __begin->_M_next = nullptr; 86 _M_next = __keep; 87 return __end; 88 } 89 90 void 91 _M_reverse_after() noexcept 92 { 93 _Fwd_list_node_base* __tail = _M_next; 94 if (!__tail) 95 return; 96 while (_Fwd_list_node_base* __temp = __tail->_M_next) 97 { 98 _Fwd_list_node_base* __keep = _M_next; 99 _M_next = __temp; 100 __tail->_M_next = __temp->_M_next; 101 _M_next->_M_next = __keep; 102 } 103 } 104 }; 105 106 /** 107 * @brief A helper node class for %forward_list. 108 * This is just a linked list with uninitialized storage for a 109 * data value in each node. 110 * There is a sorting utility method. 111 */ 112 template<typename _Tp> 113 struct _Fwd_list_node 114 : public _Fwd_list_node_base 115 { 116 _Fwd_list_node() = default; 117 118 __gnu_cxx::__aligned_buffer<_Tp> _M_storage; 119 120 _Tp* 121 _M_valptr() noexcept 122 { return _M_storage._M_ptr(); } 123 124 const _Tp* 125 _M_valptr() const noexcept 126 { return _M_storage._M_ptr(); } 127 }; 128 129 /** 130 * @brief A forward_list::iterator. 131 * 132 * All the functions are op overloads. 133 */ 134 template<typename _Tp> 135 struct _Fwd_list_iterator 136 { 137 typedef _Fwd_list_iterator<_Tp> _Self; 138 typedef _Fwd_list_node<_Tp> _Node; 139 140 typedef _Tp value_type; 141 typedef _Tp* pointer; 142 typedef _Tp& reference; 143 typedef ptrdiff_t difference_type; 144 typedef std::forward_iterator_tag iterator_category; 145 146 _Fwd_list_iterator() noexcept 147 : _M_node() { } 148 149 explicit 150 _Fwd_list_iterator(_Fwd_list_node_base* __n) noexcept 151 : _M_node(__n) { } 152 153 reference 154 operator*() const noexcept 155 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } 156 157 pointer 158 operator->() const noexcept 159 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } 160 161 _Self& 162 operator++() noexcept 163 { 164 _M_node = _M_node->_M_next; 165 return *this; 166 } 167 168 _Self 169 operator++(int) noexcept 170 { 171 _Self __tmp(*this); 172 _M_node = _M_node->_M_next; 173 return __tmp; 174 } 175 176 bool 177 operator==(const _Self& __x) const noexcept 178 { return _M_node == __x._M_node; } 179 180 bool 181 operator!=(const _Self& __x) const noexcept 182 { return _M_node != __x._M_node; } 183 184 _Self 185 _M_next() const noexcept 186 { 187 if (_M_node) 188 return _Fwd_list_iterator(_M_node->_M_next); 189 else 190 return _Fwd_list_iterator(nullptr); 191 } 192 193 _Fwd_list_node_base* _M_node; 194 }; 195 196 /** 197 * @brief A forward_list::const_iterator. 198 * 199 * All the functions are op overloads. 200 */ 201 template<typename _Tp> 202 struct _Fwd_list_const_iterator 203 { 204 typedef _Fwd_list_const_iterator<_Tp> _Self; 205 typedef const _Fwd_list_node<_Tp> _Node; 206 typedef _Fwd_list_iterator<_Tp> iterator; 207 208 typedef _Tp value_type; 209 typedef const _Tp* pointer; 210 typedef const _Tp& reference; 211 typedef ptrdiff_t difference_type; 212 typedef std::forward_iterator_tag iterator_category; 213 214 _Fwd_list_const_iterator() noexcept 215 : _M_node() { } 216 217 explicit 218 _Fwd_list_const_iterator(const _Fwd_list_node_base* __n) noexcept 219 : _M_node(__n) { } 220 221 _Fwd_list_const_iterator(const iterator& __iter) noexcept 222 : _M_node(__iter._M_node) { } 223 224 reference 225 operator*() const noexcept 226 { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); } 227 228 pointer 229 operator->() const noexcept 230 { return static_cast<_Node*>(this->_M_node)->_M_valptr(); } 231 232 _Self& 233 operator++() noexcept 234 { 235 _M_node = _M_node->_M_next; 236 return *this; 237 } 238 239 _Self 240 operator++(int) noexcept 241 { 242 _Self __tmp(*this); 243 _M_node = _M_node->_M_next; 244 return __tmp; 245 } 246 247 bool 248 operator==(const _Self& __x) const noexcept 249 { return _M_node == __x._M_node; } 250 251 bool 252 operator!=(const _Self& __x) const noexcept 253 { return _M_node != __x._M_node; } 254 255 _Self 256 _M_next() const noexcept 257 { 258 if (this->_M_node) 259 return _Fwd_list_const_iterator(_M_node->_M_next); 260 else 261 return _Fwd_list_const_iterator(nullptr); 262 } 263 264 const _Fwd_list_node_base* _M_node; 265 }; 266 267 /** 268 * @brief Forward list iterator equality comparison. 269 */ 270 template<typename _Tp> 271 inline bool 272 operator==(const _Fwd_list_iterator<_Tp>& __x, 273 const _Fwd_list_const_iterator<_Tp>& __y) noexcept 274 { return __x._M_node == __y._M_node; } 275 276 /** 277 * @brief Forward list iterator inequality comparison. 278 */ 279 template<typename _Tp> 280 inline bool 281 operator!=(const _Fwd_list_iterator<_Tp>& __x, 282 const _Fwd_list_const_iterator<_Tp>& __y) noexcept 283 { return __x._M_node != __y._M_node; } 284 285 /** 286 * @brief Base class for %forward_list. 287 */ 288 template<typename _Tp, typename _Alloc> 289 struct _Fwd_list_base 290 { 291 protected: 292 typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type; 293 typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; 294 295 struct _Fwd_list_impl 296 : public _Node_alloc_type 297 { 298 _Fwd_list_node_base _M_head; 299 300 _Fwd_list_impl() 301 noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value) 302 : _Node_alloc_type(), _M_head() 303 { } 304 305 _Fwd_list_impl(_Fwd_list_impl&&) = default; 306 307 _Fwd_list_impl(_Fwd_list_impl&& __fl, _Node_alloc_type&& __a) 308 : _Node_alloc_type(std::move(__a)), _M_head(std::move(__fl._M_head)) 309 { } 310 311 _Fwd_list_impl(_Node_alloc_type&& __a) 312 : _Node_alloc_type(std::move(__a)), _M_head() 313 { } 314 }; 315 316 _Fwd_list_impl _M_impl; 317 318 public: 319 typedef _Fwd_list_iterator<_Tp> iterator; 320 typedef _Fwd_list_const_iterator<_Tp> const_iterator; 321 typedef _Fwd_list_node<_Tp> _Node; 322 323 _Node_alloc_type& 324 _M_get_Node_allocator() noexcept 325 { return this->_M_impl; } 326 327 const _Node_alloc_type& 328 _M_get_Node_allocator() const noexcept 329 { return this->_M_impl; } 330 331 _Fwd_list_base() = default; 332 333 _Fwd_list_base(_Node_alloc_type&& __a) 334 : _M_impl(std::move(__a)) { } 335 336 // When allocators are always equal. 337 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a, 338 std::true_type) 339 : _M_impl(std::move(__lst._M_impl), std::move(__a)) 340 { } 341 342 // When allocators are not always equal. 343 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a); 344 345 _Fwd_list_base(_Fwd_list_base&&) = default; 346 347 ~_Fwd_list_base() 348 { _M_erase_after(&_M_impl._M_head, nullptr); } 349 350 protected: 351 _Node* 352 _M_get_node() 353 { 354 auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); 355 return std::__to_address(__ptr); 356 } 357 358 template<typename... _Args> 359 _Node* 360 _M_create_node(_Args&&... __args) 361 { 362 _Node* __node = this->_M_get_node(); 363 __try 364 { 365 ::new ((void*)__node) _Node; 366 _Node_alloc_traits::construct(_M_get_Node_allocator(), 367 __node->_M_valptr(), 368 std::forward<_Args>(__args)...); 369 } 370 __catch(...) 371 { 372 this->_M_put_node(__node); 373 __throw_exception_again; 374 } 375 return __node; 376 } 377 378 template<typename... _Args> 379 _Fwd_list_node_base* 380 _M_insert_after(const_iterator __pos, _Args&&... __args); 381 382 void 383 _M_put_node(_Node* __p) 384 { 385 typedef typename _Node_alloc_traits::pointer _Ptr; 386 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__p); 387 _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ptr, 1); 388 } 389 390 _Fwd_list_node_base* 391 _M_erase_after(_Fwd_list_node_base* __pos); 392 393 _Fwd_list_node_base* 394 _M_erase_after(_Fwd_list_node_base* __pos, 395 _Fwd_list_node_base* __last); 396 }; 397 398 /** 399 * @brief A standard container with linear time access to elements, 400 * and fixed time insertion/deletion at any point in the sequence. 401 * 402 * @ingroup sequences 403 * 404 * @tparam _Tp Type of element. 405 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. 406 * 407 * Meets the requirements of a <a href="tables.html#65">container</a>, a 408 * <a href="tables.html#67">sequence</a>, including the 409 * <a href="tables.html#68">optional sequence requirements</a> with the 410 * %exception of @c at and @c operator[]. 411 * 412 * This is a @e singly @e linked %list. Traversal up the 413 * %list requires linear time, but adding and removing elements (or 414 * @e nodes) is done in constant time, regardless of where the 415 * change takes place. Unlike std::vector and std::deque, 416 * random-access iterators are not provided, so subscripting ( @c 417 * [] ) access is not allowed. For algorithms which only need 418 * sequential access, this lack makes no difference. 419 * 420 * Also unlike the other standard containers, std::forward_list provides 421 * specialized algorithms %unique to linked lists, such as 422 * splicing, sorting, and in-place reversal. 423 */ 424 template<typename _Tp, typename _Alloc = allocator<_Tp>> 425 class forward_list : private _Fwd_list_base<_Tp, _Alloc> 426 { 427 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value, 428 "std::forward_list must have a non-const, non-volatile value_type"); 429 #ifdef __STRICT_ANSI__ 430 static_assert(is_same<typename _Alloc::value_type, _Tp>::value, 431 "std::forward_list must have the same value_type as its allocator"); 432 #endif 433 434 private: 435 typedef _Fwd_list_base<_Tp, _Alloc> _Base; 436 typedef _Fwd_list_node<_Tp> _Node; 437 typedef _Fwd_list_node_base _Node_base; 438 typedef typename _Base::_Node_alloc_type _Node_alloc_type; 439 typedef typename _Base::_Node_alloc_traits _Node_alloc_traits; 440 typedef allocator_traits<__alloc_rebind<_Alloc, _Tp>> _Alloc_traits; 441 442 public: 443 // types: 444 typedef _Tp value_type; 445 typedef typename _Alloc_traits::pointer pointer; 446 typedef typename _Alloc_traits::const_pointer const_pointer; 447 typedef value_type& reference; 448 typedef const value_type& const_reference; 449 450 typedef _Fwd_list_iterator<_Tp> iterator; 451 typedef _Fwd_list_const_iterator<_Tp> const_iterator; 452 typedef std::size_t size_type; 453 typedef std::ptrdiff_t difference_type; 454 typedef _Alloc allocator_type; 455 456 // 23.3.4.2 construct/copy/destroy: 457 458 /** 459 * @brief Creates a %forward_list with no elements. 460 */ 461 forward_list() = default; 462 463 /** 464 * @brief Creates a %forward_list with no elements. 465 * @param __al An allocator object. 466 */ 467 explicit 468 forward_list(const _Alloc& __al) noexcept 469 : _Base(_Node_alloc_type(__al)) 470 { } 471 472 /** 473 * @brief Copy constructor with allocator argument. 474 * @param __list Input list to copy. 475 * @param __al An allocator object. 476 */ 477 forward_list(const forward_list& __list, const _Alloc& __al) 478 : _Base(_Node_alloc_type(__al)) 479 { _M_range_initialize(__list.begin(), __list.end()); } 480 481 private: 482 forward_list(forward_list&& __list, _Node_alloc_type&& __al, 483 false_type) 484 : _Base(std::move(__list), std::move(__al)) 485 { 486 // If __list is not empty it means its allocator is not equal to __a, 487 // so we need to move from each element individually. 488 insert_after(cbefore_begin(), 489 std::__make_move_if_noexcept_iterator(__list.begin()), 490 std::__make_move_if_noexcept_iterator(__list.end())); 491 } 492 493 forward_list(forward_list&& __list, _Node_alloc_type&& __al, 494 true_type) 495 noexcept 496 : _Base(std::move(__list), _Node_alloc_type(__al), true_type{}) 497 { } 498 499 public: 500 /** 501 * @brief Move constructor with allocator argument. 502 * @param __list Input list to move. 503 * @param __al An allocator object. 504 */ 505 forward_list(forward_list&& __list, const _Alloc& __al) 506 noexcept(_Node_alloc_traits::_S_always_equal()) 507 : forward_list(std::move(__list), _Node_alloc_type(__al), 508 typename _Node_alloc_traits::is_always_equal{}) 509 { } 510 511 /** 512 * @brief Creates a %forward_list with default constructed elements. 513 * @param __n The number of elements to initially create. 514 * @param __al An allocator object. 515 * 516 * This constructor creates the %forward_list with @a __n default 517 * constructed elements. 518 */ 519 explicit 520 forward_list(size_type __n, const _Alloc& __al = _Alloc()) 521 : _Base(_Node_alloc_type(__al)) 522 { _M_default_initialize(__n); } 523 524 /** 525 * @brief Creates a %forward_list with copies of an exemplar element. 526 * @param __n The number of elements to initially create. 527 * @param __value An element to copy. 528 * @param __al An allocator object. 529 * 530 * This constructor fills the %forward_list with @a __n copies of 531 * @a __value. 532 */ 533 forward_list(size_type __n, const _Tp& __value, 534 const _Alloc& __al = _Alloc()) 535 : _Base(_Node_alloc_type(__al)) 536 { _M_fill_initialize(__n, __value); } 537 538 /** 539 * @brief Builds a %forward_list from a range. 540 * @param __first An input iterator. 541 * @param __last An input iterator. 542 * @param __al An allocator object. 543 * 544 * Create a %forward_list consisting of copies of the elements from 545 * [@a __first,@a __last). This is linear in N (where N is 546 * distance(@a __first,@a __last)). 547 */ 548 template<typename _InputIterator, 549 typename = std::_RequireInputIter<_InputIterator>> 550 forward_list(_InputIterator __first, _InputIterator __last, 551 const _Alloc& __al = _Alloc()) 552 : _Base(_Node_alloc_type(__al)) 553 { _M_range_initialize(__first, __last); } 554 555 /** 556 * @brief The %forward_list copy constructor. 557 * @param __list A %forward_list of identical element and allocator 558 * types. 559 */ 560 forward_list(const forward_list& __list) 561 : _Base(_Node_alloc_traits::_S_select_on_copy( 562 __list._M_get_Node_allocator())) 563 { _M_range_initialize(__list.begin(), __list.end()); } 564 565 /** 566 * @brief The %forward_list move constructor. 567 * @param __list A %forward_list of identical element and allocator 568 * types. 569 * 570 * The newly-created %forward_list contains the exact contents of the 571 * moved instance. The contents of the moved instance are a valid, but 572 * unspecified %forward_list. 573 */ 574 forward_list(forward_list&&) = default; 575 576 /** 577 * @brief Builds a %forward_list from an initializer_list 578 * @param __il An initializer_list of value_type. 579 * @param __al An allocator object. 580 * 581 * Create a %forward_list consisting of copies of the elements 582 * in the initializer_list @a __il. This is linear in __il.size(). 583 */ 584 forward_list(std::initializer_list<_Tp> __il, 585 const _Alloc& __al = _Alloc()) 586 : _Base(_Node_alloc_type(__al)) 587 { _M_range_initialize(__il.begin(), __il.end()); } 588 589 /** 590 * @brief The forward_list dtor. 591 */ 592 ~forward_list() noexcept 593 { } 594 595 /** 596 * @brief The %forward_list assignment operator. 597 * @param __list A %forward_list of identical element and allocator 598 * types. 599 * 600 * All the elements of @a __list are copied. 601 * 602 * Whether the allocator is copied depends on the allocator traits. 603 */ 604 forward_list& 605 operator=(const forward_list& __list); 606 607 /** 608 * @brief The %forward_list move assignment operator. 609 * @param __list A %forward_list of identical element and allocator 610 * types. 611 * 612 * The contents of @a __list are moved into this %forward_list 613 * (without copying, if the allocators permit it). 614 * 615 * Afterwards @a __list is a valid, but unspecified %forward_list 616 * 617 * Whether the allocator is moved depends on the allocator traits. 618 */ 619 forward_list& 620 operator=(forward_list&& __list) 621 noexcept(_Node_alloc_traits::_S_nothrow_move()) 622 { 623 constexpr bool __move_storage = 624 _Node_alloc_traits::_S_propagate_on_move_assign() 625 || _Node_alloc_traits::_S_always_equal(); 626 _M_move_assign(std::move(__list), __bool_constant<__move_storage>()); 627 return *this; 628 } 629 630 /** 631 * @brief The %forward_list initializer list assignment operator. 632 * @param __il An initializer_list of value_type. 633 * 634 * Replace the contents of the %forward_list with copies of the 635 * elements in the initializer_list @a __il. This is linear in 636 * __il.size(). 637 */ 638 forward_list& 639 operator=(std::initializer_list<_Tp> __il) 640 { 641 assign(__il); 642 return *this; 643 } 644 645 /** 646 * @brief Assigns a range to a %forward_list. 647 * @param __first An input iterator. 648 * @param __last An input iterator. 649 * 650 * This function fills a %forward_list with copies of the elements 651 * in the range [@a __first,@a __last). 652 * 653 * Note that the assignment completely changes the %forward_list and 654 * that the number of elements of the resulting %forward_list is the 655 * same as the number of elements assigned. 656 */ 657 template<typename _InputIterator, 658 typename = std::_RequireInputIter<_InputIterator>> 659 void 660 assign(_InputIterator __first, _InputIterator __last) 661 { 662 typedef is_assignable<_Tp, decltype(*__first)> __assignable; 663 _M_assign(__first, __last, __assignable()); 664 } 665 666 /** 667 * @brief Assigns a given value to a %forward_list. 668 * @param __n Number of elements to be assigned. 669 * @param __val Value to be assigned. 670 * 671 * This function fills a %forward_list with @a __n copies of the 672 * given value. Note that the assignment completely changes the 673 * %forward_list, and that the resulting %forward_list has __n 674 * elements. 675 */ 676 void 677 assign(size_type __n, const _Tp& __val) 678 { _M_assign_n(__n, __val, is_copy_assignable<_Tp>()); } 679 680 /** 681 * @brief Assigns an initializer_list to a %forward_list. 682 * @param __il An initializer_list of value_type. 683 * 684 * Replace the contents of the %forward_list with copies of the 685 * elements in the initializer_list @a __il. This is linear in 686 * il.size(). 687 */ 688 void 689 assign(std::initializer_list<_Tp> __il) 690 { assign(__il.begin(), __il.end()); } 691 692 /// Get a copy of the memory allocation object. 693 allocator_type 694 get_allocator() const noexcept 695 { return allocator_type(this->_M_get_Node_allocator()); } 696 697 // 23.3.4.3 iterators: 698 699 /** 700 * Returns a read/write iterator that points before the first element 701 * in the %forward_list. Iteration is done in ordinary element order. 702 */ 703 iterator 704 before_begin() noexcept 705 { return iterator(&this->_M_impl._M_head); } 706 707 /** 708 * Returns a read-only (constant) iterator that points before the 709 * first element in the %forward_list. Iteration is done in ordinary 710 * element order. 711 */ 712 const_iterator 713 before_begin() const noexcept 714 { return const_iterator(&this->_M_impl._M_head); } 715 716 /** 717 * Returns a read/write iterator that points to the first element 718 * in the %forward_list. Iteration is done in ordinary element order. 719 */ 720 iterator 721 begin() noexcept 722 { return iterator(this->_M_impl._M_head._M_next); } 723 724 /** 725 * Returns a read-only (constant) iterator that points to the first 726 * element in the %forward_list. Iteration is done in ordinary 727 * element order. 728 */ 729 const_iterator 730 begin() const noexcept 731 { return const_iterator(this->_M_impl._M_head._M_next); } 732 733 /** 734 * Returns a read/write iterator that points one past the last 735 * element in the %forward_list. Iteration is done in ordinary 736 * element order. 737 */ 738 iterator 739 end() noexcept 740 { return iterator(nullptr); } 741 742 /** 743 * Returns a read-only iterator that points one past the last 744 * element in the %forward_list. Iteration is done in ordinary 745 * element order. 746 */ 747 const_iterator 748 end() const noexcept 749 { return const_iterator(nullptr); } 750 751 /** 752 * Returns a read-only (constant) iterator that points to the 753 * first element in the %forward_list. Iteration is done in ordinary 754 * element order. 755 */ 756 const_iterator 757 cbegin() const noexcept 758 { return const_iterator(this->_M_impl._M_head._M_next); } 759 760 /** 761 * Returns a read-only (constant) iterator that points before the 762 * first element in the %forward_list. Iteration is done in ordinary 763 * element order. 764 */ 765 const_iterator 766 cbefore_begin() const noexcept 767 { return const_iterator(&this->_M_impl._M_head); } 768 769 /** 770 * Returns a read-only (constant) iterator that points one past 771 * the last element in the %forward_list. Iteration is done in 772 * ordinary element order. 773 */ 774 const_iterator 775 cend() const noexcept 776 { return const_iterator(nullptr); } 777 778 /** 779 * Returns true if the %forward_list is empty. (Thus begin() would 780 * equal end().) 781 */ 782 bool 783 empty() const noexcept 784 { return this->_M_impl._M_head._M_next == nullptr; } 785 786 /** 787 * Returns the largest possible number of elements of %forward_list. 788 */ 789 size_type 790 max_size() const noexcept 791 { return _Node_alloc_traits::max_size(this->_M_get_Node_allocator()); } 792 793 // 23.3.4.4 element access: 794 795 /** 796 * Returns a read/write reference to the data at the first 797 * element of the %forward_list. 798 */ 799 reference 800 front() 801 { 802 _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next); 803 return *__front->_M_valptr(); 804 } 805 806 /** 807 * Returns a read-only (constant) reference to the data at the first 808 * element of the %forward_list. 809 */ 810 const_reference 811 front() const 812 { 813 _Node* __front = static_cast<_Node*>(this->_M_impl._M_head._M_next); 814 return *__front->_M_valptr(); 815 } 816 817 // 23.3.4.5 modifiers: 818 819 /** 820 * @brief Constructs object in %forward_list at the front of the 821 * list. 822 * @param __args Arguments. 823 * 824 * This function will insert an object of type Tp constructed 825 * with Tp(std::forward<Args>(args)...) at the front of the list 826 * Due to the nature of a %forward_list this operation can 827 * be done in constant time, and does not invalidate iterators 828 * and references. 829 */ 830 template<typename... _Args> 831 #if __cplusplus > 201402L 832 reference 833 #else 834 void 835 #endif 836 emplace_front(_Args&&... __args) 837 { 838 this->_M_insert_after(cbefore_begin(), 839 std::forward<_Args>(__args)...); 840 #if __cplusplus > 201402L 841 return front(); 842 #endif 843 } 844 845 /** 846 * @brief Add data to the front of the %forward_list. 847 * @param __val Data to be added. 848 * 849 * This is a typical stack operation. The function creates an 850 * element at the front of the %forward_list and assigns the given 851 * data to it. Due to the nature of a %forward_list this operation 852 * can be done in constant time, and does not invalidate iterators 853 * and references. 854 */ 855 void 856 push_front(const _Tp& __val) 857 { this->_M_insert_after(cbefore_begin(), __val); } 858 859 /** 860 * 861 */ 862 void 863 push_front(_Tp&& __val) 864 { this->_M_insert_after(cbefore_begin(), std::move(__val)); } 865 866 /** 867 * @brief Removes first element. 868 * 869 * This is a typical stack operation. It shrinks the %forward_list 870 * by one. Due to the nature of a %forward_list this operation can 871 * be done in constant time, and only invalidates iterators/references 872 * to the element being removed. 873 * 874 * Note that no data is returned, and if the first element's data 875 * is needed, it should be retrieved before pop_front() is 876 * called. 877 */ 878 void 879 pop_front() 880 { this->_M_erase_after(&this->_M_impl._M_head); } 881 882 /** 883 * @brief Constructs object in %forward_list after the specified 884 * iterator. 885 * @param __pos A const_iterator into the %forward_list. 886 * @param __args Arguments. 887 * @return An iterator that points to the inserted data. 888 * 889 * This function will insert an object of type T constructed 890 * with T(std::forward<Args>(args)...) after the specified 891 * location. Due to the nature of a %forward_list this operation can 892 * be done in constant time, and does not invalidate iterators 893 * and references. 894 */ 895 template<typename... _Args> 896 iterator 897 emplace_after(const_iterator __pos, _Args&&... __args) 898 { return iterator(this->_M_insert_after(__pos, 899 std::forward<_Args>(__args)...)); } 900 901 /** 902 * @brief Inserts given value into %forward_list after specified 903 * iterator. 904 * @param __pos An iterator into the %forward_list. 905 * @param __val Data to be inserted. 906 * @return An iterator that points to the inserted data. 907 * 908 * This function will insert a copy of the given value after 909 * the specified location. Due to the nature of a %forward_list this 910 * operation can be done in constant time, and does not 911 * invalidate iterators and references. 912 */ 913 iterator 914 insert_after(const_iterator __pos, const _Tp& __val) 915 { return iterator(this->_M_insert_after(__pos, __val)); } 916 917 /** 918 * 919 */ 920 iterator 921 insert_after(const_iterator __pos, _Tp&& __val) 922 { return iterator(this->_M_insert_after(__pos, std::move(__val))); } 923 924 /** 925 * @brief Inserts a number of copies of given data into the 926 * %forward_list. 927 * @param __pos An iterator into the %forward_list. 928 * @param __n Number of elements to be inserted. 929 * @param __val Data to be inserted. 930 * @return An iterator pointing to the last inserted copy of 931 * @a val or @a pos if @a n == 0. 932 * 933 * This function will insert a specified number of copies of the 934 * given data after the location specified by @a pos. 935 * 936 * This operation is linear in the number of elements inserted and 937 * does not invalidate iterators and references. 938 */ 939 iterator 940 insert_after(const_iterator __pos, size_type __n, const _Tp& __val); 941 942 /** 943 * @brief Inserts a range into the %forward_list. 944 * @param __pos An iterator into the %forward_list. 945 * @param __first An input iterator. 946 * @param __last An input iterator. 947 * @return An iterator pointing to the last inserted element or 948 * @a __pos if @a __first == @a __last. 949 * 950 * This function will insert copies of the data in the range 951 * [@a __first,@a __last) into the %forward_list after the 952 * location specified by @a __pos. 953 * 954 * This operation is linear in the number of elements inserted and 955 * does not invalidate iterators and references. 956 */ 957 template<typename _InputIterator, 958 typename = std::_RequireInputIter<_InputIterator>> 959 iterator 960 insert_after(const_iterator __pos, 961 _InputIterator __first, _InputIterator __last); 962 963 /** 964 * @brief Inserts the contents of an initializer_list into 965 * %forward_list after the specified iterator. 966 * @param __pos An iterator into the %forward_list. 967 * @param __il An initializer_list of value_type. 968 * @return An iterator pointing to the last inserted element 969 * or @a __pos if @a __il is empty. 970 * 971 * This function will insert copies of the data in the 972 * initializer_list @a __il into the %forward_list before the location 973 * specified by @a __pos. 974 * 975 * This operation is linear in the number of elements inserted and 976 * does not invalidate iterators and references. 977 */ 978 iterator 979 insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) 980 { return insert_after(__pos, __il.begin(), __il.end()); } 981 982 /** 983 * @brief Removes the element pointed to by the iterator following 984 * @c pos. 985 * @param __pos Iterator pointing before element to be erased. 986 * @return An iterator pointing to the element following the one 987 * that was erased, or end() if no such element exists. 988 * 989 * This function will erase the element at the given position and 990 * thus shorten the %forward_list by one. 991 * 992 * Due to the nature of a %forward_list this operation can be done 993 * in constant time, and only invalidates iterators/references to 994 * the element being removed. The user is also cautioned that 995 * this function only erases the element, and that if the element 996 * is itself a pointer, the pointed-to memory is not touched in 997 * any way. Managing the pointer is the user's responsibility. 998 */ 999 iterator 1000 erase_after(const_iterator __pos) 1001 { return iterator(this->_M_erase_after(const_cast<_Node_base*> 1002 (__pos._M_node))); } 1003 1004 /** 1005 * @brief Remove a range of elements. 1006 * @param __pos Iterator pointing before the first element to be 1007 * erased. 1008 * @param __last Iterator pointing to one past the last element to be 1009 * erased. 1010 * @return @ __last. 1011 * 1012 * This function will erase the elements in the range 1013 * @a (__pos,__last) and shorten the %forward_list accordingly. 1014 * 1015 * This operation is linear time in the size of the range and only 1016 * invalidates iterators/references to the element being removed. 1017 * The user is also cautioned that this function only erases the 1018 * elements, and that if the elements themselves are pointers, the 1019 * pointed-to memory is not touched in any way. Managing the pointer 1020 * is the user's responsibility. 1021 */ 1022 iterator 1023 erase_after(const_iterator __pos, const_iterator __last) 1024 { return iterator(this->_M_erase_after(const_cast<_Node_base*> 1025 (__pos._M_node), 1026 const_cast<_Node_base*> 1027 (__last._M_node))); } 1028 1029 /** 1030 * @brief Swaps data with another %forward_list. 1031 * @param __list A %forward_list of the same element and allocator 1032 * types. 1033 * 1034 * This exchanges the elements between two lists in constant 1035 * time. Note that the global std::swap() function is 1036 * specialized such that std::swap(l1,l2) will feed to this 1037 * function. 1038 * 1039 * Whether the allocators are swapped depends on the allocator traits. 1040 */ 1041 void 1042 swap(forward_list& __list) noexcept 1043 { 1044 std::swap(this->_M_impl._M_head._M_next, 1045 __list._M_impl._M_head._M_next); 1046 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(), 1047 __list._M_get_Node_allocator()); 1048 } 1049 1050 /** 1051 * @brief Resizes the %forward_list to the specified number of 1052 * elements. 1053 * @param __sz Number of elements the %forward_list should contain. 1054 * 1055 * This function will %resize the %forward_list to the specified 1056 * number of elements. If the number is smaller than the 1057 * %forward_list's current number of elements the %forward_list 1058 * is truncated, otherwise the %forward_list is extended and the 1059 * new elements are default constructed. 1060 */ 1061 void 1062 resize(size_type __sz); 1063 1064 /** 1065 * @brief Resizes the %forward_list to the specified number of 1066 * elements. 1067 * @param __sz Number of elements the %forward_list should contain. 1068 * @param __val Data with which new elements should be populated. 1069 * 1070 * This function will %resize the %forward_list to the specified 1071 * number of elements. If the number is smaller than the 1072 * %forward_list's current number of elements the %forward_list 1073 * is truncated, otherwise the %forward_list is extended and new 1074 * elements are populated with given data. 1075 */ 1076 void 1077 resize(size_type __sz, const value_type& __val); 1078 1079 /** 1080 * @brief Erases all the elements. 1081 * 1082 * Note that this function only erases 1083 * the elements, and that if the elements themselves are 1084 * pointers, the pointed-to memory is not touched in any way. 1085 * Managing the pointer is the user's responsibility. 1086 */ 1087 void 1088 clear() noexcept 1089 { this->_M_erase_after(&this->_M_impl._M_head, nullptr); } 1090 1091 // 23.3.4.6 forward_list operations: 1092 1093 /** 1094 * @brief Insert contents of another %forward_list. 1095 * @param __pos Iterator referencing the element to insert after. 1096 * @param __list Source list. 1097 * 1098 * The elements of @a list are inserted in constant time after 1099 * the element referenced by @a pos. @a list becomes an empty 1100 * list. 1101 * 1102 * Requires this != @a x. 1103 */ 1104 void 1105 splice_after(const_iterator __pos, forward_list&& __list) noexcept 1106 { 1107 if (!__list.empty()) 1108 _M_splice_after(__pos, __list.before_begin(), __list.end()); 1109 } 1110 1111 void 1112 splice_after(const_iterator __pos, forward_list& __list) noexcept 1113 { splice_after(__pos, std::move(__list)); } 1114 1115 /** 1116 * @brief Insert element from another %forward_list. 1117 * @param __pos Iterator referencing the element to insert after. 1118 * @param __list Source list. 1119 * @param __i Iterator referencing the element before the element 1120 * to move. 1121 * 1122 * Removes the element in list @a list referenced by @a i and 1123 * inserts it into the current list after @a pos. 1124 */ 1125 void 1126 splice_after(const_iterator __pos, forward_list&& __list, 1127 const_iterator __i) noexcept; 1128 1129 void 1130 splice_after(const_iterator __pos, forward_list& __list, 1131 const_iterator __i) noexcept 1132 { splice_after(__pos, std::move(__list), __i); } 1133 1134 /** 1135 * @brief Insert range from another %forward_list. 1136 * @param __pos Iterator referencing the element to insert after. 1137 * @param __list Source list. 1138 * @param __before Iterator referencing before the start of range 1139 * in list. 1140 * @param __last Iterator referencing the end of range in list. 1141 * 1142 * Removes elements in the range (__before,__last) and inserts them 1143 * after @a __pos in constant time. 1144 * 1145 * Undefined if @a __pos is in (__before,__last). 1146 * @{ 1147 */ 1148 void 1149 splice_after(const_iterator __pos, forward_list&&, 1150 const_iterator __before, const_iterator __last) noexcept 1151 { _M_splice_after(__pos, __before, __last); } 1152 1153 void 1154 splice_after(const_iterator __pos, forward_list&, 1155 const_iterator __before, const_iterator __last) noexcept 1156 { _M_splice_after(__pos, __before, __last); } 1157 // @} 1158 1159 /** 1160 * @brief Remove all elements equal to value. 1161 * @param __val The value to remove. 1162 * 1163 * Removes every element in the list equal to @a __val. 1164 * Remaining elements stay in list order. Note that this 1165 * function only erases the elements, and that if the elements 1166 * themselves are pointers, the pointed-to memory is not 1167 * touched in any way. Managing the pointer is the user's 1168 * responsibility. 1169 */ 1170 void 1171 remove(const _Tp& __val); 1172 1173 /** 1174 * @brief Remove all elements satisfying a predicate. 1175 * @param __pred Unary predicate function or object. 1176 * 1177 * Removes every element in the list for which the predicate 1178 * returns true. Remaining elements stay in list order. Note 1179 * that this function only erases the elements, and that if the 1180 * elements themselves are pointers, the pointed-to memory is 1181 * not touched in any way. Managing the pointer is the user's 1182 * responsibility. 1183 */ 1184 template<typename _Pred> 1185 void 1186 remove_if(_Pred __pred); 1187 1188 /** 1189 * @brief Remove consecutive duplicate elements. 1190 * 1191 * For each consecutive set of elements with the same value, 1192 * remove all but the first one. Remaining elements stay in 1193 * list order. Note that this function only erases the 1194 * elements, and that if the elements themselves are pointers, 1195 * the pointed-to memory is not touched in any way. Managing 1196 * the pointer is the user's responsibility. 1197 */ 1198 void 1199 unique() 1200 { unique(std::equal_to<_Tp>()); } 1201 1202 /** 1203 * @brief Remove consecutive elements satisfying a predicate. 1204 * @param __binary_pred Binary predicate function or object. 1205 * 1206 * For each consecutive set of elements [first,last) that 1207 * satisfy predicate(first,i) where i is an iterator in 1208 * [first,last), remove all but the first one. Remaining 1209 * elements stay in list order. Note that this function only 1210 * erases the elements, and that if the elements themselves are 1211 * pointers, the pointed-to memory is not touched in any way. 1212 * Managing the pointer is the user's responsibility. 1213 */ 1214 template<typename _BinPred> 1215 void 1216 unique(_BinPred __binary_pred); 1217 1218 /** 1219 * @brief Merge sorted lists. 1220 * @param __list Sorted list to merge. 1221 * 1222 * Assumes that both @a list and this list are sorted according to 1223 * operator<(). Merges elements of @a __list into this list in 1224 * sorted order, leaving @a __list empty when complete. Elements in 1225 * this list precede elements in @a __list that are equal. 1226 */ 1227 void 1228 merge(forward_list&& __list) 1229 { merge(std::move(__list), std::less<_Tp>()); } 1230 1231 void 1232 merge(forward_list& __list) 1233 { merge(std::move(__list)); } 1234 1235 /** 1236 * @brief Merge sorted lists according to comparison function. 1237 * @param __list Sorted list to merge. 1238 * @param __comp Comparison function defining sort order. 1239 * 1240 * Assumes that both @a __list and this list are sorted according to 1241 * comp. Merges elements of @a __list into this list 1242 * in sorted order, leaving @a __list empty when complete. Elements 1243 * in this list precede elements in @a __list that are equivalent 1244 * according to comp(). 1245 */ 1246 template<typename _Comp> 1247 void 1248 merge(forward_list&& __list, _Comp __comp); 1249 1250 template<typename _Comp> 1251 void 1252 merge(forward_list& __list, _Comp __comp) 1253 { merge(std::move(__list), __comp); } 1254 1255 /** 1256 * @brief Sort the elements of the list. 1257 * 1258 * Sorts the elements of this list in NlogN time. Equivalent 1259 * elements remain in list order. 1260 */ 1261 void 1262 sort() 1263 { sort(std::less<_Tp>()); } 1264 1265 /** 1266 * @brief Sort the forward_list using a comparison function. 1267 * 1268 * Sorts the elements of this list in NlogN time. Equivalent 1269 * elements remain in list order. 1270 */ 1271 template<typename _Comp> 1272 void 1273 sort(_Comp __comp); 1274 1275 /** 1276 * @brief Reverse the elements in list. 1277 * 1278 * Reverse the order of elements in the list in linear time. 1279 */ 1280 void 1281 reverse() noexcept 1282 { this->_M_impl._M_head._M_reverse_after(); } 1283 1284 private: 1285 // Called by the range constructor to implement [23.3.4.2]/9 1286 template<typename _InputIterator> 1287 void 1288 _M_range_initialize(_InputIterator __first, _InputIterator __last); 1289 1290 // Called by forward_list(n,v,a), and the range constructor when it 1291 // turns out to be the same thing. 1292 void 1293 _M_fill_initialize(size_type __n, const value_type& __value); 1294 1295 // Called by splice_after and insert_after. 1296 iterator 1297 _M_splice_after(const_iterator __pos, const_iterator __before, 1298 const_iterator __last); 1299 1300 // Called by forward_list(n). 1301 void 1302 _M_default_initialize(size_type __n); 1303 1304 // Called by resize(sz). 1305 void 1306 _M_default_insert_after(const_iterator __pos, size_type __n); 1307 1308 // Called by operator=(forward_list&&) 1309 void 1310 _M_move_assign(forward_list&& __list, true_type) noexcept 1311 { 1312 clear(); 1313 this->_M_impl._M_head._M_next = __list._M_impl._M_head._M_next; 1314 __list._M_impl._M_head._M_next = nullptr; 1315 std::__alloc_on_move(this->_M_get_Node_allocator(), 1316 __list._M_get_Node_allocator()); 1317 } 1318 1319 // Called by operator=(forward_list&&) 1320 void 1321 _M_move_assign(forward_list&& __list, false_type) 1322 { 1323 if (__list._M_get_Node_allocator() == this->_M_get_Node_allocator()) 1324 _M_move_assign(std::move(__list), true_type()); 1325 else 1326 // The rvalue's allocator cannot be moved, or is not equal, 1327 // so we need to individually move each element. 1328 this->assign(std::__make_move_if_noexcept_iterator(__list.begin()), 1329 std::__make_move_if_noexcept_iterator(__list.end())); 1330 } 1331 1332 // Called by assign(_InputIterator, _InputIterator) if _Tp is 1333 // CopyAssignable. 1334 template<typename _InputIterator> 1335 void 1336 _M_assign(_InputIterator __first, _InputIterator __last, true_type) 1337 { 1338 auto __prev = before_begin(); 1339 auto __curr = begin(); 1340 auto __end = end(); 1341 while (__curr != __end && __first != __last) 1342 { 1343 *__curr = *__first; 1344 ++__prev; 1345 ++__curr; 1346 ++__first; 1347 } 1348 if (__first != __last) 1349 insert_after(__prev, __first, __last); 1350 else if (__curr != __end) 1351 erase_after(__prev, __end); 1352 } 1353 1354 // Called by assign(_InputIterator, _InputIterator) if _Tp is not 1355 // CopyAssignable. 1356 template<typename _InputIterator> 1357 void 1358 _M_assign(_InputIterator __first, _InputIterator __last, false_type) 1359 { 1360 clear(); 1361 insert_after(cbefore_begin(), __first, __last); 1362 } 1363 1364 // Called by assign(size_type, const _Tp&) if Tp is CopyAssignable 1365 void 1366 _M_assign_n(size_type __n, const _Tp& __val, true_type) 1367 { 1368 auto __prev = before_begin(); 1369 auto __curr = begin(); 1370 auto __end = end(); 1371 while (__curr != __end && __n > 0) 1372 { 1373 *__curr = __val; 1374 ++__prev; 1375 ++__curr; 1376 --__n; 1377 } 1378 if (__n > 0) 1379 insert_after(__prev, __n, __val); 1380 else if (__curr != __end) 1381 erase_after(__prev, __end); 1382 } 1383 1384 // Called by assign(size_type, const _Tp&) if Tp is non-CopyAssignable 1385 void 1386 _M_assign_n(size_type __n, const _Tp& __val, false_type) 1387 { 1388 clear(); 1389 insert_after(cbefore_begin(), __n, __val); 1390 } 1391 }; 1392 1393 #if __cpp_deduction_guides >= 201606 1394 template<typename _InputIterator, typename _ValT 1395 = typename iterator_traits<_InputIterator>::value_type, 1396 typename _Allocator = allocator<_ValT>, 1397 typename = _RequireInputIter<_InputIterator>, 1398 typename = _RequireAllocator<_Allocator>> 1399 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator()) 1400 -> forward_list<_ValT, _Allocator>; 1401 #endif 1402 1403 /** 1404 * @brief Forward list equality comparison. 1405 * @param __lx A %forward_list 1406 * @param __ly A %forward_list of the same type as @a __lx. 1407 * @return True iff the elements of the forward lists are equal. 1408 * 1409 * This is an equivalence relation. It is linear in the number of 1410 * elements of the forward lists. Deques are considered equivalent 1411 * if corresponding elements compare equal. 1412 */ 1413 template<typename _Tp, typename _Alloc> 1414 bool 1415 operator==(const forward_list<_Tp, _Alloc>& __lx, 1416 const forward_list<_Tp, _Alloc>& __ly); 1417 1418 /** 1419 * @brief Forward list ordering relation. 1420 * @param __lx A %forward_list. 1421 * @param __ly A %forward_list of the same type as @a __lx. 1422 * @return True iff @a __lx is lexicographically less than @a __ly. 1423 * 1424 * This is a total ordering relation. It is linear in the number of 1425 * elements of the forward lists. The elements must be comparable 1426 * with @c <. 1427 * 1428 * See std::lexicographical_compare() for how the determination is made. 1429 */ 1430 template<typename _Tp, typename _Alloc> 1431 inline bool 1432 operator<(const forward_list<_Tp, _Alloc>& __lx, 1433 const forward_list<_Tp, _Alloc>& __ly) 1434 { return std::lexicographical_compare(__lx.cbegin(), __lx.cend(), 1435 __ly.cbegin(), __ly.cend()); } 1436 1437 /// Based on operator== 1438 template<typename _Tp, typename _Alloc> 1439 inline bool 1440 operator!=(const forward_list<_Tp, _Alloc>& __lx, 1441 const forward_list<_Tp, _Alloc>& __ly) 1442 { return !(__lx == __ly); } 1443 1444 /// Based on operator< 1445 template<typename _Tp, typename _Alloc> 1446 inline bool 1447 operator>(const forward_list<_Tp, _Alloc>& __lx, 1448 const forward_list<_Tp, _Alloc>& __ly) 1449 { return (__ly < __lx); } 1450 1451 /// Based on operator< 1452 template<typename _Tp, typename _Alloc> 1453 inline bool 1454 operator>=(const forward_list<_Tp, _Alloc>& __lx, 1455 const forward_list<_Tp, _Alloc>& __ly) 1456 { return !(__lx < __ly); } 1457 1458 /// Based on operator< 1459 template<typename _Tp, typename _Alloc> 1460 inline bool 1461 operator<=(const forward_list<_Tp, _Alloc>& __lx, 1462 const forward_list<_Tp, _Alloc>& __ly) 1463 { return !(__ly < __lx); } 1464 1465 /// See std::forward_list::swap(). 1466 template<typename _Tp, typename _Alloc> 1467 inline void 1468 swap(forward_list<_Tp, _Alloc>& __lx, 1469 forward_list<_Tp, _Alloc>& __ly) 1470 noexcept(noexcept(__lx.swap(__ly))) 1471 { __lx.swap(__ly); } 1472 1473 _GLIBCXX_END_NAMESPACE_CONTAINER 1474 _GLIBCXX_END_NAMESPACE_VERSION 1475 } // namespace std 1476 1477 #endif // _FORWARD_LIST_H 1478