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