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