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