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