Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/list.tcc
1 // List implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001-2025 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 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/list.tcc 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{list} 54 */ 55 56 #ifndef _LIST_TCC 57 #define _LIST_TCC 1 58 59 namespace std _GLIBCXX_VISIBILITY(default) 60 { 61 _GLIBCXX_BEGIN_NAMESPACE_VERSION 62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 63 64 template<typename _Tp, typename _Alloc> 65 void 66 _List_base<_Tp, _Alloc>:: 67 _M_clear() _GLIBCXX_NOEXCEPT 68 { 69 typedef typename _Node_traits::_Node _Node; 70 typedef typename _Node_traits::_Node_base _Node_base; 71 typename _Node_base::_Base_ptr __cur = _M_impl._M_node._M_next; 72 while (__cur != _M_impl._M_node._M_base()) 73 { 74 _Node& __tmp = static_cast<_Node&>(*__cur); 75 __cur = __tmp._M_next; 76 this->_M_destroy_node(__tmp._M_node_ptr()); 77 } 78 } 79 80 #if __cplusplus >= 201103L 81 template<typename _Tp, typename _Alloc> 82 template<typename... _Args> 83 typename list<_Tp, _Alloc>::iterator 84 list<_Tp, _Alloc>:: 85 emplace(const_iterator __position, _Args&&... __args) 86 { 87 _Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...); 88 __tmp->_M_hook(__position._M_const_cast()._M_node); 89 this->_M_inc_size(1); 90 return iterator(__tmp->_M_base()); 91 } 92 #endif 93 94 template<typename _Tp, typename _Alloc> 95 typename list<_Tp, _Alloc>::iterator 96 list<_Tp, _Alloc>:: 97 #if __cplusplus >= 201103L 98 insert(const_iterator __position, const value_type& __x) 99 #else 100 insert(iterator __position, const value_type& __x) 101 #endif 102 { 103 _Node_ptr __tmp = _M_create_node(__x); 104 __tmp->_M_hook(__position._M_const_cast()._M_node); 105 this->_M_inc_size(1); 106 return iterator(__tmp->_M_base()); 107 } 108 109 #if __cplusplus >= 201103L 110 template<typename _Tp, typename _Alloc> 111 typename list<_Tp, _Alloc>::iterator 112 list<_Tp, _Alloc>:: 113 insert(const_iterator __position, size_type __n, const value_type& __x) 114 { 115 if (__n) 116 { 117 list __tmp(__n, __x, get_allocator()); 118 iterator __it = __tmp.begin(); 119 splice(__position, __tmp); 120 return __it; 121 } 122 return __position._M_const_cast(); 123 } 124 125 template<typename _Tp, typename _Alloc> 126 template<typename _InputIterator, typename> 127 typename list<_Tp, _Alloc>::iterator 128 list<_Tp, _Alloc>:: 129 insert(const_iterator __position, _InputIterator __first, 130 _InputIterator __last) 131 { 132 list __tmp(__first, __last, get_allocator()); 133 if (!__tmp.empty()) 134 { 135 iterator __it = __tmp.begin(); 136 splice(__position, __tmp); 137 return __it; 138 } 139 return __position._M_const_cast(); 140 } 141 #endif 142 143 template<typename _Tp, typename _Alloc> 144 typename list<_Tp, _Alloc>::iterator 145 list<_Tp, _Alloc>:: 146 #if __cplusplus >= 201103L 147 erase(const_iterator __position) noexcept 148 #else 149 erase(iterator __position) 150 #endif 151 { 152 iterator __ret = iterator(__position._M_node->_M_next); 153 _M_erase(__position._M_const_cast()); 154 return __ret; 155 } 156 157 // Return a const_iterator indicating the position to start inserting or 158 // erasing elements (depending whether the list is growing or shrinking), 159 // and set __new_size to the number of new elements that must be appended. 160 // Equivalent to the following, but performed optimally: 161 // if (__new_size < size()) { 162 // __new_size = 0; 163 // return std::next(begin(), __new_size); 164 // } else { 165 // __newsize -= size(); 166 // return end(); 167 // } 168 template<typename _Tp, typename _Alloc> 169 typename list<_Tp, _Alloc>::const_iterator 170 list<_Tp, _Alloc>:: 171 _M_resize_pos(size_type& __new_size) const 172 { 173 const_iterator __i; 174 #if _GLIBCXX_USE_CXX11_ABI 175 const size_type __len = size(); 176 if (__new_size < __len) 177 { 178 if (__new_size <= __len / 2) 179 { 180 __i = begin(); 181 std::advance(__i, __new_size); 182 } 183 else 184 { 185 __i = end(); 186 ptrdiff_t __num_erase = __len - __new_size; 187 std::advance(__i, -__num_erase); 188 } 189 __new_size = 0; 190 return __i; 191 } 192 else 193 __i = end(); 194 #else 195 size_type __len = 0; 196 for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len) 197 ; 198 #endif 199 __new_size -= __len; 200 return __i; 201 } 202 203 #if __cplusplus >= 201103L 204 template<typename _Tp, typename _Alloc> 205 void 206 list<_Tp, _Alloc>:: 207 _M_default_append(size_type __n) 208 { 209 size_type __i = 0; 210 __try 211 { 212 for (; __i < __n; ++__i) 213 emplace_back(); 214 } 215 __catch(...) 216 { 217 for (; __i; --__i) 218 pop_back(); 219 __throw_exception_again; 220 } 221 } 222 223 template<typename _Tp, typename _Alloc> 224 void 225 list<_Tp, _Alloc>:: 226 resize(size_type __new_size) 227 { 228 const_iterator __i = _M_resize_pos(__new_size); 229 if (__new_size) 230 _M_default_append(__new_size); 231 else 232 erase(__i, end()); 233 } 234 235 template<typename _Tp, typename _Alloc> 236 void 237 list<_Tp, _Alloc>:: 238 resize(size_type __new_size, const value_type& __x) 239 { 240 const_iterator __i = _M_resize_pos(__new_size); 241 if (__new_size) 242 insert(end(), __new_size, __x); 243 else 244 erase(__i, end()); 245 } 246 #else 247 template<typename _Tp, typename _Alloc> 248 void 249 list<_Tp, _Alloc>:: 250 resize(size_type __new_size, value_type __x) 251 { 252 const_iterator __i = _M_resize_pos(__new_size); 253 if (__new_size) 254 insert(end(), __new_size, __x); 255 else 256 erase(__i._M_const_cast(), end()); 257 } 258 #endif 259 260 template<typename _Tp, typename _Alloc> 261 list<_Tp, _Alloc>& 262 list<_Tp, _Alloc>:: 263 operator=(const list& __x) 264 { 265 if (this != std::__addressof(__x)) 266 { 267 #if __cplusplus >= 201103L 268 if (_Node_alloc_traits::_S_propagate_on_copy_assign()) 269 { 270 auto& __this_alloc = this->_M_get_Node_allocator(); 271 auto& __that_alloc = __x._M_get_Node_allocator(); 272 if (!_Node_alloc_traits::_S_always_equal() 273 && __this_alloc != __that_alloc) 274 { 275 // replacement allocator cannot free existing storage 276 clear(); 277 } 278 std::__alloc_on_copy(__this_alloc, __that_alloc); 279 } 280 #endif 281 _M_assign_dispatch(__x.begin(), __x.end(), __false_type()); 282 } 283 return *this; 284 } 285 286 template<typename _Tp, typename _Alloc> 287 void 288 list<_Tp, _Alloc>:: 289 _M_fill_assign(size_type __n, const value_type& __val) 290 { 291 iterator __i = begin(); 292 for (; __i != end() && __n > 0; ++__i, --__n) 293 *__i = __val; 294 if (__n > 0) 295 insert(end(), __n, __val); 296 else 297 erase(__i, end()); 298 } 299 300 template<typename _Tp, typename _Alloc> 301 template <typename _InputIterator> 302 void 303 list<_Tp, _Alloc>:: 304 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 305 __false_type) 306 { 307 iterator __first1 = begin(); 308 iterator __last1 = end(); 309 for (; __first1 != __last1 && __first2 != __last2; 310 ++__first1, (void)++__first2) 311 *__first1 = *__first2; 312 if (__first2 == __last2) 313 erase(__first1, __last1); 314 else 315 insert(__last1, __first2, __last2); 316 } 317 318 #if __cplusplus > 201703L 319 # define _GLIBCXX20_ONLY(__expr) __expr 320 #else 321 # define _GLIBCXX20_ONLY(__expr) 322 #endif 323 324 template<typename _Tp, typename _Alloc> 325 typename list<_Tp, _Alloc>::__remove_return_type 326 list<_Tp, _Alloc>:: 327 remove(const value_type& __value) 328 { 329 #if !_GLIBCXX_USE_CXX11_ABI 330 size_type __removed __attribute__((__unused__)) = 0; 331 #endif 332 list __to_destroy(get_allocator()); 333 iterator __first = begin(); 334 iterator __last = end(); 335 while (__first != __last) 336 { 337 iterator __next = __first; 338 ++__next; 339 if (*__first == __value) 340 { 341 // _GLIBCXX_RESOLVE_LIB_DEFECTS 342 // 526. Is it undefined if a function in the standard changes 343 // in parameters? 344 __to_destroy.splice(__to_destroy.begin(), *this, __first); 345 #if !_GLIBCXX_USE_CXX11_ABI 346 _GLIBCXX20_ONLY( __removed++ ); 347 #endif 348 } 349 350 __first = __next; 351 } 352 353 #if !_GLIBCXX_USE_CXX11_ABI 354 return _GLIBCXX20_ONLY( __removed ); 355 #else 356 return _GLIBCXX20_ONLY( __to_destroy.size() ); 357 #endif 358 } 359 360 template<typename _Tp, typename _Alloc> 361 typename list<_Tp, _Alloc>::__remove_return_type 362 list<_Tp, _Alloc>:: 363 unique() 364 { 365 iterator __first = begin(); 366 iterator __last = end(); 367 if (__first == __last) 368 return _GLIBCXX20_ONLY( 0 ); 369 #if !_GLIBCXX_USE_CXX11_ABI 370 size_type __removed __attribute__((__unused__)) = 0; 371 #endif 372 list __to_destroy(get_allocator()); 373 iterator __next = __first; 374 while (++__next != __last) 375 { 376 if (*__first == *__next) 377 { 378 __to_destroy.splice(__to_destroy.begin(), *this, __next); 379 #if !_GLIBCXX_USE_CXX11_ABI 380 _GLIBCXX20_ONLY( __removed++ ); 381 #endif 382 } 383 else 384 __first = __next; 385 __next = __first; 386 } 387 388 #if !_GLIBCXX_USE_CXX11_ABI 389 return _GLIBCXX20_ONLY( __removed ); 390 #else 391 return _GLIBCXX20_ONLY( __to_destroy.size() ); 392 #endif 393 } 394 395 template<typename _Tp, typename _Alloc> 396 void 397 list<_Tp, _Alloc>:: 398 #if __cplusplus >= 201103L 399 merge(list&& __x) 400 #else 401 merge(list& __x) 402 #endif 403 { 404 // _GLIBCXX_RESOLVE_LIB_DEFECTS 405 // 300. list::merge() specification incomplete 406 if (this != std::__addressof(__x)) 407 { 408 _M_check_equal_allocators(__x); 409 410 iterator __first1 = begin(); 411 iterator __last1 = end(); 412 iterator __first2 = __x.begin(); 413 iterator __last2 = __x.end(); 414 415 const _Finalize_merge __fin(*this, __x, __first2); 416 417 while (__first1 != __last1 && __first2 != __last2) 418 if (*__first2 < *__first1) 419 { 420 iterator __next = __first2; 421 _M_transfer(__first1, __first2, ++__next); 422 __first2 = __next; 423 } 424 else 425 ++__first1; 426 if (__first2 != __last2) 427 { 428 _M_transfer(__last1, __first2, __last2); 429 __first2 = __last2; 430 } 431 } 432 } 433 434 template<typename _Tp, typename _Alloc> 435 template <typename _StrictWeakOrdering> 436 void 437 list<_Tp, _Alloc>:: 438 #if __cplusplus >= 201103L 439 merge(list&& __x, _StrictWeakOrdering __comp) 440 #else 441 merge(list& __x, _StrictWeakOrdering __comp) 442 #endif 443 { 444 // _GLIBCXX_RESOLVE_LIB_DEFECTS 445 // 300. list::merge() specification incomplete 446 if (this != std::__addressof(__x)) 447 { 448 _M_check_equal_allocators(__x); 449 450 iterator __first1 = begin(); 451 iterator __last1 = end(); 452 iterator __first2 = __x.begin(); 453 iterator __last2 = __x.end(); 454 455 const _Finalize_merge __fin(*this, __x, __first2); 456 457 while (__first1 != __last1 && __first2 != __last2) 458 if (__comp(*__first2, *__first1)) 459 { 460 iterator __next = __first2; 461 _M_transfer(__first1, __first2, ++__next); 462 __first2 = __next; 463 } 464 else 465 ++__first1; 466 if (__first2 != __last2) 467 { 468 _M_transfer(__last1, __first2, __last2); 469 __first2 = __last2; 470 } 471 } 472 } 473 474 template<typename _Tp, typename _Alloc> 475 void 476 list<_Tp, _Alloc>:: 477 sort() 478 { 479 // Do nothing if the list has length 0 or 1. 480 if (empty() || ++begin() == end()) 481 return; 482 483 { 484 typedef __list::_Scratch_list<typename _Node_traits::_Node_base> 485 _Scratch_list; 486 487 // The algorithm used here is largely unchanged from the SGI STL 488 // and is described in The C++ Standard Template Library by Plauger, 489 // Stepanov, Lee, Musser. 490 // Each element of *this is spliced out and merged into one of the 491 // sorted lists in __tmp, then all the lists in __tmp are merged 492 // together and then swapped back into *this. 493 // Because all nodes end up back in *this we do not need to update 494 // this->size() while nodes are temporarily moved out. 495 _Scratch_list __carry; 496 _Scratch_list __tmp[64]; 497 _Scratch_list* __fill = __tmp; 498 _Scratch_list* __counter; 499 500 typename _Scratch_list::template _Ptr_cmp<iterator, void> __ptr_comp; 501 502 __try 503 { 504 do 505 { 506 __carry._M_take_one(begin()._M_node); 507 508 for(__counter = __tmp; 509 __counter != __fill && !__counter->empty(); 510 ++__counter) 511 { 512 513 __counter->merge(__carry, __ptr_comp); 514 __carry.swap(*__counter); 515 } 516 __carry.swap(*__counter); 517 if (__counter == __fill) 518 ++__fill; 519 } 520 while ( !empty() ); 521 522 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 523 __counter->merge(__counter[-1], __ptr_comp); 524 __fill[-1].swap(this->_M_impl._M_node); 525 } 526 __catch(...) 527 { 528 // Move all nodes back into *this. 529 __carry._M_put_all(end()._M_node); 530 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 531 __tmp[__i]._M_put_all(end()._M_node); 532 __throw_exception_again; 533 } 534 } 535 } 536 537 template<typename _Tp, typename _Alloc> 538 template <typename _Predicate> 539 typename list<_Tp, _Alloc>::__remove_return_type 540 list<_Tp, _Alloc>:: 541 remove_if(_Predicate __pred) 542 { 543 #if !_GLIBCXX_USE_CXX11_ABI 544 size_type __removed __attribute__((__unused__)) = 0; 545 #endif 546 list __to_destroy(get_allocator()); 547 iterator __first = begin(); 548 iterator __last = end(); 549 while (__first != __last) 550 { 551 iterator __next = __first; 552 ++__next; 553 if (__pred(*__first)) 554 { 555 __to_destroy.splice(__to_destroy.begin(), *this, __first); 556 #if !_GLIBCXX_USE_CXX11_ABI 557 _GLIBCXX20_ONLY( __removed++ ); 558 #endif 559 } 560 __first = __next; 561 } 562 563 #if !_GLIBCXX_USE_CXX11_ABI 564 return _GLIBCXX20_ONLY( __removed ); 565 #else 566 return _GLIBCXX20_ONLY( __to_destroy.size() ); 567 #endif 568 } 569 570 template<typename _Tp, typename _Alloc> 571 template <typename _BinaryPredicate> 572 typename list<_Tp, _Alloc>::__remove_return_type 573 list<_Tp, _Alloc>:: 574 unique(_BinaryPredicate __binary_pred) 575 { 576 iterator __first = begin(); 577 iterator __last = end(); 578 if (__first == __last) 579 return _GLIBCXX20_ONLY(0); 580 #if !_GLIBCXX_USE_CXX11_ABI 581 size_type __removed __attribute__((__unused__)) = 0; 582 #endif 583 list __to_destroy(get_allocator()); 584 iterator __next = __first; 585 while (++__next != __last) 586 { 587 if (__binary_pred(*__first, *__next)) 588 { 589 __to_destroy.splice(__to_destroy.begin(), *this, __next); 590 #if !_GLIBCXX_USE_CXX11_ABI 591 _GLIBCXX20_ONLY( __removed++ ); 592 #endif 593 } 594 else 595 __first = __next; 596 __next = __first; 597 } 598 599 #if !_GLIBCXX_USE_CXX11_ABI 600 return _GLIBCXX20_ONLY( __removed ); 601 #else 602 return _GLIBCXX20_ONLY( __to_destroy.size() ); 603 #endif 604 } 605 606 #undef _GLIBCXX20_ONLY 607 608 template<typename _Tp, typename _Alloc> 609 template <typename _StrictWeakOrdering> 610 void 611 list<_Tp, _Alloc>:: 612 sort(_StrictWeakOrdering __comp) 613 { 614 // Do nothing if the list has length 0 or 1. 615 if (empty() || ++begin() == end()) 616 return; 617 618 { 619 typedef __list::_Scratch_list<typename _Node_traits::_Node_base> 620 _Scratch_list; 621 622 _Scratch_list __carry; 623 _Scratch_list __tmp[64]; 624 _Scratch_list* __fill = __tmp; 625 _Scratch_list* __counter; 626 627 typename _Scratch_list:: 628 template _Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp 629 = { __comp }; 630 631 __try 632 { 633 do 634 { 635 __carry._M_take_one(begin()._M_node); 636 637 for(__counter = __tmp; 638 __counter != __fill && !__counter->empty(); 639 ++__counter) 640 { 641 642 __counter->merge(__carry, __ptr_comp); 643 __carry.swap(*__counter); 644 } 645 __carry.swap(*__counter); 646 if (__counter == __fill) 647 ++__fill; 648 } 649 while ( !empty() ); 650 651 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 652 __counter->merge(__counter[-1], __ptr_comp); 653 __fill[-1].swap(this->_M_impl._M_node); 654 } 655 __catch(...) 656 { 657 // Move all nodes back into *this. 658 __carry._M_put_all(end()._M_node); 659 for (size_t __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 660 __tmp[__i]._M_put_all(end()._M_node); 661 __throw_exception_again; 662 } 663 } 664 } 665 666 _GLIBCXX_END_NAMESPACE_CONTAINER 667 _GLIBCXX_END_NAMESPACE_VERSION 668 } // namespace std 669 670 #endif /* _LIST_TCC */ 671
