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