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