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