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